Necesito unir dos listas, ordenarlas y eliminar duplicados. ¿Hay una mejor manera de hacer esto?

Question

Tengo dos listas sin clasificar y necesito producir otra lista que esté ordenada y donde todos los elementos sean únicos.

Los elementos pueden aparecer varias veces en ambas listas y no están ordenados originalmente.

Mi función es el siguiente:

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

¿Hay una mejor manera de lograr lo mismo?

llamada de la muestra:

[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

Nuestro amigable vecindario Lisp gurú señaló el remove-duplicates function.

También proporcionó el siguiente fragmento:

(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

creo que lo primero ordenar las dos listas por separado y luego combinarlos con una función que también salta sobre los duplicados. Esto debería ser un poco más rápido ya que requiere un recorrido menos de ambas listas.

P.S .: Dudo que se pueda hacer mucho más rápido, ya que básicamente siempre se necesita al menos un tipo y una combinación. Quizás puedas combinar ambos en una función, pero no me sorprendería si eso no marca una (gran) diferencia.

Answer 3

Parece que necesita utilizar Conjuntos.

Answer 4

Si las listas se ordenan antes de que ellos se fusionan, que se pueden combinar, duplicar, eliminado y ordenados al mismo tiempo. Si están ordenados Y sin duplicados, la función merge/sort/duplicate-remove se vuelve realmente trivial.

De hecho, podría ser mejor cambiar la función de inserción para que realice una inserción ordenada que verifique si hay duplicados. Entonces siempre tiene listas ordenadas que están libres de duplicados, y fusionarlas es una cuestión trivial.

Por otra parte, es posible que prefiera tener una función de inserción rápida a costa de ordenar/eliminar duplicados más adelante.

Answer 5

¿No funcionaría mejor la función de eliminación de duplicados si se aplicara el género antes de quitar los duplicados?

Answer 6

Como señaló Antti, probablemente desee aprovechar REMOVE-DUPLICATES y SORT, aunque probablemente utilizaría una palabra clave (o argumento opcional) para la función de prueba: (defun merge-lists (list-1 list- 2 ordenar-fn clave & ('eql) ...) o (defun merge-listas (lista 1-lista-tipo 2-fn & opcionales (test de prueba # #)' eql) ...)

De esta manera, no tendrá que especificar la función de prueba (utilizada por REMOVE-DUPLICATES para probar si "se consideran duplicados"), a menos que EQL no sea suficiente.