objective-c - キーを予測可能な順序で格納する辞書構造に名前を付けますか？

Question

注：私の特定のコンテキストはObjective-Cですが、私の質問は実際にはプログラミング言語の選択を超えています。また、誰かが文句を言うので「主観的」とタグ付けしましたが、個人的にはほぼ完全に客観的だと思います。また、この関連するSOの質問を知っていますが、これはより大きな問題だったので、これを別の質問にする方がよいと思いました。よく読んで理解せずに質問を批判しないでください。ありがとう！

私たちのほとんどは、選択した言語に応じて、キーと値の関連付けを格納する辞書の抽象データ型に精通しています。これをマップ、辞書、連想配列、ハッシュなどと呼びます。辞書の簡単な定義は、次の3つのプロパティで要約できます。

値はキーによってアクセスされます（配列のようなインデックスではなく）。
各キーは値に関連付けられています。
各キーは一意である必要があります。

その他のプロパティは、間違いなく、特定の目的のための便利さまたは専門分野です。たとえば、一部の言語（特に、PHPやPythonなどのスクリプト言語）は、辞書と配列の間の境界線を曖昧にし、辞書の順序を提供します。これは便利ですが、そのような追加は辞書の基本的な特性ではありません。純粋な意味では、辞書の実際の実装の詳細は関係ありません。

私の質問では、最も重要な観察事項は、キーが列挙される順序が定義されていないことです。辞書は、最も便利な順序でキーを提供する場合があり、必要に応じてキーを整理するのはクライアントの責任です。

自然にソートされた順序（オブジェクトの比較に基づく）や挿入順序など、特定のキーの順序を課すカスタム辞書を作成しました。前者にSortedDictionaryのいくつかのバリアント（実際にはすでに実装済み）という名前を付けるのは明らかですが、後者の方が問題があります。LinkedHashMapとLinkedMap（Java）、OrderedDictionary（.NET）、OrderedDictionary（Flash）、OrderedDict（Python）、およびOrderedDictionary （ Objective-C）を見てきました。これらのいくつかはより成熟しており、いくつかはより概念実証です。

LinkedHashMapは、Javaコレクションの従来の実装に従って名前が付けられています。二重リンクリストを使用して挿入順序を追跡するため「リンク」、HashMapをサブクラス化するため「ハッシュ」です。ユーザーがそれについて心配する必要がないという事実に加えて、クラス名は実際にはそれが何をするかを示していません。順序付きを使用することは既存のコード間のコンセンサスのように見えますが、このトピックに関するWeb検索でも、「順序付き」と「並べ替え」の間の理解できる混乱が明らかになり、同じように感じます。.NET実装には、明らかな誤称についてのコメントもあり、順序付けの特定のポイントでオブジェクトを取得および挿入できるため、代わりに「IndexedDictionary」にする必要があることを示唆しています。

フレームワークとAPIを設計していて、クラスにできるだけインテリジェントな名前を付けたいと思っています。私の見解では、インデックス付けはおそらく機能し（人々がそれをどのように解釈するかによって、また辞書の宣伝された機能に基づいて）、順序付けは不正確であり、混乱する可能性が非常に高く、「すぐに」リンクされます（Monty Pythonに謝罪します））。;-)

ユーザーとして、あなたにとって最も意味のある名前は何ですか？クラスが何をしているのかを正確に表す特定の名前はありますか？（必要に応じて、InsertionOrderDictionaryのような少し長い名前を使用することを嫌いではありません。）

編集：もう1つの強力な可能性（以下の私の回答で説明）はIndexedDictionaryです。ユーザーが特定のインデックスにキーを挿入したり、キーを並べ替えたりすることを許可しても意味がないため、「挿入順序」はあまり好きではありません。

score 6 · Accepted Answer

次の理由で、私はOrderedDictionaryに投票します。

