順序付きセットと順序なしセットの違いを理解し、多くの目的で順序付きセットが必要ない理由を理解しています。ただし、すべてのセット操作は引き続き実行されます。順序付けられたセットで可能であり、セットはとにかく何らかの順序で内部に格納する必要があるのに、なぜデフォルトでセットが順序付けられないのですか？セットの順序を維持することによるパフォーマンスへの影響は大きすぎますか？
コメント
- "順序付けされていないコレクション内の値の順序付け"は、挿入順序に依存し、値自体には依存しない場合があります。'通常使用される意味での順序付け（数学用語に由来します）。
- この質問は、'ではないため、トピックから外れていると見なされる場合があります。特定のプログラムの開発についてではなく、言語の設計についてです。
- @outis私は'正しいサブサイトについて確信が持てませんでしたが、別のサブサイトがありますか？
回答
重要なのは、オーバーヘッドが特に大きいということではなく、そこにあるということです。 すべて。
言語機能は、常に費用対効果のバランスをとる必要があります。辞書はPythonプログラミングの絶対的な基本であるため、ほとんどの場合、順序付けが不要な場合に、挿入順序を保持するためだけに必要な速度よりも少し遅くなることは非常に悪いことです。わずかに高速なアクセスと引き換えに挿入順序を破棄し、特別なクラス用に順序を保持するデータ構造を残します。dictが実行できるすべてのことを実行できる別のデータ構造があり、dictが言語のあまり使用されていないしわであった場合、
コメント
- これに対する私の反論は、内部辞書に、より効率的な順序付けられていないdictデータ型を使用することです（そこと同じように） ' s
dequeは、他の特定のコンテキストでのパフォーマンスを最適化します）が、メインのユーザー向けdictデータ型に順序を保持させます。 - また、3.6のCPython実装が実際に挿入順序を保持していることを理解していますか？ dicts？
回答
アイテムが何らかの順序で内部に保存されているのは正しいですが、この内部順序はキーのハッシュコードによって決定されます。これにより、取得が非常に高速になります。したがって、set / dictを順序付けする必要がある場合は、このために別個の内部データ構造（たとえば、順序付けられたキーのリスト）を維持する必要があります。
もちろん、これによりサイズが大きくなります。しかし、おそらくもっと悪いことに、それはパフォーマンスに影響を与えます。たとえば、セットからアイテムを削除することはO（1）操作ですが、内部の順序付きリストからキーも削除する必要がある場合は、O（n）になります。このようなコストは、一部のアプリケーションにとって悲惨なものになります。順序集合が必要になることは非常にまれであるため、このようなトレードオフは、標準のset / dictタイプでは価値がありません。
回答
あなたの前提は正しくありません。 Python 3.6以降、 dictは挿入順序を記憶しています。これは実装の詳細であり、3.7で完全な言語機能に昇格しました。 3.6では、**kwargsの特定のケースでは、順序の保持が明確に保証されています。
コメント
- はい、'はまだ言語機能ではなく、単なる実装であるため、質問したときに'気づいていませんでした。 1つの実装で詳細。しかし、少なくとも辞書は長期的に注文されるようになり、うまくいけばセットされるようです。
- @oulenz it 'はもはや実装の詳細ではなく、'はPython3.7以降で必要です
回答
注文済みセットは、格納される要素に最初に順序付け（つまり、比較方法）がある場合にのみ可能ですが、常に指定されているとは限りません。
現在のほとんどの環境でのデフォルトのセット/マップの実装は、自動サイズ変更ハッシュテーブルに基づいており、次の利点があります。
- 高速
- 使用するメモリが少ない
- 要素に順序を指定する必要がない
とにかく、セットは何らかの順序で内部に保存する必要があります
しかし、この内部順序は必ずしも意味を持たず、同じままでもありません。実際、経験の浅い開発者を混乱させることがあるハッシュテーブルのプロパティの1つは、内部の順序に基づく反復順序が、要素が追加されたとき（つまり、サイズ変更がトリガーされたとき）または異なる間で完全に変更される可能性があることです。実行されます。
コメント
- 最初の発言がわかりません'。 '比較方法は必要ありません。順序は継承されるだけです。たとえば、リストまたは文字列リテラルから
{3, 5, 4}。 - @oulenz：'の順序を気にしない場合意味がなく、時間の経過とともに変化する場合、いくつかの種類の反復順序があるため、すべてのセットが順序付けられます。ただし、" ordered set "は、順序付けが要素のセマンティックであることを意味し、常に可能であるとは限りません。 'すべてのセットを注文する理由がよくわかりません。
- "注文したセット"は、順序がセマンティックであることを意味するのではなく、いくつかの順序があることを意味します。もちろん、この順序が確立されると、内容が変更されない限り、保存されることに注意します。
- 申し訳ありませんが、'影響が存在することに気づいていませんでした。一部の人にとっては。私は単に数学から線形に順序付けられたセットを念頭に置いていました。 en.wikipedia.org/wiki/Total_order
- @jameslarge順序関係は'私には知られていない必要があります。リストから順序集合を導出すると、その順序が正確にわかります。特定の順序を確保したい場合は、セットを並べ替えることができます。ただし、'注文が不要な場合は、無視してかまいません。
回答
セットまたは辞書の背後にある一般的な考え方は、多くのルックアップ操作を実行することを計画しているということです。ほとんどの場合、O（1）ルックアップを可能にするハッシュを使用することにより、前述のルックアップ操作用に最適化されます。
順序は配列またはリンクリストを使用して行われ、実際、順序が重要な操作を実行すると、最適化されます。 最後または最初に値を追加するなど。
これら2つのデータ構造の性質上、どちらも両方に最適化されていません。これが不可能であるとは言えませんが、ルックアップ操作と順序ベースの操作の両方を最適化する場合は、両方のデータ構造が必要になります。
したがって、次のトレードオフがあります。
ルックアップ操作の最適化< =>注文ベースの操作< =>メモリ使用量
一般的なコンセンサスは、プログラマーとして、一般的にどちらか一方を最適化することを望んでいるが、両方は最適化しないことです。 2つのうちの1つを最適化します。
とはいえ、両方を使用した、または少なくともJavaでの実装が あります。具体的には、LinkedHashMapは配列とハッシュの両方です-ベースの辞書。両方が必要な場合もありますが、リストのみが必要な場合はArrayListを使用し、辞書のみが必要な場合はHashMapを使用することをお勧めします。 。
コメント
- え？ Java LinkedHashMapは、"配列とハッシュベースの辞書の両方ではありません"。 'は基本的にHashMap（つまり、内部で配列を使用）にリンクリストを重ね合わせて、挿入順序での反復を可能にします。
- 線形データ構造は'順序付けられた唯一のデータ構造。二分木も注文できます（赤黒やAVL木など）。トレードオフに関係する可能性のある別の操作は挿入です（配列はルックアップ、反復、およびメモリ使用量の点では非常に効率的ですが、挿入に関しては最も遅くなります）。