c#中计算数组频率分布的最快方法是什么?

Question

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

使用桶搜索是好主意吗?

实际上我发现了这个问题计算一个集合的频率分布与。net/c#

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

编辑:在所有讨论之后，我有了内部/外部循环的解决方案，但我仍然想用Dictionary消除内部循环，以获得O(n)性能，在这种情况下，如果我理解正确的话，我需要将输入值散列到桶索引中。所以我们需要某种复杂度为0(1)的哈希函数?有什么办法吗?

Answer 1

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

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个元素，我怀疑你会看到很多实际的性能优势。

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]++;
  }
}