algorithm - tuplas - listas python

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

¿Hay una mejor manera de lograr lo mismo?

Ejemplo de llamada:

[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

¿No funcionaría mejor la función de eliminación de duplicados si el ordenamiento se aplicara antes que los duplicados eliminados?

Answer 2

Creo que primero ordenaría las dos listas por separado y luego las fusionaría con una función que también omite 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 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

Nuestro amigable Lisp gurú del barrio señaló la función de 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 4

Parece que necesitas usar Sets.

Answer 5

Si las listas se ordenan antes de fusionarlas, se pueden combinar, eliminar duplicadas y ordenar 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 su función de inserción para que realice una inserción ordenada que compruebe 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 6

Como Antti señaló, es probable que desee aprovechar REMOVE-DUPLICATES y SORT, 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 & optional (test #'' eql) ...)

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