我有一个~10'000个元素的排序列表,其中我在弹出第一个元素之间插入一些元素(1-10)。测量显示排序过程需要几毫秒(约5),大概是因为lsort
每次都从头开始。它现在占用了大部分帧时间,所以我需要对它做些什么。
是否有一些技巧可以将一个大的排序列表与一个小的排序列表合并,并提高效率?
用于解释上下文的代码:
while {true} {
set work [lindex $frontier 0]
set frontier [lreplace $frontier 0 0]
if {[done $work]} break;
set more_work [do work]; # about 1-10 elements, distribution is generally hard to predict
lappend frontier {*}$more_work
set frontier [lsort $frontier]; # when frontier is 10'000 elements time to sort is ~5ms
}
尽力实现一个类似于类似排序的Tcl proc,将发布结果。 :-)
这个过程减少了从大约5ms到大约1.2ms的时间:
proc merge_insert {sorted1 sorted2} {
set res {}
set prevloc 0
foreach insert $sorted2 {
# find location of next element to insert
set nextloc [lsearch -bisect -integer -index 1 $sorted1 [lindex $insert 1]]
# append up to next loc
lappend res {*}[lrange $sorted1 $prevloc $nextloc] $insert
# put read location just beyond the inserted element
set prevloc [+ 1 $nextloc]
}
# append whatever tail is left
lappend res {*}[lrange $sorted1 $prevloc end]
return $res
}
排序的属性是每个有序元素中第二个元素的整数,因此是-integer index 1
和lindex $insert 1
。