5

いくつかのプログラミング言語には、有限集合の数学的概念の実装であると想定される Set コレクションがあります。

ただし、これは必ずしも正しいとは限りません。たとえば、C#およびJavaでは、 の両方の実装で、任意のコレクションをそれ自体のメンバーとしてHashSet<T>追加できます。HashSet<T>数学的集合の現代的な定義では、これは許可されていません。

バックグラウンド：

単純集合論によると、集合の定義は次のとおりです。

セットは、個別のオブジェクトのコレクションです。

ただし、この定義は、ラッセルのパラドックスや他のパラドックスにつながることで知られています。便宜上、ラッセルのパラドックスは次のとおりです。

R を、それ自体のメンバーではないすべてのセットのセットとします。R がそれ自体のメンバーでない場合、その定義はそれ自体を含む必要があることを示し、R がそれ自体を含む場合、それ自体のメンバーではないすべてのセットのセットとしての独自の定義と矛盾します。

したがって、現代の集合論 ( ZFCを参照) によると、集合の定義は次のとおりです。

セットは個別のオブジェクトのコレクションであり、そのいずれもセット自体ではありません。

具体的には、これは規則性の公理の結果です。

それで何？これにはどのような意味がありますか？この質問が StackOverflow にあるのはなぜですか?

ラッセルのパラドックスの意味の 1 つは、すべてのコレクションがセットであるとは限らないということです。さらに、これは数学者がセットの定義を通常の英語の定義として落としたポイントでした。したがって、プログラミング言語の設計全般に関して言えば、この質問には大きな重みがあると思います。

質問:

では、何らかの形でこれらの原則を設計そのものに使用しているプログラミング言語が、言語ライブラリの Set の実装でそれを無視するのはなぜでしょうか?

第二に、これは数学的概念の他の実装でよくあることですか?

おそらく私は少しうるさいですが、これらがセットの真の実装である場合、定義の一部が無視されるのはなぜですか?

アップデート

動作を例示する C# および Java コード スニペットの追加:

Java スニペット:

Set<Object> hashSet = new HashSet<Object>();
hashSet.add(1);
hashSet.add("Tiger");
hashSet.add(hashSet);
hashSet.add('f');

Object[] array = hashSet.toArray();
HashSet<Object> hash = (HashSet<Object>)array[3];

System.out.println("HashSet in HashSet:");       
for (Object obj : hash)
    System.out.println(obj);

System.out.println("\nPrinciple HashSet:");
for (Object obj : hashSet)
    System.out.println(obj);

どちらが出力されますか：

HashSet in HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]

Principle HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]

C# スニペット:

HashSet<object> hashSet = new HashSet<object>();
hashSet.Add(1);
hashSet.Add("Tiger");
hashSet.Add(hashSet);
hashSet.Add('f');

object[] array = hashSet.ToArray();
var hash = (HashSet<object>)array[2];

Console.WriteLine("HashSet in HashSet:");
foreach (object obj in hash)
     Console.WriteLine(obj);

Console.WriteLine("\nPrinciple HashSet:");
foreach (object obj in hashSet)
     Console.WriteLine(obj);

どちらが出力されますか：

HashSet in HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f

Principle HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f

更新 2

Martijn Courteauxの 2 番目のポイントに関しては、計算効率の名目で実行できるということでした。

C# で 2 つのテスト コレクションを作成しました。それらの 1 つの Add メソッドを除いて、それらは同一でした - 次のチェックを追加しました:コレクションに追加される項目はif (this != obj)どこですか。obj

100,000 のランダムな整数を追加する場所で、両方を別々にクロックしました。

チェックあり: ~ 28 ミリ秒

チェックなし: ~ 21 ミリ秒

これはかなり大きなパフォーマンスの向上です。

4

4 に答える 4

9

プログラミング言語セットは実際には ZFC セットのようなものではありませんが、あなたが思っているよりもかなり異なる理由があります:

  1. 理解によってセットを形成することはできません (つまり、... などのすべてのオブジェクトのセット)。これはすでにすべての（私が信じている）単純な集合論のパラドックスをブロックしているため、それらは無関係であることに注意してください。

  2. 通常、それらは無限にはなりません。

  3. セットではないオブジェクトが存在します (ZFC ではセットしかありません)。

  4. これらは通常変更可能です (つまり、要素をセットに追加/セットから削除できます)。

  5. それらに含まれるオブジェクトは変更可能です。

だから答えは

では、何らかの形でこれらの原則を設計そのものに使用しているプログラミング言語が、言語ライブラリの Set の実装でそれを無視するのはなぜでしょうか?

言語がこれらの原則を使用していないということです。

于 2013-09-01T07:02:53.173 に答える
4

さて、これにはいくつかの理由があると思います：

  1. 非常に特殊なプログラミング目的のために、それ自体を含むセットを作成したい場合があります。Setこれを行っているときは、セットが数学的に何を意味するかについてあまり気にせず、重複するエントリを作成せずにセットに要素を「追加」するという機能を楽しみたいだけです。（正直に言うと、あなたがそれをしたい状況が思い浮かびません。）

  2. パフォーマンス目的のため。Set を使用してそれ自体を含むようにする機会は非常にまれです。そのため、要素を追加しようとするたびにそれがセット自体であるかどうかを確認するのは、コンピューティング パワー、エネルギー、時間、パフォーマンス、および環境の状態の無駄になります。

于 2013-08-31T21:32:43.323 に答える
3

C# について話すことはできませんが、Java に関する限り、セットはセットです。Set インターフェイスの javadoc を見ると、次のように表示されます (強調は私のものです)。

注: ミュータブル オブジェクトをセット要素として使用する場合は、細心の注意を払う必要があります。オブジェクトがセット内の要素であるときに、オブジェクトの値が equals 比較に影響を与える方法で変更された場合、セットの動作は指定されません。この禁止事項の特殊なケースは、集合がそれ自体を要素として含むことが許されないということです。

禁止が積極的に実施されているかどうかは不明です (たとえば、HashSet をそれ自体に追加しても例外はスローされません)。

于 2013-08-31T20:56:47.343 に答える
0

Java では、セットは数学的セットです。オブジェクトを挿入できますが、セットに含めることができるのは 1 つだけです。セットに関する javadoc からの情報:

「重複要素を含まないコレクション。より正式には、セットには、e1.equals(e2) のような要素 e1 と e2 のペアが含まれず、最大でも 1 つの null 要素が含まれます。その名前が示すように、このインターフェイスは数学的なセットの抽象化をモデル化します。 ."

ソース: http://docs.oracle.com/javase/7/docs/api/

于 2013-08-31T20:51:32.323 に答える