元組索引的數據結構

我需要一個存儲元組的數據結構，並且允許我執行如下查詢：給定整數的元組，找到下一個（爲其設置的上限）。我的意思是考慮自然順序(a,b,c)<=(d,e,f) <=> a<=d and b<=e and c<=f。我已經嘗試MSD基數排序，它將項目拆分成桶並對它們進行排序（並且對於元組中的所有位置遞歸地執行此操作）。有人有其他建議嗎？理想情況下，我希望在O（log n）內發生高級查詢，其中n是元組的數量。元組索引的數據結構

來源

2013-03-19 user1377000

如果您有abc（2,2,2），其次是（3,1,3）或（3,2,2）或者甚至是（2,3,3）？希望根據期望的順序清楚。 – rlb 2013-03-20 09:18:12

謝謝。我很抱歉沒有足夠具體。假設我們能夠將每個元組轉換爲相應的基數爲10的整數。接下來將是_smallest_這樣的整數大於當前的整數。因此，在你的例子中，（2,2,2）<（2,3,3）<（3,1,3）<（3,2,2）。 – user1377000 2013-03-20 09:37:15

順便說一句，如果你想要建議類似的東西:)（考慮到潛在的巨大空間和我們對4或8字節的限制），轉換爲10的基數是沒有問題的。 – user1377000 2013-03-20 09:38:01

有兩個選項。

在排序後的數組上使用二進制搜索。如果你用一個簡單的數組來構建密鑰（假設是32位int）'，並且把它們放在一個簡單的數組中，你可以使用二分搜索來定位這個值你正在尋找（如果使用C，甚至有一個庫函數來做到這一點），下一個只是一個位置。最壞情況下的性能是O（logN）的，如果你能做到http://en.wikipedia.org/wiki/Interpolation_search那麼你可能甚至接近O（log日誌N）

問題的二進制鍵的可能會非常棘手添加新值，可能需要回旋如果您將超過有效內存。但速度很快，平均只有少量隨機存儲器訪問。

或者，您可以通過以某種形式生成帶有| b | c的鍵來構建哈希表，然後讓哈希數據指向包含下一個值的結構，無論該結構如何。在創建表格時，可能有點難以創建，您需要知道下一個值。

哈希方法的問題是它可能會比二元搜索方法使用更多的內存，如果你沒有散列衝突，但性能很好，但是然後開始丟棄，雖然這個算法有一些變化來幫助一些案例。哈希方法可能更容易插入新值。

我也看到你不得不沿着這些路線類似的問題，所以我想的是什麼，我說是結合了膽量，B，C，產生一個單一的長鍵，並使用二進制搜索，哈希甚至b樹。如果密鑰的長度是你的問題（什麼語言），你能把它當作一個字符串嗎？

如果這個答案是完全離開基地，讓我知道，我會看看如果我可以刪除這個答案，所以你的問題仍然沒有答案，而不是一個無用的答案。

來源

2013-03-21 08:05:30 rlb

這實際上是一個很好的答案。有兩件事情不清楚：1）在這種情況下，B樹的優勢是什麼，比如說，平衡二叉搜索樹？（有沒有？）2）我正在使用Java。如果我使用了BigInteger之類的東西，我還可以在每次需要時計算密鑰。 – user1377000 2013-03-21 08:26:27

另外，比較鍵的複雜性是什麼？ – user1377000 2013-03-21 08:41:11

第一個選項是一個簡單的數組，而不是一棵樹。如此定義：struct {int key [3];數據...; } theArray [NNN];搜索你開始它的中間NNN/2，然後根據比較上升或下降。比較密鑰時，您檢查密鑰[0]，並且只需要檢查密鑰[1]，如果值相等，請參閱java中的http://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search上的示例。涵蓋了大量的例子。 – rlb 2013-03-24 02:09:23

元組索引的數據結構

回答

相關問題