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

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

  •  01-07-2019
  •  | 
  •  

質問

ソートされていないリストが 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)
役に立ちましたか？

解決

私たちの近所のフレンドリーな 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))

他のヒント

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

追記：基本的に常に少なくとも 1 つの並べ替えと 1 つのマージが必要になるため、これよりも速く実行できるとは思えません。おそらく両方を 1 つの関数に組み合わせることができますが、それが（大きな）違いを生まなくても私は驚かないでしょう。

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

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

繰り返しになりますが、後で重複を並べ替えたり削除したりすることを犠牲にして、高速な挿入機能を使用したい場合もあります。

重複を削除する前に並べ替えを適用すると、重複の削除機能がより適切に動作するのではないでしょうか?

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 によって「これらは重複とみなされますか」をテストするために使用されます) を指定する必要がなくなります。

Setを使用する必要があるようです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top