algorithm - 2 つのリストを結合し、並べ替えて、重複を削除する必要があります。これを行うより良い方法はありますか？

Question

2 つの並べ替えられていないリストがあり、並べ替えられ、すべての要素が一意である別のリストを作成する必要があります。

要素は両方のリストで複数回発生する可能性があり、元はソートされていません。

私の関数は次のようになります。

(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

最初に 2 つのリストを別々に並べ替えてから、重複をスキップする関数でそれらをマージすると思います。両方のリストのトラバーサルが 1 回少なくて済むため、これは少し高速になるはずです。

PS: 基本的に常に少なくとも 1 つのソートと 1 つのマージが必要なため、はるかに高速に実行できるとは思えません。おそらく、両方を 1 つの関数に組み合わせることができますが、それが (大きな) 違いをもたらさなくても驚かないでしょう。

Answer 3

マージする前にリストを並べ替えると、マージ、重複の削除、および並べ替えを同時に行うことができます。それらがソートされていて重複がない場合、マージ/ソート/重複削除機能は本当に簡単になります。

実際、挿入関数を変更して、重複をチェックするソートされた挿入を実行する方がよい場合があります。次に、重複のないソートされたリストが常にあり、それらをマージするのは簡単なことです。

繰り返しになりますが、後で重複をソート/削除することを犠牲にして、高速な挿入機能を使用することをお勧めします。

Answer 4

remove-duplicatesの前にソートが適用された場合、remove-duplicates関数はより適切に機能しませんか？

Answer 5

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＆optional（test＃' eql）...）

このように、EQLが十分でない場合を除いて、テスト関数（REMOVE-DUPLICATESが「これらは重複と見なされるか」をテストするために使用）を指定する必要はありません。

Answer 6

セットを使用する必要があるようです。