需要在插入時快速的關聯數組，尋找最近的鍵，並按鍵順序迭代

我正在執行類似於N維卷積的操作，但會在我進行時合併彼此接近的值以保存記憶和時間。需要在插入時快速的關聯數組，尋找最近的鍵，並按鍵順序迭代

我在數組中尋找一個鍵。
如果我找到密鑰，我添加到存儲在該密鑰的值。
如果我找不到密鑰，我找到下一個最高和最低的密鑰。
如果兩個鄰居之間的距離近得足夠近，那麼我就用該鍵值對進行累加。
否則，我添加一個新的鍵值對。

關鍵是雙。它永遠是積極的，永遠不會無限。（我專門處理零。）我預計價值從幾分錢到高達1000億美元。隨着算法繼續保持10,000和1,000,000之間的最大數組大小，舍入粗糙度將會改變。（只有測試才能在速度，內存和準確性之間進行折衷，揭示最佳區域）。由於數值範圍與數組大小的關係，直接尋址並不實際;我需要稀疏的存儲空間。

天真的方法是使用列表並執行BinarySearch查找鍵或插入點，然後從那裏繼續。這對於查找最近的密鑰很快，可以按鍵順序進行迭代，但插入非常可怕。（我不需要執行刪除操作！外循環中的每次迭代都會從頭開始創建一個新列表。）

建議使用哪種數據結構？維基百科提到了一些，如Trie，Judy陣列等。

（我在幾年前實現了類似Trie的特性，但那是在java中，花了我一個星期的時間來執行，而且很棘手。時間）

更新：

的SortedSet的建議，使我改變我的要求。找到下一個最低和最高的鍵是我完成我的任務的方式，SortedSet.GetViewBetween以不同的方式處理事情。因爲我只是想看看是否有足夠的接近與彙整的價值，我有一定的舍入粒度G，我可以用

var possibilities = mySet.GetViewBetween(x - G, x + G)

如果設置爲空只要求所有感興趣的元素，我需要補充。如果不是，它可能是一個小集合，我遍歷它。

我需要執行性能測試以查看它是否足夠快。但即使它沒有，具有相同合同的另一個集合也是FindNextHighestKey和FindNextLowestKey的可接受替代方案。

更新2：

我已決定使用純詞典，並迫使鍵成使用自定義的舍入函數的桶。以排序順序對項目進行迭代並不重要，通過使用這個舍入函數，我可以找到「足夠接近」的值來進行聚合。在迭代過程中我不會改變粒度;每當我完成一個新的維度時，我會調整它。每次迭代我創建一個新數組來保存該通道的結果。

來源

2013-01-11 Paul Chernoch

這是功課嗎？ – daryal

我知道沒有建立在支持這個集合。 BCL對有序集合的支持很糟糕。 – CodesInChaos

不是功課。該應用是由於颶風導致的N個屬性的概率損失獲得損失預期值的N倍卷積。保險風險分析。 –

如果你的關鍵是獨一無二的，你可以看Dictionary<TKey,TValue>或SortedDictionary<TKey,TValue>

來源

2013-01-11 15:02:50 chameleon86

你將如何實現「如果我找不到密鑰，我找到下一個最高和最低的密鑰。」 – CodesInChaos

我不相信有一種有效的機制可以從這兩者中獲得「相鄰密鑰」。 –

有一種有效的方法來查看密鑰是否在x-k和x + k之間：爲強制粒度要求的字典編寫自定義比較器。但是，隨着我的算法的進行，我將根據需要擴大粒度，一旦將項目添加到字典中，最好不要在比較中間更改比較器！ –

我發現this question，這讓我SortedSet<T>。

如果你可以插入，刪除，並查找處理O（日誌（N）），這可能是你應該讓你的鑰匙。

根據您的新要求......爲什麼不直接使用之前的粒度疏鍵雙打地圖，並用Dictionary<double, T>去？如果您希望在運行時更改粒度，但這不會起作用，但其他方法也不會真的如此。

來源

2013-01-11 15:11:52

似乎有點討厭使用，但它應該有可能實現一個二進制搜索。 – CodesInChaos

@CodesInChaos它是一個二叉搜索樹。您只需調用SortedSet.Contains來執行二分搜索。它沒有實現IList，所以prev和next元素有點棘手。我在想，GetViewBetween可能會有幫助（因爲窗口邊界是已知的）。 –

看起來接近我需要的東西。我曾考慮過紅黑樹，並且知道SortedSet，但它沒有「FindClosest」方法。但是，我不知道「GetViewBetween」方法。如果效率很高，我可以用它完成我的任務。我會調查。 –

需要在插入時快速的關聯數組，尋找最近的鍵，並按鍵順序迭代

回答

相關問題