두 개의 목록을 결합하고 정렬하고 중복 항목을 제거해야 합니다.이를 수행하는 더 좋은 방법이 있습니까?
문제
두 개의 정렬되지 않은 목록이 있고 정렬되어 있고 모든 요소가 고유한 또 다른 목록을 생성해야 합니다.
요소는 두 목록 모두에서 여러 번 나타날 수 있으며 원래는 정렬되지 않았습니다.
내 기능은 다음과 같습니다
(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))
다른 팁
내 생각에는 먼저 두 목록을 별도로 정렬한 다음 중복 항목도 건너뛰는 기능으로 병합할 것 같습니다.두 목록 모두를 한 번 더 적게 탐색해야 하므로 조금 더 빨라야 합니다.
추신.:기본적으로 항상 적어도 하나의 정렬과 하나의 병합이 필요하기 때문에 훨씬 더 빨리 완료될 수 있을지 의심됩니다.아마도 둘 다 하나의 기능으로 결합할 수 있지만 그것이 (큰) 차이를 만들지 않더라도 놀라지 않을 것입니다.
목록을 병합하기 전에 정렬하면 병합, 중복 제거 및 정렬을 동시에 수행할 수 있습니다.정렬되고 중복이 없으면 병합/정렬/중복 제거 기능이 정말 간단해집니다.
실제로 중복을 확인하는 정렬된 삽입을 수행하도록 삽입 기능을 변경하는 것이 더 나을 수도 있습니다.그런 다음 항상 중복되지 않은 목록을 정렬했으며 이를 병합하는 것은 사소한 문제입니다.
그런 다음 나중에 중복 항목을 정렬/제거하는 대신 빠른 삽입 기능을 선호할 수도 있습니다.
중복 제거 기능보다 먼저 정렬을 적용하면 중복 제거 기능이 더 잘 작동하지 않나요?
Antti가 지적했듯이 REMOVE-DUPLICATES 및 SORT를 활용하고 싶을 수도 있지만 테스트 함수에 키워드(또는 선택적 인수)를 사용할 수도 있습니다.(Defun Merge-Lists (List-1 List-2 Sort-FN & Key (Test #'EQL)) ...) ...)
이렇게 하면 EQL이 충분하지 않은 한 테스트 기능(REMOVE-DUPLICATES에서 "중복으로 간주되는지 여부"를 테스트하는 데 사용됨)을 지정할 필요가 없습니다.
Set을 사용해야 할 것 같습니다.