Ich brauche zwei Listen beizutreten, sortieren sie und Duplikate entfernen. Gibt es einen besseren Weg, dies zu tun?

Question

Ich habe zwei unsortierten Listen und ich brauche eine andere Liste zu erzeugen, die sortiert und in dem alle Elemente sind einzigartig.

Die Elemente können mehrmals in beiden Listen auf, und sie sind ursprünglich unsortiert.

Meine Funktion sieht wie folgt aus:

(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))))

Gibt es einen besseren Weg, um das gleiche zu erreichen?

Beispielaufruf:

[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

zeigte Unsere Nachbarschaft freundlich Lisp-Guru der entfernen-Duplikate Funktion .

Er stellte auch das folgende Snippet:

(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

Ich glaube, ich würde zuerst die beiden Listen separat sortieren und sie dann mit einer Funktion zusammenführen, die auch über Duplikate überspringen. Dies sollte ein wenig schneller sein, da es eine erfordert weniger Traversal von beiden Listen.

P. S .: Ich bezweifle, kann es viel schneller durchgeführt werden, wie Sie grundsätzlich immer mindestens eine Art und eine Zusammenführung benötigen. Vielleicht können Sie sowohl in einer Funktion verbinden, aber ich wäre nicht überrascht, wenn das nicht einen (großen) Unterschied machen.

Answer 3

Wenn die Listen sortiert werden, bevor Sie kombiniere sie, können sie zusammengefügt werden, vervielfältigen befreites und zugleich sortiert. Wenn sie sortiert und doppelte frei, dann die Zusammenführung / Art / duplizieren zu entfernende Funktion wird wirklich trivial.

In der Tat könnte es besser sein, Ihre Insert-Funktion zu ändern, so dass es eine sortierte Einfügung durchführt, die nach Dubletten überprüft. Dann haben Sie immer sortierte Listen, die frei von Dubletten sind, und ihre Zusammenlegung ist eine triviale Angelegenheit.

Dann wieder, Sie könnten es vorziehen, eine schnelle Insert-Funktion auf Kosten der Sortierung / Entfernen von Duplikaten auf später haben.

Answer 4

Wäre nicht die remove-Duplikate funktionieren besser funktionieren, wenn die Sortierung vor der remove-Duplikate angewendet wurde?

Answer 5

Wie Antti wies darauf hin, Sie wollen wahrscheinlich REMOVE-Duplikate und SORT nutzen, obwohl ich wahrscheinlich ein Schlüsselwort (oder optionales Argument) für die Testfunktion verwenden würde: (Defun merge-Listen (list-1-Liste-2 sort-fn & Taste (Test # 'eql))   ...) oder (Defun merge-Listen (list-1-Liste-2 sort-fn & optional (Test # 'eql)   ...)

Auf diese Weise werden Sie nicht die Testfunktion (durch REMOVE-DUPLICATES verwendet testen für „ist diese als Duplikate“) angeben müssen, es sei denn, EQL nicht gut genug ist.

Answer 6

Klingt wie Sie mit Sets sein müssen.