2

我有一个浮点值数组，想要这个值，更重要的是最大四个值的位置。

我最初构建系统是为了遍历数组并以通常的方式找到最大值，方法是将当前位置的值与记录的 max-so-far 进行比较，并在 max-so-far 变化时更新位置变量。这很好用，一个非常简单的 O(n) 算法。后来我才知道，我不仅需要保持最高价值，还需要保持前三四​​名。我扩展了相同的过程并将 max-so-far 复杂化为一个包含四个 max-so-far 的数组，现在代码很难看。

它仍然可以工作并且仍然足够快，因为只在过程中添加了少量的计算。它仍然有效地遍历数组并检查每个值一次。

我在 MATLAB 中使用返回两个数组、排序列表和随附的原始位置列表的排序函数来执行此操作。通过查看前几个值，我得到了我所需要的。我正在将此功能复制到 C# .NET 2.0 程序中。

我知道我可以对 List 对象做类似的事情，并且 List 对象具有内置的排序例程，但我不相信它可以告诉我原始位置，而这些正是我所追求的。

它一直运行良好，但现在我发现自己想要第五个最大值，并且看到重写目前是一个丑陋的 if 语句混乱的 max-so-far 检查器只会加剧丑陋。添加第五个级别会很好并且不会变慢，但我想问问 SO 社区是否有更好的方法。

对整个列表进行排序比我当前的方法需要更多的计算，但我认为这不是问题，因为列表“只有”一两千个浮点数；因此，如果有一个排序例程可以返回原始位置，那将是理想的。

作为背景，该数组是对一千字节波形文件进行傅立叶变换的结果，因此最大值的位置对应于样本数据的峰值频率。我一直对前四名感到满意，但我认为需要真正收集前五名或六名以获得更准确的样本分类。

4

4 回答 4

9

我可以建议您必须编码的替代算法:)

使用大小为 K 的堆，其中 K 表示要保存的顶部元素的数量。将其初始化为原始数组的前 K 个元素。对于所有 N - K 元素遍历数组，并在需要时插入。

proc top_k (array<n>, heap<k>)
heap <- array<1..k-1>
for each (array<k..n-1>) 
  if array[i] > heap.min
     heap.erase(heap.min)
     heap.insert(array[i])
  end if
end for
于 2009-03-06T01:30:18.087 回答
2

您仍然可以使用您的列表想法 - 您放入列表中的元素可以是存储索引和值的结构；但仅按值排序，例如：

class IndexAndValue : IComparable<IndexAndValue>
{
    public int index;
    public double value;

    public int CompareTo(IndexAndValue other)
    {
        return value.CompareTo(other.value);
    }
}

然后您可以将它们粘贴在列表中，同时保留有关索引的信息。如果你只保留列表中最大的 m 个项目，那么你的效率应该是 O(mn)。

于 2009-03-06T01:33:24.100 回答
2

我不知道您当前使用的是哪种算法，但我会建议一个简单的算法。承认您有一个浮点数组f和最大capacity 数字，您可以执行以下操作：

int capacity = 4; // number of floats you want to retrieve
float [] f; // your float list
float [] max_so_far = new float[capacity]; // max so far

// say that the first 'capacity' elements are the biggest, for now
for (int i = 0; i < capacity; i++)
  max_so_far[i] = i;

// for each number not processed
for (int i = capacity; i < f.length; i++)
{
  // find out the smallest 'max so far' number
  int m = 0;
  for (int j = 0; j < capacity; j++)
    if (f[max_so_far[j]] < f[max_so_far[m]])
      m = j;

  // if our current number is bigger than the smallest stored, replace it
  if (f[i] > f[max_so_far[m]])
    max_so_far[m] = i;
}

在算法结束时，您将拥有存储在 中的最大元素的索引max_so_far。

请注意，如果capacity值增长，它将比替代方案稍慢，后者在跟踪初始位置的同时对列表进行排序。请记住，排序需要 O(n log n) 比较，而该算法需要 O(n容量)。

于 2009-03-06T02:04:38.847 回答
1

另一种选择是使用快速选择。快速选择返回列表中第 k 个元素的位置。在获得第 k 个元素的位置和值后，遍历列表并获取值小于/大于第 k 个元素的每个元素。

我在这里找到了快速选择的 ac# 实现：链接文本

优点：

  1. O(n+k) 平均运行时间。

缺点：

  1. 找到的 k 个元素未排序。如果对它们进行排序，则运行时间为 O(n + logk)
  2. 我没有检查过这个，但我认为对于一个非常小的 k 最好的选择是在数组上运行 k ，每次都找到下一个最小/最大的元素。
于 2010-01-07T11:16:26.437 回答