thuật toán hiệu quả để kiểm tra _which_ đặt một số cụ thể thuộc về

Question

Nếu tôi có một phạm vi lớn các phạm vi liên tục (ví dụ: [0..5], [10..20], [7..13], [- 1. .37]) và có thể sắp xếp các bộ đó thành bất kỳ cấu trúc dữ liệu nào tôi thích, cách hiệu quả nhất để kiểm tra là gì đặt một số thử nghiệm cụ thể thuộc về?

Tôi đã nghĩ về việc lưu trữ các bộ trong cây nhị phân cân bằng dựa trên số lượng thấp của một tập hợp (và mỗi nút sẽ có tất cả các tập có cùng số lượng thấp nhất của tập hợp của chúng). Điều này sẽ cho phép bạn prune hiệu quả số lượng các bộ dựa trên việc test_number bạn đang thử nghiệm với các bộ là ít hơn số thấp nhất của một tập hợp, và sau đó cắt tỉa nút đó và tất cả các nút ở bên phải của nút đó (mà có số thấp trong phạm vi của chúng lớn hơn số test_number). Tôi nghĩ rằng sẽ cắt giảm khoảng 25% của các bộ trung bình, nhưng sau đó tôi sẽ cần phải tuyến tính nhìn vào tất cả các phần còn lại của các nút trong cây nhị phân để xác định xem test_number thuộc về những bộ. (Tôi có thể tối ưu hóa thêm bằng cách sắp xếp danh sách các bộ tại bất kỳ nút nào bằng số cao nhất trong tập hợp, cho phép tôi thực hiện tìm kiếm nhị phân trong một danh sách cụ thể để xác định tập hợp nào, nếu có, chứa số test_number. Tôi nghĩ rằng vấn đề này đã được giải quyết trong xử lý đồ họa vì họ đã tìm ra các cách để kiểm tra hiệu quả các đa giác nào trong toàn bộ mô hình của chúng sẽ đóng góp. với một pixel cụ thể, nhưng tôi không biết thuật ngữ của loại thuật toán đó.

Answer 1

Trực giác của bạn về sự liên quan của vấn đề với đồ họa là chính xác. Cân nhắc xây dựng và truy vấn segment tree. Nó đặc biệt thích hợp cho truy vấn đếm bạn muốn. Xem thêm description in Computational Geometry của nó.

Answer 2

Tôi nghĩ rằng tôi sẽ tổ chức chúng theo cùng cách các trang chỉ mục của Mediawiki - dưới dạng bucket sort. Tôi không biết rằng đó là thuật toán hiệu quả nhất, nhưng nó phải nhanh và dễ thực hiện (thậm chí tôi đã quản lý nó và trong SQL tại đó !!).

Về cơ bản, thuật toán cho phân loại là

For Each SetOfNumbers 
    For Each NumberInSet 
     Put SetOfNumbers into Bin(NumberInSet) 

Sau đó, để truy vấn, bạn chỉ có thể đếm số mục trong Bin (MyNumber)

Cách tiếp cận này sẽ làm việc tốt khi SetOfNumbers của bạn hiếm khi thay đổi, mặc dù nếu họ thay đổi thường xuyên thì thường không quá khó để giữ cho Thùng được cập nhật. Đó là bất lợi chính là nó giao dịch không gian, và thời gian phân loại ban đầu, cho các truy vấn rất nhanh.

Lưu ý rằng trong thuật toán tôi đã mở rộng phạm vi thành SetsOfNumbers - liệt kê mọi số trong một phạm vi nhất định.

Answer 3

Tôi nghĩ việc xây dựng một cấu trúc cây sẽ tăng tốc độ đáng kể (miễn là bạn có đủ bộ và số để kiểm tra xem nó có xứng đáng với chi phí ban đầu) hay không. Thay vì một cây nhị phân, nó phải là một cây bậc ba. Mỗi nút phải có các nút trái, giữa và phải, trong đó nút bên trái chứa một tập hợp hoàn toàn ít hơn tập hợp nút, bên phải là lớn hơn, và phần giữa đã chồng lên nhau.

   Set1 
      /| \ 
      / | \ 
      / | \ 
     Set2 Set3 Set4 

Thật nhanh chóng và dễ dàng để biết liệu có trùng lặp trong các bộ vì bạn chỉ phải so sánh giá trị tối thiểu và tối đa để đặt chúng. Trong trường hợp đơn giản trên, Set2 [max] < Set1 [min], Set4 [min]> Set1 [max], và Set1 và Set3 có một số chồng lên nhau.Điều này sẽ tăng tốc độ tìm kiếm của bạn bởi vì nếu số bạn đang tìm kiếm nằm trong Set1, nó sẽ không nằm trong Set2 hoặc Set4, và bạn không phải kiểm tra chúng.

Tôi chỉ muốn chỉ ra rằng việc sử dụng lược đồ như thế này chỉ tiết kiệm thời gian cho việc thực hiện ngây thơ của việc kiểm tra mọi bộ nếu bạn có nhiều số để kiểm tra hơn bạn có bộ.