Je dois rejoindre deux listes, les trier et supprimer les doublons. Y a-t-il une meilleure manière de faire cela?

Question

J'ai deux listes non triées et je dois produire une autre liste triée et dans laquelle tous les éléments sont uniques.

Les éléments peuvent apparaître plusieurs fois dans les deux listes et ils ne sont initialement pas triés.

Ma fonction ressemble à ceci:

(defun merge-lists (list-a list-b sort-fn)
    "Merges two lists of (x, y) coordinates sorting them and removing dupes"
    (let   ((prev nil))
        (remove-if
            (lambda (point)
                (let   ((ret-val (equal point prev)))
                    (setf prev point)
                    ret-val))
            (sort
                (merge 'list list-a list-b sort-fn) ;'
                 sort-fn))))

Existe-t-il un meilleur moyen de réaliser la même chose?

Exemple d'appel:

[CL]> (merge-lists '(9 8 4 8 9 7 2) '(1 7 3 9 2 6) #'>)
  ==> (9 8 7 6 4 3 2 1)

Answer 1

Notre gourou Lisp, responsable de l'environnement, a indiqué la fonction remove-duplicates .

Il a également fourni l'extrait suivant:

(defun merge-lists (list-a list-b sort-fn test-fn)
    (sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn))

Answer 2

Je pense que je voudrais d'abord trier les deux listes séparément, puis les fusionner avec une fonction qui ignore également les doublons. Cela devrait être un peu plus rapide car il faut parcourir les deux listes de moins.

P.S .: Je doute que cela puisse être fait beaucoup plus rapidement car vous avez toujours besoin d'au moins une sorte et d'une fusion. Peut-être que vous pouvez combiner les deux dans une seule fonction, mais je ne serais pas surpris si cela ne fait pas une (grande) différence.

Answer 3

Si les listes sont triées avant de les fusionner, elles peuvent être fusionnées, supprimées en double et triées en même temps. Si elles sont triées ET exemptes de doublons, la fonction de fusion / tri / duplication-supprime devient vraiment triviale.

En fait, il peut être préférable de modifier votre fonction d’insertion afin qu’elle effectue une insertion triée qui recherche les doublons. Ensuite, vous avez toujours des listes triées qui ne contiennent pas de doublons, et leur fusion est une affaire banale.

Là encore, vous préférerez peut-être une fonction d’insertion rapide au lieu de trier / supprimer les doublons ultérieurement.

Answer 4

La fonction remove-duplicates ne fonctionnerait-elle pas mieux si le tri était appliqué avant les remove-duplicates?

Answer 5

Comme Antti l'a fait remarquer, vous souhaiterez probablement tirer parti de REMOVE-DUPLICATES et SORT, bien que j'utiliserais probablement un mot clé (ou un argument optionnel) pour la fonction de test: (defun merge-lists (liste-1 liste-2 tri-fn & clé (test # 'eql)))   ...) ou (defun merge-lists (list-1 list-2 sort-fn & optionnel (test # 'eql))   ...)

De cette façon, vous n'avez pas besoin de spécifier la fonction de test (utilisée par REMOVE-DUPLICATES pour tester "est-ce que ces doublons sont considérés comme"), à moins que EQL ne soit pas assez bon.

Answer 6

On dirait que vous devez utiliser des sets.