向排序列表添加少量元素时如何更快地排序？

Question

我有一个约 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 进行类似合并的排序，将 post 结果。 :-)

Answer 1

此过程将经过的时间从 ~5 毫秒减少到 ~1.2 毫秒：

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。

向排序列表添加少量元素时如何更快地排序？

How to sort faster when adding few elements to sorted list?

sorting

tcl