セットを再考する
序章
C ++、C#、Java、およびPythonには、オブジェクトの順序付けられていないコレクションを定義するためのクラス、set、HashSet、Set、およびsetがあります。このアイデアの問題点は、これらのクラスが「小さな」個別のセットに適していることです。プロパティを示すセットが必要な場合もありますが、そのセットのすべての可能な要素をリストすると、コンピューターのメモリが不足します。この例は次のとおりです。
- すべての倍精度浮動小数点数のセットを検討してください。このようなセットを作成すると、ほとんどのコンピューティングデバイスのメモリが使い果たされ、データの入力にかなりの時間がかかります。
このようなセットの例は他にもたくさんありますが、通常の順序付けられていないオブジェクトのコレクションは理想的でも実用的でもありません。セットは膨大なメモリ要件を必要としません(または要求しません)が、非常に大きなセットを検討する場合のC ++、C#、Java、およびPythonのセットタイプは大量のメモリを必要とします。上記のような通常の順序付けされていない個別のコレクションを使用する代わりに、より一般的なクラス(またはある種のオブジェクト)を作成してみませんか?
私がこれを説明するときに私の語彙が適切でない場合は、私を許してください。私はコンピューター科学者ではありません。私は数学の低学年の学生で、数学で集合をどのように考えることができるかをエミュレートしたいと思っています。たとえば、実数は、宇宙の亜原子粒子の数よりも多くの元素を含む集合です。さらに、C ++、C#、Java、Pythonで見られる集合構成のように、実数の各要素を集合に配置して実数を構成することはできません。
代替セットオブジェクトの提案
セットオブジェクトの提案には、このセットの定性的な説明とセット操作の説明の2つの部分があります。
定性的説明
それへの2つの部分としてのセット。ジェネリックオブジェクトタイプ、およびプロパティ。
ジェネリックオブジェクトタイプ:セットの要素はドメインからのものである必要があります。プログラミングでは、ドメインは通常、ある種のオブジェクトタイプです。プログラミングで定期的に見られるオブジェクトタイプの例をいくつか示します。
- プリミティブデータ型:int、bool、float、double、char、stringなど。
- 固定配列:特定の固定サイズのデータ。下記は用例です
- 動的配列:ベクトル、リストなど。
- 構造体
- クラス
- 名前空間
- void(つまり、任意のタイプのオブジェクトを使用して任意のセットを作成できるということです)
- 特定のタイプのオブジェクトを返す関数
- 特定の入力品質を持つ関数(たとえば、3つの入力を持つ関数、または1つの整数入力を持つ関数など)
- 別のセット
- 等
セットのプロパティ:プロパティは、ジェネリックオブジェクトタイプ(1)の要素がセットの一部であるかどうかを決定します。プロパティは、trueまたはfalseを返す関数です。Trueはセットの一部であることを意味し、Falseはセットの一部ではないことを意味します。
(2)の利点は、プロパティ関数に、C ++、C#、Java、Pythonにすでにあるようなオブジェクトの個別のセットを含めることができること、または要素がプロパティを示すかどうかを確認できることです(たとえば、オブジェクトXはfloatですか? )。プロパティ関数は、要素がセットのプロパティであるかどうかを判断するために、任意に多くの入力を持つことができます(つまり、true / falseを返します)。また、プロパティ関数は、任意のオブジェクトを入力として処理するのに十分な柔軟性を備えている必要があることも考慮する必要があります。たとえば、セットのプロパティ関数がHorseオブジェクトの高さが6フィートよりも高いかどうかをチェックするときに、Catオブジェクトがセットの要素であるかどうかをテストしようとする場合があります。このようなシナリオでは、プロパティ関数は例外をスローする可能性がありますが、プロパティ関数は引き続きfalseを返す必要があります。
セット操作
- 和集合:2つ以上のセットを入力とする関数。入力のプロパティ関数は、それぞれP1、P2、...、Pnです。Union関数は、プロパティ関数がP1またはP2または---またはPnである新しいセットを返します。
- 共通部分:入力として2つ以上のセットを持つ関数。入力のプロパティ関数は、それぞれP1、P2、...、Pnです。Intersection関数は、プロパティ関数P1とP2、および---とPnを持つ新しいセットを返します。
- 褒め言葉:入力のみの関数がセットです。入力セットのプロパティ関数をP1とします。Compliment関数は、P1がtrueを返す場合、プロパティ関数がfalseを返す新しいセットを返します。P1がfalseの場合、プロパティ関数はtrueを返します。つまり、この新しいセットには、NOTP1のプロパティ関数があります。
- 相対的な褒め言葉:2つのセットを入力として持つ関数。入力のプロパティ関数は、それぞれP1、P2です。相対補完関数は、プロパティ関数が(P1であり、P2ではない)である新しいセットを返します。
- デカルト積:入力として1つ以上のセットに与えられます。この関数は、セットの2番目のコピーを生成します。コピーされたセットは、対応する元の入力セットと同じ順序でリストまたは配列に配置されます。
このセット実装の欠点は、任意の2つのセットについて、汎用オブジェクトタイプとプロパティを使用して1つのセットが別のセットのサブセットであることを示す決定論的な方法がないことです。おそらく、コンピュータサイエンス(および数学)でこれの最も有名な例は、P=NPであるかどうかです。これが機能するためには、任意の2つのセットの任意の2つのプロパティ関数P1とP2について、P1がP2を意味するか、P2がP1を意味することを示す必要があります。これは必ずしも簡単なことではありません。 構築したいこのセットオブジェクトで、この機能を犠牲にするつもりです。
達成するための一連の目標
私は、定性的記述セクションのセットオブジェクト、またはこれらのプログラミング言語のセットオプションを開発するのに十分な知識がありません。StackOverflowコミュニティに、開発を支援するよう呼びかけています。
- 上記のsetオブジェクトとset操作をさまざまな言語(C ++、C#、Java、Pythonだけでなく)で開発します。特定の種類のオブジェクトのセットを作成できない場合があることを受け入れたいと思います(例:
- このページおよび/またはGitHubで、SetObjectおよびSet操作コードをさまざまな言語で提示および提供します。
- 例では、setオブジェクトと演算子を使用します。
- セットがジェネリックオブジェクトタイプに使用できない、または使用できるものを詳しく説明します。
コード
このセクションには、Setオブジェクトのさまざまな実装があります。ここに記載されている言語以外の言語で実装している場合は、送信してください。私(または任意のmod)はそれをリストに追加できます。