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

StackOverflow https://stackoverflow.com/questions/100048

  •  01-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top