Ho bisogno di unire due liste, una sorta di loro e rimuovere i duplicati.C'è un modo migliore per fare questo?

Question

Ho due elenchi non ordinati e ho bisogno di produrre un altro elenco, che è ordinata e in cui tutti gli elementi sono unici.

Gli elementi possono verificarsi più volte in entrambe le liste e sono originariamente ordinato.

La mia funzione simile a questo:

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

C'è un modo migliore per ottenere lo stesso?

Chiamata di esempio:

[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

Il nostro quartiere amichevole Lisp guru ha sottolineato il rimuovere duplicati funzione.

Egli ha anche fornito il seguente frammento:

(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

Penso che prima di ordinare i due elenchi separatamente e poi unirli con una funzione che passa anche più di duplicati.Questo dovrebbe essere un po ' più veloce, in quanto richiede meno di attraversamento di entrambe le liste.

P. S.:Dubito che possa essere fatto molto più velocemente di come si fondamentalmente sempre bisogno di almeno un tipo e uno di tipo merge.Forse si possono combinare in una sola funzione, ma io non sarei sorpreso se non un (grande) differenza.

Answer 3

Se le liste sono ordinate prima di procedere all'unione, possono essere uniti, duplicati rimossi e ordinati allo stesso tempo.Se sono ordinate E senza duplicati, quindi l'unione di ordinamento//duplica-rimuovere la funzione diventa davvero banale.

In realtà, potrebbe essere meglio per cambiare la tua funzione di inserimento in modo che esegue l'ordinamento di una inserzione che controlla la presenza di duplicati.Quindi si hanno sempre gli elenchi ordinati che sono liberi di duplicati, e la loro unione è una questione di poco conto.

Poi di nuovo, si potrebbe preferire di avere un veloce funzione di inserimento al costo di ordinamento/rimozione di duplicati in seguito.

Answer 4

Non rimuovere duplicati funzione di funzionare meglio se l'ordinamento è stato applicato prima di rimuovere duplicati?

Answer 5

Come Antti ha sottolineato, probabilmente si vuole sfruttare RIMUOVERE DUPLICATI e di ORDINAMENTO, anche se probabilmente sarei utilizzare una parola chiave (o argomento opzionale) per la funzione di test:(defun unione-list (elenco 1 elenco 2 ordinamento-fn &key (test #'eql)) ...) o (defun unione-list (elenco 1 elenco 2 ordinamento-fn &opzionale (test #'eql) ...)

In questo modo, non è necessario specificare la funzione di test (utilizzato da RIMUOVERE DUPLICATI per il test di "questi sono considerati duplicati"), a meno che non EQL non è abbastanza buono.

Answer 6

Suona come avete bisogno di essere utilizzando Set.