「インデックス付き」は、1つのインスタンスを除いて、Cocoaクラスで使用されることはありません。常に名詞として表示されます（NSIndexSet、NSIndexPath、objectAtIndex：など）。「Index」が動詞として表示されるインスタンスは、NSPropertyDescriptionの「indexed」プロパティにあるisIndexedとsetIndexedの1つだけです。NSPropertyDescriptionは、データベースのテーブル列にほぼ類似しています。ここで、「インデックス付け」とは、検索時間を短縮するための最適化を指します。したがって、NSPropertyDescriptionがCore Dataフレームワークの一部である場合、「isIndexed」および「setIndexed」はSQLデータベースのインデックスと同等であることが理にかなっています。したがって、データベース内のインデックスはルックアップ時間を短縮するために作成されるため、これを「IndexedDictionary」と呼ぶのは冗長に思えます。O（1）ルックアップ時間があります。ただし、Cocoaの「インデックス」は順序ではなく位置を指すため、これを「IndexDictionary」と呼ぶことも誤称になります。この2つは意味的に異なります。

「OrderedDictionary」に対する懸念は承知していますが、前例はすでにココアに設定されています。ユーザーが特定の順序を維持したい場合は、「ordered」を使用します。-[NSApplicationorderedDocuments]、-[NSWindoworderedIndex]、-[NSApplicationorderedWindows]など。したがって、JohnPirieはほとんど正しい考えを持っています。

ただし、辞書への挿入をユーザーの負担にしたくはありません。彼らは一度辞書を作成してから、適切な順序を維持させたいと思うでしょう。彼らは特定の順序でオブジェクトを要求することさえ望んでいません。順序の指定は、初期化中に行う必要があります。

したがって、OrderedDictonaryを、InsertionOrderDictionaryとNaturalOrderDictionaryおよびCustomOrderDictionaryのプライベートサブクラスを持つクラスクラスターにすることをお勧めします。次に、ユーザーは次のようにOrderedDictionaryを作成するだけです。

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

CustomOrderDictionaryの場合、比較セレクター、または（10.6を実行している場合は）ブロックを提供することができます。これにより、適切な名前を維持しながら、将来の拡張に最も柔軟に対応できると思います。

score 4 · Accepted Answer

4

に投票しInsertionOrderDictionaryます。あなたはそれを釘付けにしました。

于 2009-06-20T19:15:10.083 に答える

score 3 · Accepted Answer

OrderedDictionary に強い票を投じます。

「順序付けられた」という言葉は、あなたが宣伝していることを正確に意味します。つまり、アイテムのリストを反復処理する際に、それらのアイテムの選択に定義された順序があるということです。「インデックス付き」は実装の単語です。順序付けがどのように達成されるかについて詳しく説明しています。インデックス、リンクされたリスト、ツリー... ユーザーは気にしません。データ構造のその側面は非表示にする必要があります。「オーダー済み」は、提供する追加機能を表す正確な言葉であり、それをどのように実現するかに関係ありません。

さらに、順序の選択はユーザーの選択に委ねられているようです。ユーザーがアルファベット順から挿入時の順序に切り替えることができるデータ型のメソッドを作成できなかった理由は何ですか? デフォルトの場合、ユーザーは特定の順序付けを選択し、それに固執します。この場合、各順序付けメソッドに特化したサブクラスを作成した場合よりも実装の効率が低下することはありません。また、あまり使用されていないケースでは、アプリのコンテキストに応じて、開発者は同じデータに対してさまざまな順序付けのいずれかを実際に使用したい場合があります。(私が取り組んできた特定のプロジェクトで、そのようなデータ構造を利用できるようにしたかったと思います。)

それがまさにそれであるため、OrderedDictionary と呼びます。（率直に言って、「辞書」という言葉の使用にはもっと問題があります。その言葉は、そのような一般的な実装では提供されない順序付けを強く意味するためですが、それは私の不満です。あなたは本当にできるはずです「辞書」と言って、順序付けがアルファベット順であることを知っている (それが辞書の本来の姿だからです) しかし、その議論は、一般的な言語での既存の実装には遅すぎます。) そして、ユーザーが選択した順序でアクセスできるようにします。

score 2 · Accepted Answer

