Мне нужно объединить два списка, отсортировать их и удалить дубликаты. Есть лучший способ сделать это?

Question

У меня есть два несортированных списка, и мне нужно создать другой список, который отсортирован и в котором все элементы уникальны.

Элементы могут встречаться несколько раз в обоих списках, и они изначально не отсортированы.

Моя функция выглядит так:

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

Есть ли лучший способ добиться того же?

Пример звонка:

[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

Наш дружественный гуру Lisp указал на функцию remove-duplicates .

Он также предоставил следующий фрагмент:

(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

Если списки отсортированы до их объединения, их можно объединить, удалить дубликаты и отсортировать одновременно. Если они отсортированы И без дубликатов, то функция слияния / сортировки / дублирования-удаления становится действительно тривиальной.

На самом деле, может быть лучше изменить функцию вставки, чтобы она выполняла сортированную вставку, которая проверяет наличие дубликатов. Тогда у вас всегда есть отсортированные списки, которые не содержат дубликатов, и объединить их - тривиальное дело.

Опять же, вы можете предпочесть иметь функцию быстрой вставки за счет последующей сортировки / удаления дубликатов.

Answer 3

Я думаю, что сначала я бы отсортировал два списка по отдельности, а затем объединил их с функцией, которая также пропускает дубликаты. Это должно быть немного быстрее, так как требуется один обход обоих списков.

П.С .: Я сомневаюсь, что это можно сделать намного быстрее, так как в принципе вам всегда нужен хотя бы один вид и одно слияние. Возможно, вы можете объединить оба в одной функции, но я не удивлюсь, если это не будет иметь (большой) разницы.

Answer 4

Как отметил Antti, вы, вероятно, хотите использовать REMOVE-DUPLICATES и SORT, хотя я бы, вероятно, использовал ключевое слово (или необязательный аргумент) для тестовой функции: (defun merge-lists (list-1 list-2 sort-fn & key (test # 'eql)) ...) или же (defun merge-lists (list-1 list-2 sort-fn & необязательный (test # 'eql) ...)

Таким образом, вам не нужно будет указывать функцию теста (используемую REMOVE-DUPLICATES для проверки на "это считается дубликатами"), если только EQL не достаточно хорош.

Answer 5

Разве функция удаления дубликатов не будет работать лучше, если сортировка была применена до удаления дубликатов?

Answer 6

Звучит так, будто вам нужно использовать Наборы.