Xóa các tập hợp con là

Question

Giả sử bạn có hai danh sách các tập hợp số nguyên. Gọi cho họ A và B. Mỗi bộ trong A có thể được chứa trong một trong các bộ trong B. Thuật toán hiệu quả nhất để tìm tất cả các phần tử trong A sao cho không có phần tử nào được chứa trong bộ B?

Answer 1

Để thử và cắt không gian tìm kiếm, chúng tôi có thể thử một số kiểm tra và bộ lọc như một phần của tìm kiếm. Để lấy một ví dụ của bạn trong các ý kiến,

A = [{1,2},{1,4},{3,4,7}] 
B = [{2,3,4},{1,2,4},{1,2,5,6}]  

bắt đầu với một đếm O (n) của các yếu tố độc đáo trong bộ như phím trỏ đến chỉ số chéo tương quan của các bộ họ thuộc về:

1: A: {0,1}, B: {1,2} 
2: A: {0} , B: {0,1,2} 
3: A: {2} , B: {0} 
4: A: {1,2}, B: {0,1} 
5: A: {} , B: {2} 
6: A: {} , B: {2} 
7: A: {2} , B: {} 

Chúng ta có thể ngay lập tức đặt sang một bộ trong A bao gồm một phần tử không tìm thấy trong B, chẳng hạn như tập thứ ba của A.

Bây giờ, chúng ta sẽ đi qua từng bộ trong A chưa được loại trừ và kiểm tra xem có một giao điểm hoàn chỉnh tương ứng của ít nhất một bộ trong B. Vì số lượng chỉ mục trong trường hợp của bạn là trong hàng triệu , thay vì ban đầu vượt qua B toàn bộ, chúng tôi sẽ chia phép kiểm tra B thành các phần, mỗi bộ k, nói 1024. Hơn nữa, để biểu diễn 1024 chỉ mục này, chúng tôi sẽ chia chúng thành 16 bit 64 bit chúng ta có thể bitwise AND (&) cái này với cái khác.

Tại bất kỳ điểm nào trong traversal này, chúng tôi được hưởng lợi từ một lối ra sớm nếu kết quả AND hoạt động trong điều kiện không:

set A[0] => elements 1,2 => set-index-intersection in B: b110 & b111 => match 
set A[1] => elements 1,4 => set-index-intersection in B: b110 & b11 => match 

Nhìn chung, phần bởi phần làm việc, chúng tôi đang tìm kiếm khoảng 10 * 16 hoạt động để kiểm tra xem một bộ trong A có được bao gồm trong một trong các bộ trong phần hiện tại của k bộ B hay không. Nói cách khác, chúng tôi đã giảm số lượng hoạt động từ 10.000.000 xuống 160.000 để kiểm tra toàn bộ một bộ trong A (mỗi một triệu bộ trong B). Đó là một yếu tố của 62.