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

Question

我在想，对于那个计算，最好的方法是什么。假设我有一个值的输入数组和一个边界数组-我希望为边界数组中的每个段计算/分桶频率分布。

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

实际上，我发现了这个问题Calculating frequency distribution of a collection with .Net/C#

但是我不知道如何使用桶来实现，因为在我的情况下每个桶的大小可能不同。

编辑： 经过所有讨论，我有内部/外部循环的解决方案，但我仍然希望使用字典消除内部循环，以便在这种情况下获得O（n）性能，如果我理解正确的话，需要将输入值哈希到桶索引中。所以我们需要一些具有O（1）复杂度的哈希函数？您有什么想法如何做到这一点？

- Andrey

---

你能更好地描述一下边界数组吗？各个边界之间是否有关联（例如它们是否顺序排列），还是它们的大小和位置完全随机？我假设边界数组完全覆盖了可能值的范围，这是正确的吗？另外，我假设没有重叠，对吗？ - Mike Dinescu

在“大O符号”或小代码的意义上，哪种方法是最快的？一个简单的方法是编写一个名为Func<MyData,int>的函数，并将其与Linqs .GroupBy一起使用，将其分组成“桶”——但可能有更快的计算方法来完成这个任务。 - Random Dev

是的，你说得对。边界值在数值上单调递增。它们没有重叠并覆盖了可能值的范围。例如：0、10、50、100、120。 - Andrey

最快的意思是大O符号，没有Linqs。 GroupBy，只有计算方法。 - Andrey

一种简单但不太快的解决方案是二分查找。 - CodesInChaos

这些值是什么类型？如果它们是 .NET 基元类型（int、double、string、decimal、datetime 等），那么它们已经具有良好的 O(1) 哈希函数，您根本不需要担心它们。只需使用 Dictionary<TKey, TValue> 即可解决问题。然而，我想指出的是，二分查找非常快，可以与哈希函数解决方案相媲美。最好测试一下在您的情况下哪个更快。 - Vilx-

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个元素，我认为您不太可能看到实际的性能提升。

- drharris

---

你认为像Java中所展示的BucketizedHashtable实现怎么样？或者在执行开始时进行数组排序，这样做有意义吗？ - Jevgenij Nekrasov

使用 Dictionary<sometype, int> 来消除内部循环，以获得摊销的 O(n) 性能。 - Hans Passant

@Hans 你是什么意思？我真的不太明白 :( - Andrey

@Jevgenij - 桶哈希表通常使用标准桶大小，据我所知。这很有效，因为您不需要遍历桶数组，而是使用一个函数输入值并输出桶编号。如果转换函数运行时间为O(1)，则可以实现O(n)性能，因为它消除了任何内部循环的要求。这类似于@Hans所说的使用Dictionary<type, int>，但它需要一种将输入值哈希到桶索引中的方法。至于数组排序，您只会增加算法复杂度。 - drharris

内部循环可以被二分查找替换，从而获得总体O(n*log(m))的时间复杂度，其中n为输入计数，m为桶计数。 - Vilx-

我提到了二分查找选项，但除非您的桶数组非常长，否则您不会看到任何真实世界的性能优势，甚至可能会看到更差的性能。 二分查找很好，但它有开销，并且在循环中进行数千次比仅迭代内部循环要糟糕得多，特别是对于较小的数组。 但是，如果OP想要走这条路线，这是一个选项。 - drharris

Answer 2

如果您的输入数组代表真实世界的数据（具有其模式），并且边界数组太大，无法在内部循环中再次迭代，则可以考虑以下方法：

• 首先对输入数组进行排序。如果您使用真实世界的数据，我建议考虑使用Timsort - Wiki。它为可以在真实世界数据中看到的模式提供了非常好的性能保证。

• 遍历排序后的数组，并将其与边界数组中的第一个值进行比较：

  • 如果输入数组中的值小于边界，则增加此边界的频率计数器
  • 如果输入数组中的值大于边界，则转到边界数组中的下一个值，并增加新边界的计数器。

在代码中，它可能看起来像这样：

Timsort(myArray);
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>()

for (int i = 0; i<myArray.Lenght; i++) {
  if (myArray[i]<boundaries[boundPos]) { 
     boundaries[boubdPos]++;
  }
  else {
    boundPos++;
    boundaries[boubdPos]++;
  }
}

- Andrey Taptunov

---

边界用值数组表示。但是复杂度呢？据我所知，Timsort最坏情况下为O(nlogn) + O(n)的循环。我认为使用二分搜索的内/外循环应该会更好吧？ - Andrey

不太对。如果中间有一个“空”桶，那么这种方法将失败。也就是说，在排序数组中有两个相邻的输入值，但它们进入的桶并不相邻。但这可以修复。总的来说，这是一个非常好的想法。根据数据的不同，甚至可能可以使用基数排序，其时间复杂度为O(n)，尽管可能需要大量数据才能使其值得。但总体运行时间将是干净的O(n)。 - Vilx-

抱歉将此文本发布为答案，它应该是一条评论。 - Vilx-

@Vilx-，同意并感谢您的纠正。我没有考虑到这种情况。 - Andrey Taptunov