什麼搜索算法失敗最快

給定一個整數，我需要從一個小集合中找到一個匹配。該整數將幾乎總是而不是在該集合中。對於大多數搜索算法，這是最糟糕的情況（花費最長時間）。但對於此應用程序，搜索時間將由搜索失敗的速度決定。所以我想要一個算法誰最好的情況是'找不到'。什麼搜索算法失敗最快

這樣的事情是否存在？

的整數遠離隨機的，是數組索引 - 說0..10k（15位）。這些集合將包含0..7個整數，這對於簡單的線性搜索來說足夠少。但幾乎在所有情況下，這都是最糟糕的情況。

我能想到的唯一的事情就是布盧姆過濾器。它的工作原理如下：定義F（int）= Set Bit（i AND 1Fh）（即一個32位整數）。對於每個集合，我都會將F（每個元素）（一個32位整數，最大n位設爲n個元素）的OR值存儲在一起。然後搜索IF（F（i）AND F（set））> 0，然後執行線性搜索。

因此搜索將永遠不會被除非至少一個元件具有相同的低5位作爲測試整數i執行。第二個測試可以基於接下來的最低5位添加。

更好的想法任何人？

來源

2012-11-22 Guy Gordon

一組多達7個16位整數將整齊地放入單個緩存行中，所以在內存訪問效率方面，初始方法可能已經是最優化的。是什麼讓你相信線性搜索值得優化呢？ – willglynn

原則上布隆過濾器可能是一個好方法，但只有7個元素，你將很難打線性搜索。你的建議散列不是很好（想想當你有4個元素時，預計有多少位會被設置）。如果SSE指令發揮作用，您可以使用VCMPPS在一條指令中進行比較。 – rlibby

@willglynn，剖析表明這是一個熱點。此代碼位於三重循環內，是跳過大多數內部案例的優化的一部分。涉及的數據結構在設計時考慮了緩存效率。當我想到如何排列設定的元素時，我想這可能是毫無意義的，因爲在大多數情況下我需要檢查整個設置。因此，這個問題。 –

最快的算法，我可以想像，這將成功或失敗立即，布爾是一個巨大的陣列0..MaxInt，全是假的，除了真正的數組[集成員。搜索將是一個簡單的數組查詢：

Found = Array[Test]

但內存佔用是荒謬的。常見的優化是散列陣列。

作爲一個測試，我已經實現了使用成員集合位的完美hash。函數PHash（int）返回整數0..15，它是數組索引，如果存在（）。搜索是：

IF Array[PHash(Test)] = Test 
    THEN Found at Index PHash(Test) 
    ELSE Not Found

它可能會驚訝沒有人表示這將比線性搜索慢。（嘆息）

當然，沒有單個散列可以減少15位整數不同的4位整數。我使用許多不同的散列函數。爲了生成Set，我發現哪個函數爲該Set生成不同的4位散列，然後將該Set存儲爲散列函數指針加上一個16元素數組。每個數組元素都是X或一個Set Member，其中X不在設定的範圍內。（找不到完美的散列會拋出一個異常，但尚未發生。）這些開銷在分析過程中無關緊要，因爲它在程序啓動時完成一次。

要查找一組測試整數，我叫Set.HashFunction（測試），然後比較試驗到Set.Array元。最後的比較與線性搜索的每一步相同。爲了更快，散列函數必須比線性搜索的剩餘比較更快。所以這可能是一個更快的算法，但只適用於足夠大的設置大小。

我還沒有試驗過找到那個尺寸。無論如何，這取決於每個散列函數的速度。

來源

2012-11-23 01:21:19

更廣泛的背景是什麼？我認爲評估這種速度比單個緩存行填充更快的唯一方法是擴展問題範圍。合併或選擇性地消除這些最內部的測試可能是可能的。即使不這樣做，外層循環可能會保證將來需要N次迭代的數據的顯式預取 - 假設邏輯是CPU無法猜測已經預取的內容。沒有更多的信息，這只是猜測。 – willglynn

什麼搜索算法失敗最快

回答

相關問題