在大数组中查找第N个有序元素
13793 为本文评分：
暂无评分
在大数组中查找第N个有序元素
匿名作者 2014年7月17日，星期四
处理大型数组时，一个常见任务是查找有序数组中的第N个数组值。这对于查找第N个最小或最大像素值，以及对浮点数据样本进行统计分析（例如查找95%百分位数或类似操作）非常有用。在IDL中查找有序序列中第N个值的最简短代码实际上只需2行。以下是实现此功能的简短函数：
;+
; 返回有序序列中的第N个数字
;-
function ordinal_1, array, N
compile_opt idl2,logical_predicate
s = sort(array)
return, array[s[N]]
end
然而，由于排序是一项计算密集型操作，该函数运行速度相当慢，特别是当数组变大时。我进行了以下时间测试。
IDL> a = total(read_image(filepath('ohare.jpg',subdir=['examples','data'])),1)
IDL> tic & x = ordinal_1(a, 123456) & toc & print, x
% Time elapsed: 3.7200000 seconds.
150.000
在我的测试中，查找第123456个最小的数组元素耗时3.72秒。IDL中的MEDIAN函数通过不完全排序返回有序序列的中心元素。它比排序快得多，因为它不需要跟踪所有元素及其有序位置，只关心有序数组中第N/2个元素。在以下示例中，通过反复调用MEDIAN函数并每次迭代将数组大小减半，来查找有序序列中的第N个元素。这段代码比上面的代码长得多，但最终运行速度更快：
;+
; 返回有序序列中的第N个数字。
;
; 使用重复中值法。
;-
function ordinal_2, array, N
compile_opt idl2,logical_predicate
na = n_elements(array)
type =size(array, /type)
target_index = N
tmp = arg_present(array) ? array : temporary(array)
ntmp = na
while ntmp ne target_index do begin
ntmp = n_elements(tmp)
val = fix(median(tmp), type=type)
if target_index gt ntmp/2 then begin
tmp = tmp[where(tmp gt val, count)]
target_index -= ntmp-count
endif else if target_index lt ntmp+1/2 then begin
tmp = tmp[where(tmp lt val, count)]
endif else break
if target_index lt 0 then break
if target_index ge count then break
if target_index eq 0 then begin
val = min(tmp)
break
endif
if target_index eq count-1 then begin
val = max(tmp)
break
endif
endwhile
return, val
end
对这段代码进行与简短代码相同的时间测试：
IDL> tic & x = ordinal_2(a, 123456) & toc & print, x
% Time elapsed: 0.57999992 seconds.
150.000
由此可见，时间节省非常显著，从3.72秒减少到0.58秒。随着数组增大，节省的时间可能更加显著。此函数适用于浮点型和整型数组等数值数据类型。