有效地計算記錄列表中的項目

Question

給定一個記錄列表，我試圖計算每個作者寫入的記錄數量。顯而易見的方法是使用映射，其中鍵是作者的名字，值是遞增的值。但是有沒有更有效的方法來做到這一點，而不是每次迭代都做一次查找？

如果我事先知道作者，我可以爲每個作者創建變量並在不查找的情況下增加它們，然後在完成讀取輸入後最終創建地圖。但是，我只知道數據中的一些作者。

在此先感謝。

Answer 1

基於作者姓名統計圖的解決方案是一個很好的解決方案（如果使用HashMap，它的整體平均時間複雜度爲O(n)）。

如果我是你，我會使用這種方法，直到我可以證明它不適合（太慢，使用太多內存等），只有這樣我纔會嘗試用解決問題的東西來替代它。很有可能，那一天永遠不會到來。

Answer 2

使用Java HashMap進行查找的平均情況將是O(1)，這意味着它不會大幅增加您的運行時間。

除非你是真的試圖擠壓這一切，你可能只是過度優化。

Answer 3

如果作者數量相對較少，與記錄總數相比，在這種情況下，散列查找將是最有效的技術。

如果記錄已經排序（或者您有某種btree索引，也是排序結構），那麼可能會出現更多情感算法。

Answer 4

您可能會發現TObjectIntHashMap比HashMap更高效，但兩者都會相當有效。您應該能夠在幾毫秒內掃描100K記錄。如果速度不夠快，您可以在添加/更新/刪除記錄時保留一個計數圖，以便查看此記錄。