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

Question

Tengo dos listas sin ordenar 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 originalmente no están ordenados.

Mi función se ve así:

(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 una mejor manera de lograr lo mismo?

Llamada de 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 gurú de Lisp, amigable con el vecindario, señaló la función eliminar duplicados.

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 primero ordenaría las dos listas por separado y luego las fusionaría con una función que también omita los duplicados.Esto debería ser un poco más rápido ya que requiere un recorrido menos de ambas listas.

PD.:Dudo que se pueda hacer mucho más rápido ya que básicamente siempre necesitas al menos una clasificación y una combinación.Quizás puedas combinar ambas en una sola función, pero no me sorprendería que eso no haga una (gran) diferencia.

Answer 3

Si las listas se ordenan antes de fusionarlas, se pueden fusionar, eliminar duplicados y ordenar al mismo tiempo.Si están ordenados Y libres de duplicados, entonces la función fusionar/ordenar/eliminar duplicados 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 busque duplicados.Entonces siempre tendrás listas ordenadas y 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 4

¿No funcionaría mejor la función eliminar duplicados si la clasificación se aplicara antes de eliminar duplicados?

Answer 5

Como señaló Antti, probablemente quieras aprovechar QUITAR-DUPLICATOS y ORDENAR, aunque probablemente usaría una palabra clave (o argumento opcional) para la función de prueba:(Defun Merge-Lists (List-1 List-2 Sort-Fn & Key (Test #'EQL)) ...) o (Defun Merge-Lists (List-1 List-2 Sort-Fn & Opcional (Test #' EQL) ...)

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

Answer 6

Parece que necesitas usar Sets.