陣列上布爾搜索

我有多個陣列用約100個可能值，即：陣列上布爾搜索

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

欲快速度返回其陣列含有（a || b）中& &（d || E）

在這個例子中，0和1

我在想按位操作......就像用「1111」代表「abcd」; 「ad」by「1001」，依此類推。然後我可以用OR來解決「OR」，然後檢查兩者是否都爲非零。

誰能想出更好的解決方案？這一個不是很實用，因爲它似乎不是非常容易的

有沒有可以快速做到這一點的任何DBMS？我用mongodb嘗試過，但它似乎沒有添加「$和」功能（doc說它是1.9.1版本，但我只能下載1.9.0，並且它不穩定）

I假設這是一個「布爾搜索」，類似於谷歌一直在做的事情...所以我猜測有一個更好的方法（可能不是那麼快，但更容易）

來源

2011-07-26 Lem0n

如果你的數組只有100可能的值，按位解決方案似乎很不錯。 –

與往常一樣，在內存速度競爭中，如果您可以負擔得起復制數據庫，那麼它變得微不足道（至少在概念上）。你說「你只有」有100萬個陣列，最多80個值。因此，只需構建80個數組，其中第一個包含數組的索引，等等......說實話，我只是猜測使用整數列表，這將比通過「按位表示」迭代多次更快。 – Fezvez

是的，一個按位解決方案的作品這很好。是的，有些數據庫包含這種功能，通常稱爲位圖列（或位圖索引，具體取決於）。通常的建議是將其應用於基數相對較低的列（即性別相對較小的可能值）。

來源

2011-07-26 05:04:48

從何種意義上說它不可擴展？每個（位）數組的16字節數據並不差！我不確定爲什麼你需要一個DBMS;你可以把二進制數據放在那裏，如果你需要（希望數組塊），並把它全部出來查詢。除非你計劃擁有數十億的陣列。

對於少量元素，位邏輯最快。但是如果你開始遠遠超過100個值，那麼保持數組排序並進行二進制（甚至是線性！）搜索將會更快。您需要在您的系統上進行基準測試以找到確切的截止點，但是如果您的陣列每個都有〜4個元素，我通常會更快地找到線性搜索（在布爾邏輯中計算要查找的元素的出現次數爲你去），並且它在二進制表示也變得更大的同一點上擊敗二進制數學。

來源

2011-07-26 05:22:10

我的可伸縮性問題是，如果我擁有80個可能的值和100萬個數組，我必須通過所有的數組進行按位操作。所以這是關於數據數量的O（N）。也許有一個解決方案是O（N）（或者甚至O（N^3））的可能值的數量呢？ – Lem0n

我能想到的是以某種方式創建一個允許布爾搜索的「可能值」的樹。而葉子將是匹配這個搜索的所有鍵。 – Lem0n

@ Lem0n - 您可以從每個可能的值到包含它的每個數組創建一個映射。然後你只需要合併和交叉地圖。但是，這可能只是執行按位事件的操作次數的1/20，而操縱一位可能會快20倍以上。 –

Store中的數組作爲一個線索，例如，

a 
b 
    c 
    d 
e 
d 
f 
    g

創建一個從表達的線索，以及，例如，

a 
b 
    d 
    e 
d 
e 
b 
d 
e

可以對前者匹配後者特里（忽略任何不在表達式中的值，即'c'，'f'和'g'）來獲得解決方案。我把你的trie表示和匹配算法的細節留給你。

來源

2011-07-26 07:29:07

正如你所說的可能的值大約是100，但是你有很多數組，我認爲哈希表比比特級操作更好。例如：
例如。
有一個哈希表中的值在表達式中設置，即A，B設爲1和d，E設定爲2。

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

（以上不會與重複雖然！）
第一個for循環可以並行化，可能帶有map-reduce框架甚至openMP。
（順便說一句，也可以並行化！）
這應該比構建數組中的整個元素的位表示並執行AND或OR更快。你基本上從最好的情況中受益（例如a和d是前兩個元素！）兩種方法的最壞情況都是相同的（可能是因爲每個元素都是開銷）

來源

2011-08-16 16:38:38 Davinc

陣列上布爾搜索

回答

相關問題