この質問を投稿してから、 IndexedDictionaryやIndexableDictionaryのようなものに傾倒し始めています。任意のキーの順序を維持できることは便利ですが、それを挿入の順序に制限することは、不必要な制限のように思えます。さらに、私のクラスはすでにとをサポートしていますindexOfKey:。keyAtIndex:これらは（意図的に）NSArrayindexOfObject:とに類似していobjectAtIndex:ます。insertObject:forKey:atIndex:NSMutableArrayと一致するものを追加することを強く検討していinsertObject:atIndex:ます。

配列の途中に挿入するのは非効率的であることは誰もが知っていますが、それが本当に役立つというまれな場合に許可されるべきではないという意味ではありません。（さらに、実装では、必要に応じて、二重リンクリストまたはその他の適切な構造を密かに使用して順序を追跡できます...）

大きな質問：「索引付け」または「索引付け可能」は曖昧であるか、または「順序付け」として混乱する可能性がありますか？人々はデータベースインデックスや本のインデックスなどを思い浮かべますか？アレイで実装されていると想定した場合、それは有害でしょうか、それともユーザーが機能を理解しやすくなる可能性がありますか？

編集：将来、 NSIndexSetで機能するメソッドを追加することを検討しているという事実を考えると、この名前はさらに意味があります。（NSArrayには-objectsAtIndexes:、特定のインデックスにあるオブジェクトのオブザーバーを追加/削除するためのメソッドもあります。）

score 1 · Accepted Answer

1

KeyedArray はどうですか?

于 2009-06-22T10:15:34.520 に答える

score 0 · Accepted Answer

最後の段落で述べたように、 InsertionOrder(ed)Dict(ionary) はかなり明白だと思います。キーが挿入された順序で返される以外に、それがどのように解釈されるかはわかりません。

score 0 · Accepted Answer

索引付けされた順序を挿入順序から分離することによって、配列と Dictionary を 1 つのオブジェクトに保持することになるのではないでしょうか? このタイプのオブジェクトに対する私の投票は IndexedKeyDictionary だと思います

C# の場合:

public class IndexedKeyDictionary<TKey, TValue> { 

  List<TKey> _keys;
  Dictionary<TKey, TValue> _dictionary;
  ...

  public GetValueAtIndex(int index) {
    return _dictionary[_keys[index]];
  }

  public Insert(TKey key, TValue val, int index) {
    _dictionary.Add(key, val);

    // do some array massaging (splice, etc.) to fit the new key
    _keys[index] = key;
  }

  public SwapKeyIndexes(TKey k1, TKey k2) {
    // swap the indexes of k1 and k2, assuming they exist in _keys
  }
}

本当に素晴らしいのは、インデックス付きの値です...そのため、値を並べ替えて新しいキーの順序を取得する方法があります。値がグラフ座標の場合と同様に、座標平面に沿って上下に移動すると、キー (ビン名) を読み取ることができます。そのデータ構造を何と呼びますか? IndexedValueDictionary?

score 0 · Accepted Answer

一見したところ、私は最初の応答である InsertionOrderDictionary に同意しますが、「InsertionOrder」が何を意味するかについては一見あいまいです。

あなたが説明していることは、C++ STL マップとほとんど同じように聞こえます。私が理解していることから、マップは順序付けを含む追加のルールを持つ辞書です。STL では単に「マップ」と呼んでいますが、これはかなり適切だと思います。マップの秘訣は、継承を冗長にしない限り、継承にうなずくことはできないということです。つまり、「MapDictionary」です。それはあまりにも冗長です。「地図」は少し基本的すぎて、誤解の余地がたくさんあります。

ドキュメントリンクを見た後、「CHMap」は悪い選択ではないかもしれませんが。

多分「CHMappedDictionary」？=)

幸運を祈ります。

編集：明確にしてくれてありがとう、あなたは毎日何か新しいことを学びます. =)

score -1 · Accepted Answer

allKeys特定の順序でキーを返す唯一の違いですか? もしそうなら、標準APIにメソッドallKeysSortedとメソッドを追加するだけです。allKeysOrderdByInsertionNSDictionary

この広告掲載オーダーディクショナリの目的は何ですか? 配列と比較して、プログラマーにどのような利点がありますか?

objective-c - キーを予測可能な順序で格納する辞書構造に名前を付けますか？

9 に答える 9

Related

Reference