Мне нужно добавить одно целое число в список, который уже отсортирован, так что он идет в нужном месте. Моя первая мысль была что-то вроде
(sort (cons newelt list) #'<)
Однако, учитывая, что listэто уже отсортировано, действительно требуется только одна вставка, что означает, что это решение может быть ужасно непригодным в зависимости от используемого алгоритма sort.
Итак, какой алгоритм sortиспользует?
Буду ли я лучше делать что-то вроде следующего?
(let ((tail list))
;; The first element is never less-than
(while (and tail (< newelt (cadr tail)))
(setq tail (cdr tail)))
(setcdr tail (cons newelt (cdr tail)))
list)
elisp
performance
emacs-internals
Malabarba
источник
источник
Bбудут изначально уже отсортированныеlistиAиCизначально пустые списки. РазделитеBна две частиB1,B2длиныmиmилиm+1иm, сравнитеneweltс первым элементомB2. Еслиneweltэто≥расширениеAвправо с помощьюB1и заменитьBсB2, в противном случае расширитьCего слева сB2и заменитьBнаB1. ПослеO(log n)таких шагов ничего не осталосьB. ЗатемAсодержит вещи≤ newelt, иCте> newelt, и конкатенация создает расширенный отсортированный список. Извиняюсь за не оченьe-lispпохожий язык.Ответы:
Если у вас установлен исходный код Emacs, вы можете найти исходный код для
sortсM-x find-function.Там вы можете увидеть, что
sortвыполняет сортировку слиянием. Он проверяет длину списка, разбивает список на две части, сортирует «переднюю» и «заднюю» части по рекурсии по отдельности, а затем объединяет их.Что касается того, будет ли ваша реализация быстрее - измерьте это! Он более эффективен в теории (O (n) по сравнению с O (n log n)), но
sortимеет преимущество в том, что он написан на C, поэтому результат может пойти в любую сторону. (Конечно, не забудьте побайтно скомпилировать вашу функцию.)источник