12

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

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

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

但是我不明白如何为此目的使用存储桶，因为在我的情况下每个存储桶的大小可能会有所不同。

编辑：在所有讨论之后，我有内/外循环解决方案，但我仍然想用字典消除内循环以获得 O(n) 性能，如果我理解正确，我需要将输入值散列到存储桶索引中. 所以我们需要某种复杂度为 O(1) 的散列函数？任何想法如何做到这一点？

4

2 回答 2

4

桶排序已经是 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 个元素，我怀疑您会看到很多实际性能优势。

于 2011-08-31T15:42:52.670 回答
1

如果您的输入数组代表真实世界的数据（及其模式）并且边界数组很大以在内部循环中一次又一次地迭代它，您可以考虑以下方法：

  • 首先对您的输入数组进行排序。如果您使用真实世界的数据，我建议您考虑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]++;
  }
}
于 2011-09-01T06:50:09.780 回答