對整數的下界和上界查詢的快速數據結構？

我要保持號碼的清單，數高達10萬......對整數的下界和上界查詢的快速數據結構？

如果數據是（例如）

1, 4, 9, 12, 20, 35, 52, 77, 91

，我查詢了一些，說27，我想要剛剛在列表中可用的27之前的數字，那麼將是：20

數據也將經常被修改，就像很多插入和刪除一樣。

目前我使用 stl::set加上

set<int>iterator it = lower_bound(values.begin(), values.end(), n);

所以

*it = 35 與it--，我得到20 ......但這不是足夠快，以查詢次數是大，高達500,000 ..其中包括改變我的價值或查看價值。

請給我一些指點。

來源

2012-01-31 Pheonix

http://xkcd.com/138/ – wilhelmtell 2012-01-31 19:22:33

你想要一個「二叉樹」結構。 – Gabe 2012-01-31 19:26:44

@wilhelmtell是的，在我的路上是帽子裏的男人:) – Pheonix 2012-01-31 19:26:49

想到幾個不同的想法。

對於初學者來說，這個問題有一個專門的數據結構，稱爲van Emde Boas tree，它存儲某個固定範圍[0，U）的整數並支持O（log log U）時間的後繼和前任搜索。這比使用標準的二叉搜索樹進行比較要快得多。如果你知道你正在存儲的整數的上限，這個結構可能會讓你獲得更多的性能。還有其他相關結構，例如y-fast trie也可以在此處使用。其次，如果您擁有的查詢是均勻分佈的，那麼您可能需要構建自己的二叉搜索樹，該搜索樹已進行了優化，以最大限度地減少整體查找的節點數量。這樣的搜索樹被稱爲最優二叉搜索樹，並且存在用於在O（n log n）時間中近似它們的快速算法。在this earlier question中，我詳細介紹了這樣做的一種方法。此預處理可能會使您查找速度更快，因爲該樹是專門爲優化查找時間而構建的。或者，您可以查看splay trees，它們的表現相當。

希望這會有所幫助！

來源

2012-01-31 19:27:06 templatetypedef

優秀:)完全vEB樹:)得到實施在這裏http://www.keithschwarz.com/interesting/code/?dir=van-emde-boas-tree – Pheonix 2012-01-31 20:18:46

可以分割所有數（例如）100個矢量

1-> [0..99] 
2-> [100..199] 
.....

此載體應sorted.Search與LOWER_BOUND/UPPER_BOUND函數矢量通常比在關聯容器更快。但是對於插入或刪除，您需要使用一個小矢量。

UPD 我同意templatetypedf：van Emde博阿斯樹可能是解決方案。

來源

2012-01-31 20:08:11 Andrew

有趣的是，如果你然後打破這些桶分小桶和重複這個過程只需稍作調整，即可獲得van Emde Boas樹木結構。 :-) – templatetypedef 2012-01-31 20:11:38

等等...這不起作用。如果一個元素的後繼者不在同一個桶中呢？ – templatetypedef 2012-01-31 20:27:29

我們總是知道水桶的邊界。爲了找到下一個元素，我們需要檢查下一個分區 – Andrew 2012-01-31 20:39:28

100,000是足夠小，我會考慮只使用一個位向量...... 100,000位只有12.5K，這應該是非常快速的搜索，甚至會適合L1緩存。

向後存儲位（即，接近尾聲100000; 0開始），這樣你的內存掃描是線性的，你可以使用ffs（如果你的平臺有它的話）。

來源

2012-01-31 20:33:38 Nemo

在最壞的情況下，這可能需要線性時間進行掃描。 – templatetypedef 2012-01-31 20:55:10

@templatetypedef：是的，在最壞的情況下，它可能會線性掃描12.5K。根據查詢的實際分佈情況，這可能比通過複雜數據結構追蹤指針快得多。 – Nemo 2012-01-31 21:42:15

對整數的下界和上界查詢的快速數據結構？

回答

相關問題