Cho một tập tin phẳng của IP Ranges và ánh xạ, tìm một thành phố đưa ra một IP

Question

Đây là câu hỏi:

Cho một tập tin văn bản bằng phẳng có chứa một dải địa chỉ IP mà bản đồ đến một vị trí (ví dụ 192.168.0.0-192.168.0.255 = Boston, MA), đưa ra một thuật toán sẽ tìm thành phố cho địa chỉ IP cụ thể nếu có bản đồ.

Ý tưởng duy nhất của tôi là phân tích tệp và biến phạm vi IP thành chỉ ints (nhân với 10/100 nếu thiếu chữ số) và đặt chúng trong danh sách, đồng thời đặt thấp hơn của dải ô vào băm làm khóa với vị trí dưới dạng giá trị. Sắp xếp danh sách và thực hiện tìm kiếm nhị phân được sửa đổi một chút. Nếu chỉ mục là lẻ, -1 và tìm trong băm. Nếu nó thậm chí, chỉ cần nhìn vào băm.

Bất kỳ lỗi nào trong kế hoạch của tôi hoặc giải pháp tốt hơn?

Answer 1

Trong ví dụ của bạn, 192.168.0.0-192.168.0.255 = Boston, MA.

Ba octet đầu tiên (192.168.0) có giống nhau cho cả hai địa chỉ IP trong mục nhập không? Ngoài ra, ba octet đầu tiên sẽ là duy nhất cho một thành phố?

Nếu có thì vấn đề này có thể giải quyết dễ dàng hơn

Answer 2

Cách tiếp cận của bạn có vẻ hoàn toàn hợp lý.

Nếu bạn quan tâm đến việc nghiên cứu/mã hóa thêm, có các thuật toán sẽ làm tốt hơn kỹ thuật tìm kiếm nhị phân chuẩn dựa trên thực tế là địa chỉ IP của bạn có thể được hiểu là số nguyên trong phạm vi từ 0 đến 2 - 1. Ví dụ, các cấu trúc dữ liệu van Emde Boas tree và y-Fast Trie có thể thực hiện thao tác tìm kiếm tiền nhiệm mà bạn đang tìm kiếm trong thời gian O (nhật ký U), trong đó U là địa chỉ IP tối đa có thể. Cách tiếp cận O (log N) mà tìm kiếm nhị phân sử dụng. Tuy nhiên, các yếu tố liên tục cao hơn, có nghĩa là không có gì đảm bảo rằng cách tiếp cận này sẽ nhanh hơn. Tuy nhiên, có thể đáng để khám phá như một cách tiếp cận khác có khả năng thậm chí còn nhanh hơn.

Hy vọng điều này sẽ hữu ích!

Answer 3

Sự cố có mùi của phạm vi và một trong những cấu trúc dữ liệu tốt cho vấn đề này sẽ là Cây phân đoạn. Someresources để giúp bạn bắt đầu.

Gốc của cây phân khúc có thể biểu thị địa chỉ (0.0.0.0 - 255.255.255.255). Cây con bên trái sẽ đại diện cho các địa chỉ (0.0.0.0 - 127.255.255.255) và cây con bên phải sẽ đại diện cho phạm vi (128.0.0.0 - 255.255.255.255), v.v. Điều này sẽ tiếp tục cho đến khi chúng ta đạt đến phạm vi mà không thể được chia nhỏ hơn nữa. Giả sử, nếu chúng ta có phạm vi 32.0.0.0 - 63.255.255.255, ánh xạ tới một số thành phố tùy ý, nó sẽ là nút lá, chúng tôi sẽ không chia nhỏ phạm vi đó khi chúng tôi đến đó và gắn thẻ cho thành phố cụ thể.

Để tìm kiếm một ánh xạ cụ thể, chúng tôi theo dõi cây, giống như chúng ta thực hiện trong Cây tìm kiếm nhị phân. Nếu IP của bạn nằm trong phạm vi của cây con bên trái, hãy di chuyển đến cây con bên trái, chuyển sang cây con bên phải.

Các bộ phận tốt:

