Как быстрее сортировать при добавлении нескольких элементов в отсортированный список?
У меня есть отсортированный список из ~ 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, выполняющую сортировку слиянием, я опубликую результаты. :-)
Ответы 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.
Команда
lsortкаждый раз выполняет полную сортировку слиянием; такие вставки — лучший выбор, иlsearch -bisect— это инструмент для этой цели. Увы, вставка действительный по-прежнему сопряжена с реальными затратами, потому что списки Tcl — это простые массивы под обложкой, и поэтому для вставки требуется тяжелая копия…