2

Hyperspec からの次のステートメントがそのようになっている論理的な理由はありますか? 「list-1 と list-2 の間に重複がある場合、重複するインスタンスの 1 つだけが結果に含まれます。list-1 または list-2 のいずれかに重複するエントリがある場合、冗長なエントリが表示される場合と表示されない場合があります。結果で。」

これを読むまで、union は一意のリストを返すべきだと思っていましたが、コードがそうしなかった理由に不満を感じていました。リスト内ではなくリスト間の重複を削除するのも奇妙に思えます。なぜこれを指定するのですか?

ユニオンがセットの要素の一意のリストを生成すると想定できるように思われるか、何か不足していますか?

Hyperspec の完全なページについては、http: //clhs.lisp.se/Body/f_unionc.htm を参照してください。

4

2 に答える 2

5

1 2 3コードに一意の要素 ( など)のみを持つセットがある場合、 はUNIONこのプロパティを保持します。

コードに一意ではない要素 ( など1 2 2 3) を含むセットがある場合UNION、結果セットに一意性を強制するための努力をする必要はありません。

重複の削除は別の関数で行われます: REMOVE-DUPLICATES.

于 2012-05-30T19:25:10.670 に答える
4

UNIONの引数である両方のリストの要素が一意であると仮定すると、最悪の場合のアルゴリズムの複雑さ(ソート不可、ハッシュ不可の要素)はO(n * m)になります。一方、その場合のリスト内の重複の削除はO(n ^ 2)です。UNIONに重複を削除させると、重複がない場合でも実行時間が約3倍になります。これは、ほとんどの時間が比較を行うために消費されるためです。

于 2012-05-30T15:48:01.637 に答える