1. Bạn không cần phải có tất cả các cây con, chỉ có thêm cây con được yêu cầu.Ví dụ: nếu trong dữ liệu của bạn, không có thành phố nào được ánh xạ cho phạm vi (0.0.0.0 - 127.255.255.255), chúng tôi sẽ không xây dựng cây con đó.
2. Chúng tôi là không gian hiệu quả. Nếu toàn bộ phạm vi được ánh xạ tới một thành phố, chúng tôi sẽ chỉ tạo nút gốc!
3. Đây là cấu trúc dữ liệu động. Bạn có thể thêm nhiều thành phố, dải phân chia sau này, v.v.
4. Bạn sẽ thực hiện số lần hoạt động liên tục vì độ sâu tối đa của cây sẽ là 4 x log2 (256) = 32. Đối với vấn đề cụ thể này, hóa ra rằng Phân đoạn cây sẽ là nhanh như cây van-Emde Boas và yêu cầu không gian nhỏ hơn (O (N)).
5. Đây là cấu trúc dữ liệu đơn giản nhưng không tầm thường, tốt hơn là phân loại, vì nó là động và dễ giải thích hơn cho người phỏng vấn của bạn so với cây van-Emde Boas.
6. Đây là một trong những không tầm thường dữ liệu cấu trúc đơn giản nhất để mã :)

Xin lưu ý rằng trong một số hướng dẫn Segment Tree, họ sử dụng mảng để đại diện cho cây. Điều này có lẽ không phải là những gì bạn muốn, vì chúng tôi sẽ không phổ biến toàn bộ cây, do đó, phân bổ động các nút, giống như chúng ta làm trong một cây nhị phân chuẩn là tốt nhất.

Answer 4

ý tưởng duy nhất của tôi là phân tích các tập tin, và lần lượt các dãy IP vào chỉ ints (nhân với 10/100 nếu nó thiếu chữ số) ...

Nếu sau phương pháp này, bạn sẽ có thể muốn nhân với 256^3, 256^2, 256 và 1 tương ứng cho A, B, C và D trong một địa chỉ ABCD Điều đó có hiệu quả tái tạo địa chỉ IP dưới dạng số không dấu 32 bit.

... và đặt chúng trong danh sách, đồng thời đặt giá trị thấp hơn của dãy vào băm làm khóa với vị trí dưới dạng giá trị. Sắp xếp danh sách và thực hiện tìm kiếm nhị phân được sửa đổi một chút. Nếu chỉ mục là lẻ, -1 và tìm trong băm. Nếu nó thậm chí, chỉ cần nhìn vào băm.

Tôi khuyên bạn nên tạo một mảng liền kề (một std::vector) chứa các cấu trúc có dải dưới và trên (và tên vị trí - được thảo luận bên dưới). Sau đó, như bạn nói bạn có thể tìm kiếm nhị phân cho một phạm vi bao gồm một giá trị cụ thể, mà không có bất kỳ phức tạp lẻ/thậm chí.

Sử dụng đầu dưới của phạm vi làm khóa trong băm là một cách để tránh không gian cho tên vị trí trong mảng, nhưng với số ký tự trung bình trong tên thành phố, kích thước có thể của con trỏ, một sự lựa chọn giữa một bảng băm dân cư thưa thớt và các danh sách chuyển dịch dài để tìm kiếm trong các thùng thay thế liên tiếp hoặc gián tiếp hơn đến các thùng chứa chiều dài tùy ý - bạn cần phải khá tuyệt vọng để làm phiền việc thử. Trong trường hợp đầu tiên, lưu trữ vị trí trong cấu trúc cùng với phạm vi giá trị IP có vẻ tốt.

Hoặc, bạn có thể tạo cây dựa trên ví dụ: các giá trị IP 0-255 riêng lẻ: mỗi cấp trong cây có thể là một mảng gồm 256 giá trị để lập chỉ mục trực tiếp hoặc một mảng được sắp xếp các giá trị được điền. Điều đó có thể làm giảm số lượng so sánh giá trị IP mà bạn có thể cần phải thực hiện (O (log2N) đến O (1)).