效率：使用什麼數據結構...？

Question

我正在處理一個非常大的數據集。本質上，我將處理數百萬條記錄並將值存儲到數據集中。

每次我存儲一個值時，我必須首先檢查以確保該值不在數據結構中。如果該值在數據結構中，我必須更新（或刪除/添加）記錄以更新計數。

數據集中有重複，我不想使用錯誤的數據結構，並獲得O（n）的速度，因爲我希望能夠在一夜之間運行並進入早晨完成！

有什麼建議嗎？

Answer 1

正如其他人所說，一個哈希表可能正確的答案，但哈希表並不十分節省空間，所以如果你的地步，你可能會耗盡你的記憶力，你應該考慮一個有序鍵值數組和一個並行排序值數組。基本上，如果您可以預先訪問整個密鑰列表，請創建一個這樣的數組並對其進行排序。然後創建一個平行的值數組。每次您需要存儲某些內容時，只需執行二進制搜索（O（log N））即可找到鍵陣列中的索引，然後更新值數組中的相應索引。這比散列表的速度效率更低，但將保證幾乎沒有空間開銷。

Answer 2

這聽起來像你想hash table，結合（可能）列表或某些特定的結構。對我而言，聽起來像是database。

Answer 3

使用哈希表

Answer 4

你可以嘗試一個二叉樹。 log_2（1,000,000）約爲20.如果您不知道所有密鑰會提前提供什麼，這可能會更好。