Мне нужно объединить два списка, отсортировать их и удалить дубликаты.Есть лучший способ сделать это?
Вопрос
У меня есть два несортированных списка, и мне нужно создать еще один отсортированный список, в котором все элементы уникальны.
Элементы могут встречаться несколько раз в обоих списках, и изначально они не отсортированы.
Моя функция выглядит так:
(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)
Решение
Наш дружелюбный гуру Lisp отметил функция удаления дубликатов.
Он также предоставил следующий фрагмент:
(defun merge-lists (list-a list-b sort-fn test-fn)
(sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn))
Другие советы
Я думаю, что сначала отсортировал бы два списка отдельно, а затем объединил бы их с помощью функции, которая также пропускает дубликаты.Это должно быть немного быстрее, поскольку требует на один обход обоих списков меньше.
P.S.:Я сомневаюсь, что это можно сделать намного быстрее, поскольку вам всегда нужна хотя бы одна сортировка и одно слияние.Возможно, вы можете объединить обе функции в одной функции, но я не удивлюсь, если это не будет иметь (большого) значения.
Если списки отсортированы перед их объединением, их можно объединить, удалить дубликаты и отсортировать одновременно.Если они отсортированы И не содержат дубликатов, то функция слияния/сортировки/удаления дубликатов становится действительно тривиальной.
На самом деле, возможно, было бы лучше изменить функцию вставки, чтобы она выполняла отсортированную вставку, проверяющую наличие дубликатов.Тогда у вас всегда будут отсортированные списки, в которых нет дубликатов, и их объединение — тривиальная задача.
Опять же, вы можете предпочесть иметь функцию быстрой вставки за счет последующей сортировки/удаления дубликатов.
Не будет ли функция удаления дубликатов работать лучше, если сортировка будет применена до удаления дубликатов?
Как отметил Антти, вы, вероятно, захотите использовать 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 недостаточно хорош.
Похоже, вам нужно использовать Sets.