請有人向我推薦一些 c# 中的集合（或者提示我如何自己實作它）來存盤鍵值對，我將始終最多擁有 50 個這些鍵值對。但通常只有 5-20 個鍵值對。而且我需要絕對最快的檢索給定鍵的值。首先我想到了字典，因為它的檢索訪問時間為 O(1)。但我仍然不確定為如此小的集合使用字典的開銷。但我猜 Dictionary 即使對于像這樣的小集合也能提供最好的速度？
然后我有另一個要求，我需要能夠告訴給定鍵的下一個更大的鍵（例如，我有值為 2、4、6、8、10、11、12、15 的鍵，當我說讓我們說7，我需要能夠快速判斷，下一個比 7 更大的鍵是 8)。于是想著把這些key的集合進行排序，這樣就可以很快的分辨出下一個更大的key）。我當時考慮使用 SortedDictionary，但我發現它的訪問速度較慢 O(log(n))，但會為我提供尋找下一個更大密鑰的另一個好處。
順便說一句，通過這個集合的整個使用，它永遠不會被修改，它只需要在開始時構建，這可能會很慢，對我來說構建它的速度無關緊要。此外，我根本不關心記憶體使用情況。
例如，我的解決方案也可以結合 Dictionary 和 SortedList。它將 2 個集合組合在一起，以最大限度地提高檢索速度和“getNextBiggerKey”速度。
或者現在我也在考慮將 nextBiggerKey 存盤在該鍵值對的值中。因此，至少對于那些已經在收藏中的鑰匙，它會給我下一個更大的鑰匙。
那么有人有什么好主意嗎，如何在這種情況下完全最大化性能？
更新：我所說的鍵實際上是分數型別的。但是對于低值，分子和分母都不會大于 256，因此位元組應該（很有可能）對它們都足夠。
非常感謝您的幫助，將不勝感激:)
uj5u.com熱心網友回復：
這個答案假設可能的鍵范圍很小（最多幾千個）。在這種情況下，您可以實作基于查找表的解決方案。假設小數鍵的范圍在 10 到 14 之間，包括一半和四分之一。還假設您在此范圍內有 4 個鍵，其值分別為 10、10 3/4、12 1/2 和 13。首先，您需要一種將鍵轉換為整數的方法，該整數將用作索引陣列。在這種情況下，翻譯函式將是：
f(x) = (x - 10) * 4
所以鍵 10 被轉換為索引 0，鍵 14 被轉換為索引 16。接下來您需要構造一個長度為 17（從 0 到 16）的陣列。下表顯示了該陣列的值：
| Key | Translated | Index | Value |
|---------|------------|---------|---------|
| 10 | 0 | 0 | 0 |
| 10 1/4 | 1 | 1 | 3 |
| 10 1/2 | 2 | 2 | 3 |
| 10 3/4 | 3 | 3 | 3 |
| 11 | 4 | 4 | 10 |
| 11 1/4 | 5 | 5 | 10 |
| 11 1/2 | 6 | 6 | 10 |
| 11 3/4 | 7 | 7 | 10 |
| 12 | 8 | 8 | 10 |
| 12 1/4 | 9 | 9 | 10 |
| 12 1/2 | 10 | 10 | 10 |
| 12 3/4 | 11 | 11 | 12 |
| 13 | 12 | 12 | 12 |
| 13 1/4 | 13 | 13 | -1 |
| 13 1/2 | 14 | 14 | -1 |
| 13 3/4 | 15 | 15 | -1 |
| 14 | 16 | 16 | -1 |
不，讓我們使用這個陣列進行一些搜索。
- 密鑰 12 存在嗎？我們應用翻譯函式
(12 - 10) * 4，得到索引 8。 的值為array[8]10。10 與 8 不同，因此鍵 12 不存在。 - 10 3/4 鍵的下一個更大的鍵是什么？我們應用翻譯函式，得到索引 3。它
array[3]是 3，所以鍵存在，但我們對此不感興趣。我們需要查看下一個陣列元素，array[4]. 它的值為 10，它是鍵 12 1/4 的翻譯。所以下一個更大的 10 3/4 鍵是 12 1/4。
現在您已經有了一種按鍵搜索此結構的方法，您可以考慮如何將每個鍵與一個值相關聯，最終得到一個正確的字典。最簡單的方法可能是在混合中添加另一個長度相等的陣列，將每個鍵的值存盤在同一索引中。
uj5u.com熱心網友回復：
如果鍵實際上是您顯示的整數，則計算散列來搜索元素沒有任何優勢（因此不需要散列鍵的集合）。由于您可以構建一次串列，然后可以使用不可變串列，因此我認為二進制搜索是您可以獲得的最快速度。
我首先要嘗試的是普通List<T>的 KeyValue 對，用專案填充它，對其進行一次排序，然后使用List.BinarySearch()搜索元素。可以肯定的是，您應該對多個場景進行基準測驗，但這肯定是一個好的開始。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/410079.html
標籤：