sorting - 向排序列表添加少量元素时如何更快地排序?
问题描述
我有一个约 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
and lindex $insert 1
。
推荐阅读
- django - 如何在 django 中将列表项插入数据库?
- python - 在已定义 python 函数的 *args 中索引数组列表
- android - 安卓包错误:
标签不是有效的 Android 包名称:'[ios:com.appname.appname, android:com.appname.tab] - r - 将脚本定义路径添加到 .Rprofile
- json - KotlinX 内置类的序列化
- ios - 不正确的 RealityKit generateConvex(from mesh: ) collider
- python - 将 pandas 中的 Topic-name 和 Description 转换为 Topic-Name、单词和频率
- python - 使用 pandas rd.sheet_name 显示所有工作表名称不起作用
- python - 我可以根据模型类中的布尔值更改外键中的列表吗?
- python - Python 检查互联网连接以进行抓取