在C#中计算数组频率分布的最快方法是什么？

Question

我只是想知道这个计算的最佳方法是什么.假设我有一个值的输入数组和边界数组 - 我想计算/ bucketize边界数组中每个段的频率分布.

使用桶搜索是不是一个好主意？

实际上我发现这个问题用.Net/C#计算集合的频率分布

但是我不明白如何使用桶来达到这个目的,因为每个桶的大小在我的情况下可能会有所不同.

编辑:在所有的讨论之后我有内部/外部循环解决方案,但是我仍然希望在这种情况下消除带有字典的内部循环以获得O(n)性能,如果我理解正确的话我需要将输入值散列到存储桶索引中.所以我们需要某种具有O(1)复杂度的哈希函数？有什么想法怎么做？

Answer 1

桶排序已经是 O(n^2) 最坏情况，所以我在这里只做一个简单的内/外循环。由于您的存储桶数组必然比输入数组短，因此请将其保留在内部循环中。由于您使用的是自定义存储桶大小，因此实际上没有任何数学技巧可以消除该内部循环。

int[] freq = new int[buckets.length - 1];
foreach(int d in input)
{
    for(int i = 0; i < buckets.length - 1; i++)
    {
         if(d >= buckets[i] && d < buckets[i+1])
         {
             freq[i]++;
             break;
         }
    }
}

这也是 O(n^2) 最坏情况，但你无法超越代码的简单性。在优化成为真正的问题之前，我不会担心它。如果您有更大的存储桶数组，则可以使用某种二分搜索。但是，由于频率分布通常小于 100 个元素，我怀疑您是否会看到很多现实世界的性能优势。