tìm kiếm boolean trên một mảng

Question

Tôi có nhiều mảng với khoảng 100 giá trị có thể, ví dụ:

a[0] = (a, b, c, d) 
a[1] = (a, e) 
a[2] = (d, f, g) 

Tôi muốn nhanh chóng tiện lợi trở lại đó mảng chứa (một || b) & & (d || e)

trong ví dụ này, 0 và 1

Tôi đã suy nghĩ về hoạt động bitwise ... như đại diện cho "abcd" theo "1111"; "quảng cáo" bởi "1001", v.v. Sau đó, tôi có thể giải quyết "OR" chỉ với một bit OR, và sau đó kiểm tra xem cả hai có khác không

bất kỳ ai có thể nghĩ ra giải pháp tốt hơn không? điều này không phải là rất phức tạp vì nó dường như không thể leo thang được

có bất kỳ DBMS nào có thể thực hiện điều đó nhanh chóng không? Tôi đã thử với mongodb, nhưng có vẻ như họ đã không thêm chức năng "$ và" (doc nói rằng nó trên phiên bản 1.9.1, nhưng tôi chỉ có thể tải xuống 1.9.0, và nó không ổn định anyway)

I giả sử đó là một "tìm kiếm boolean", tương tự như những gì google làm tất cả các thời gian ... vì vậy tôi đoán có một cách tốt hơn (có thể không quá nhanh, nhưng leo thang hơn) hơn

Answer 1

Vâng, một giải pháp bitwise hoạt động khá độc đáo cho việc này. Có, một số cơ sở dữ liệu bao gồm một khả năng như vậy, thường được đặt tên một cột bitmapped (hoặc bitmap chỉ mục, tùy thuộc). Lời khuyên thông thường là áp dụng nó vào một cột có số lượng thẻ tương đối thấp (nghĩa là, một số lượng khá nhỏ các giá trị có thể, chẳng hạn như giới tính).

Answer 2

Trong ý nghĩa nào là nó không thể mở rộng? 16 byte dữ liệu cho mỗi mảng (bit) không phải là xấu! Tôi không chắc chắn lý do tại sao bạn muốn có một DBMS cho việc này; bạn có thể đặt dữ liệu nhị phân trong đó nếu bạn cần (hy vọng khối của mảng), và kéo nó ra để truy vấn. Trừ khi bạn đang lập kế hoạch có hàng tỷ mảng.

Đối với số lượng nhỏ các phần tử, logic bit là nhanh nhất. Nhưng nếu bạn bắt đầu đi xa hơn 100 giá trị, thì việc giữ các mảng được sắp xếp và thực hiện tìm kiếm nhị phân (hoặc thậm chí tuyến tính!) Sẽ nhanh hơn. Bạn sẽ cần điểm chuẩn trên hệ thống của mình để tìm điểm ngắt chính xác, nhưng nếu mảng của bạn có ~ 4 phần tử, tôi thường tìm kiếm tuyến tính nhanh hơn (đếm số lần xuất hiện của các phần tử bạn đang tìm kiếm trong logic boolean) bạn đi), và nó đánh bại toán học nhị phân vào khoảng cùng một điểm mà biểu diễn nhị phân cũng trở nên lớn hơn.

Answer 3

Lưu trữ mảng của bạn như là một Trie, ví dụ:

a 
b 
    c 
    d 
e 
d 
f 
    g 

Tạo một Trie từ biểu thức là tốt, ví dụ như,

a 
b 
    d 
    e 
d 
e 
b 
d 
e 

Bạn có thể phù hợp với Trie sau so với trước đây (bỏ qua bất kỳ các giá trị không có trong biểu thức, ví dụ: 'c', 'f' và 'g') để nhận các giải pháp. Tôi để lại các chi tiết của biểu diễn trie và thuật toán phù hợp với bạn.

Answer 4

Như bạn đã nói, các giá trị có thể có khoảng 100, nhưng bạn có nhiều mảng, tôi nghĩ bảng băm hoạt động tốt hơn (các) thao tác mức bit.
Ví dụ:
có một bảng băm thiết lập với các giá trị trong biểu hiện, tức là a, b các thiết lập để 1 và d, e thiết lập để 2.

for each array a in arrays  
    for each value v in array 
    sum+= ht[v] 
    if sum == 3 
     print found 
     break 

(ở trên sẽ không có bản sao mặc dù!)
vòng đầu tiên cho vòng lặp có thể được song song, có thể với khung bản đồ giảm hoặc thậm chí là openMP.
(btw thứ hai cho cũng có thể được song song!)
Điều này sẽ nhanh hơn việc xây dựng biểu diễn bit của toàn bộ phần tử trong mảng và thực hiện AND hoặc OR. Về cơ bản bạn có lợi với trường hợp tốt nhất (ví dụ: a và d là 2 phần tử đầu tiên!) Trường hợp xấu nhất là giống nhau cho cả hai phương pháp (có thể là nếu được thực hiện cho mọi phần tử trên đầu)