Quel algorithme utilise le tri?

24

J'ai besoin d'ajouter un seul entier à une liste qui est déjà triée, de telle sorte qu'elle aille au bon endroit. Ma première pensée était quelque chose comme

(sort (cons newelt list) #'<)

Cependant, étant donné qu'il listest déjà trié, une seule insertion est vraiment nécessaire, ce qui signifie que cette solution pourrait être horriblement inappropriée en fonction de l'algorithme utilisé par sort.

Alors, quel est l'algorithme qui sortutilise?

Serais-je mieux de faire quelque chose comme ce qui suit?

(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
la source
1
J'utiliserais un tas binaire (par exemple heap.el ), si c'était une opération fréquente dans mon code.
lunaryorn
Soit des listes Binitiales déjà triées listet Aet Cinitialement vides. Diviser Ben deux parties B1, B2de longueurs met mou m+1et m, comparer neweltau premier élément de B2. Si neweltest - ≥étendre Aà sa droite avec B1et remplacer Bavec B2, étendre le reste Cà sa gauche avec B2et remplacer Bpar B1. Après de O(log n)telles étapes, rien n'est laissé B. AContient ensuite les choses ≤ newelt, et Ccelles-ci > newelt, et la concaténation produit la liste triée étendue. Toutes mes excuses pour un e-lisplangage peu similaire.
jfbu

Réponses:

26

Si le code source d'Emacs est installé, vous pouvez trouver le code source de sortavec M-x find-function.

Vous pouvez y voir qui sorteffectue un tri par fusion. Il vérifie la longueur de la liste, divise la liste en deux, trie les parties "avant" et "arrière" séparément par récursivité, puis fusionne les deux.

Quant à savoir si votre mise en œuvre serait plus rapide - mesurez-la! Il est plus efficace en théorie (O (n) vs O (n log n)), mais sorta l'avantage d'être écrit en C, donc le résultat peut aller dans les deux sens. (Bien sûr, n'oubliez pas de compiler vos fonctions en octets.)

legoscia
la source
@Malabarba Pour mémoire, sur quelle échelle de longueurs l'avez-vous testé?
T. Verron
8
Testé 1000 fois en insérant un nombre aléatoire dans une liste de 1000 nombres aléatoires (tous prégénérés). La méthode manuelle était 6 fois plus rapide.
Malabarba