將一組物品分類到桶中的最有效方法是什麼？

Question

我有一個任意的散列數組，散列元素是一個整數（稱之爲'id'）。我想將這些散列排序爲多個桶（數組中的常量），其中每個桶都是「ids」的任意範圍（例如1-10,15-20,20-30）。什麼是最好的分類策略來做到這一點？有沒有可能沒有嵌套循環？

Answer 1

如果桶的數量很少，那麼使用嵌套循環可能會更好。哈希上的外部循環，以及桶上的內部循環。 O(n*m)。

如果哈希的數量，和水桶的數量很大，您可以：

hashes = sort(hashes) 
buckets = sort(buckets) # sort by lower-bound of bucket 
i = 0 

foreach (hash in hashes) { 
    while (buckets[i].lower_bound > hash) { 
    i = i + 1 
    } 
    bucket[i].add(hash) 
} 

的基本遍歷哈希將其添加到當前桶並在需要時推進到下一桶。 O（n * log（n）+ m * log（m））

Answer 2

如果哈希值質量好，它們將呈現均勻分佈，因此您可以使用均勻分佈的桶來一次性分割集合。

如果您還希望在桶中排序的哈希值，請在桶中的所有內容之後使用正常的排序算法。然而，這將是一個不尋常的哈希使用。 （如果你不是試圖在桶內排序，那麼「排序」這個詞是不恰當的，你真正想要的是分區。）

Answer 3

你沒有提到語言/平臺，但爲了高效擊鍵（C＃）：

 var histogram = new[] { 0, 10, 15, 20, 30, 40 }; 
     var values = new[] { 12, 14, 5, 6, 7, 1, 34, 26, 17 }; 
     var bars = values.GroupBy(v => histogram.First(b => v < b));