将几个元素添加到排序列表时如何更快地排序?

问题描述 投票:1回答:1

我有一个~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,将发布结果。 :-)

sorting tcl
1个回答
2
投票

这个过程减少了从大约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 1lindex $insert 1

© www.soinside.com 2019 - 2024. All rights reserved.