Qual algoritmo a classificação usa?

24

Preciso adicionar um único número inteiro a uma lista que já esteja classificada, de modo que fique no lugar certo. Meu primeiro pensamento foi algo como

(sort (cons newelt list) #'<)

No entanto, dado que listjá está classificado, apenas uma inserção é realmente necessária, o que significa que esta solução pode ser terrivelmente inadequada, dependendo do algoritmo usado por sort.

Então, qual é o algoritmo que sortusa?

Seria melhor fazer algo como o seguinte?

(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
fonte
1
Eu usaria uma pilha binária (por exemplo, heap.el ), se essa fosse uma operação frequente no meu código.
lunaryorn
Vamos Bser inicial já ordenados liste Ae Clistas inicialmente vazias. Divida Bem duas partes B1, B2de comprimentos me mou m+1e m, compare neweltcom o primeiro elemento de B2. Se newelté ≥estender Aa sua direita com B1e substituir Bcom B2, senão estender Cà sua esquerda com B2e substituir Bcom B1. Após O(log n)essas etapas, não resta nada B. Em seguida, Acontém as coisas ≤ newelte Cessas > newelte a concatenação produz a lista classificada estendida. Desculpas por não e-lispgostar muito da linguagem.
Jfbu

Respostas:

26

Se você tiver o código fonte do Emacs instalado, poderá encontrar o código fonte sortcom M-x find-function.

Lá você pode ver que sortrealiza uma classificação de mesclagem. Ele verifica o comprimento da lista, divide a lista pela metade, classifica as partes "frontal" e "traseira" separadamente por meio de recursão e depois mescla as duas.

Quanto à sua implementação ser mais rápida, meça-a! É mais eficiente em teoria (O (n) vs O (n log n)), mas sorttem a vantagem de ser escrito em C, portanto o resultado pode ser de qualquer maneira. (Obviamente, não se esqueça de compilar sua função com bytes).

legoscia
fonte
@ Malabarba Para constar, em que escala de comprimento você testou?
T. Verron
8
Testado 1000 vezes, inserindo um número aleatório em uma lista de 1000 números aleatórios (todos pré-gerados). O método manual foi 6 vezes mais rápido.
Malabarba