如何从数组中找到前几个值？

Question

我有一个浮点值数组,想要值,更重要的是想要最多四个值的位置.

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

它仍然有效并且仍然足够快,因为只有少量的计算被添加到过程中.它仍然有效地遍历数组并检查每个值一次.

我在MATLAB中使用sort函数执行此操作,该函数返回两个数组,排序列表和随附的原始位置列表.通过查看前几个值,我确切地知道我需要什么.我正在将此功能复制到C#.NET 2.0程序中.

我知道我可以用List对象做类似的事情,并且List对象有一个内置的排序例程,但我不相信它能告诉我原来的位置,而那些真的是我追求的.

它一直运作良好,但现在我发现自己想要第五个最大值并且看到重写最大的远程检查器,这是目前丑陋的if语句只会使丑陋复杂化.它会工作得很好并且添加第五级也不会慢,但我想询问SO社区是否有更好的方法.

对整个列表进行排序需要比我当前的方法多得多的计算,但我不认为这会是一个问题,因为列表"只有"一两千个浮点数; 因此,如果存在可以回馈原始位置的排序例程,那将是理想的.

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

Answer 1

我可以建议一个替代算法,你必须编码:)

使用大小为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