Eu preciso juntar duas listas, classificá-los e remover duplicatas. Existe uma maneira melhor de fazer isso? - algoritmo, classificação, lisp, lista

Eu tenho duas listas não classificadas e preciso produzir outra lista que seja classificada e onde todos os elementos sejam exclusivos.

Os elementos podem ocorrer várias vezes em ambas as listas e eles são originalmente não classificados.

Minha função é assim:

(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 uma maneira melhor de conseguir o mesmo?

Chamada de amostra:

[CL]> (merge-lists "(9 8 4 8 9 7 2) "(1 7 3 9 2 6) #">)
==> (9 8 7 6 4 3 2 1)

Respostas:

11 para resposta № 1

Nosso guru Lisp amigo da vizinhança apontou o função remover duplicatas.

Ele também forneceu o seguinte trecho:

(defun merge-lists (list-a list-b sort-fn test-fn)
(sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn))

---

1 para resposta № 2

Acho que primeiro classificaria as duas listas separadamente e depois as mesclaria com uma função que também ignora as duplicatas. Isso deve ser um pouco mais rápido, pois requer uma passagem a menos de ambas as listas.

P.S.: Eu duvido que isso possa ser feito muito mais rápido, pois basicamente você sempre precisa de pelo menos um tipo e um merge. Talvez você possa combinar os dois em uma função, mas eu não ficaria surpreso se isso não fizesse uma grande diferença.

---

1 para resposta № 3

Se as listas estiverem classificadas antes de você mesclá-las,eles podem ser mesclados, removidos e classificados ao mesmo tempo. Se eles são classificados e livres de duplicação, a função de mesclagem / classificação / remoção de duplicatas se torna realmente trivial.

Na verdade, pode ser melhor alterar sua inserçãofunção para que execute uma inserção ordenada que verifique se há duplicatas. Então você sempre classificou listas que estão livres de duplicatas, e mesclá-las é uma questão trivial.

Então, novamente, você pode preferir ter uma função de inserção rápida ao custo de classificar / remover duplicatas mais tarde.

---

0 para a resposta № 4

A função remover duplicatas funcionaria melhor se a classificação fosse aplicada antes da remoção de duplicatas?

---

0 para a resposta № 5

Como Antti apontou, você provavelmente querAproveitar REMOVE-DUPLICATES e SORT, embora eu provavelmente usaria uma palavra-chave (ou argumento opcional) para a função de teste: (defun merge-lists (lista-1 lista-2, sort-fn e chave (teste # "eql)) ...) ou (defun merge-lists (lista-1 lista-2, sort-fn e opcional (teste # "eql) ...)

Desta forma, você não terá que especificar a função de teste (usada por REMOVE-DUPLICATES para testar "é considerada duplicada"), a menos que o EQL não seja bom o suficiente.

---

-2 para resposta № 6

Parece que você precisa estar usando Sets.

---