두 개의 목록을 결합하고 정렬하고 중복 항목을 제거해야 합니다.이를 수행하는 더 좋은 방법이 있습니까?

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

다른 팁

내 생각에는 먼저 두 목록을 별도로 정렬한 다음 중복 항목도 건너뛰는 기능으로 병합할 것 같습니다.두 목록 모두를 한 번 더 적게 탐색해야 하므로 조금 더 빨라야 합니다.

추신.:기본적으로 항상 적어도 하나의 정렬과 하나의 병합이 필요하기 때문에 훨씬 더 빨리 완료될 수 있을지 의심됩니다.아마도 둘 다 하나의 기능으로 결합할 수 있지만 그것이 (큰) 차이를 만들지 않더라도 놀라지 않을 것입니다.

목록을 병합하기 전에 정렬하면 병합, 중복 제거 및 정렬을 동시에 수행할 수 있습니다.정렬되고 중복이 없으면 병합/정렬/중복 제거 기능이 정말 간단해집니다.

실제로 중복을 확인하는 정렬된 삽입을 수행하도록 삽입 기능을 변경하는 것이 더 나을 수도 있습니다.그런 다음 항상 중복되지 않은 목록을 정렬했으며 이를 병합하는 것은 사소한 문제입니다.

그런 다음 나중에 중복 항목을 정렬/제거하는 대신 빠른 삽입 기능을 선호할 수도 있습니다.

중복 제거 기능보다 먼저 정렬을 적용하면 중복 제거 기능이 더 잘 작동하지 않나요?

Antti가 지적했듯이 REMOVE-DUPLICATES 및 SORT를 활용하고 싶을 수도 있지만 테스트 함수에 키워드(또는 선택적 인수)를 사용할 수도 있습니다.(Defun Merge-Lists (List-1 List-2 Sort-FN & Key (Test #'EQL)) ...) ...)

이렇게 하면 EQL이 충분하지 않은 한 테스트 기능(REMOVE-DUPLICATES에서 "중복으로 간주되는지 여부"를 테스트하는 데 사용됨)을 지정할 필요가 없습니다.

Set을 사용해야 할 것 같습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top