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

StackOverflow https://stackoverflow.com/questions/1022269

質問

  

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

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

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

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

私の質問で最も重要なのは、キーが列挙される順序が定義されていないことです＆＃8212;辞書は最も便利な順序でキーを提供できます。必要に応じてキーを整理するのはクライアント次第です。

カスタム辞書を作成しました。 自然なソート順（オブジェクトの比較に基づく）および挿入順。前者に SortedDictionary のバリアントを指定することは明らかです（実際に既に実装しています）が、後者にはより問題があります。 LinkedHashMap および LinkedMap （Java）、< a href = "http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx" rel = "nofollow noreferrer"> OrderedDictionary （.NET）、 OrderedDictionary （Flash）、 OrderedDict （Python）、および OrderedDictionary （Objective-C）。これらの一部はより成熟しており、一部は概念実証です。

LinkedHashMap は、Javaコレクションの伝統の実装に従って名前が付けられています＆＃8212; 「リンク」二重リンクリストを使用して挿入順序を追跡し、「ハッシュ」を使用するためです。 HashMapをサブクラス化するためです。ユーザーがそのことを心配する必要はないという事実に加えて、クラス名は実際にそれが何をするのかさえ示していません。 ordered を使用すると、既存のコード間のコンセンサスのように見えますが、このトピックに関するWeb検索では、「ordered」とと「並べ替え」、そして私は同じように感じます。 。

役に立ちましたか？

解決

次の理由により、OrderedDictionaryに投票します。

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

「OrderedDictionary」に対する懸念を理解していますが、先例は既にCocoaで設定されています。ユーザーが特定のシーケンスを維持したい場合、「ordered」を使用します：-[NSApplicationorderedDocuments]、-[NSWindoworderedIndex]、-[NSApplicationorderedWindows]など。したがって、John Pirieはほとんど正しい考えを持っています。

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

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

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

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

他のヒント

InsertionOrderDictionary に投票します。釘付けにしました。

OrderedDictionaryへの強い投票。

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

さらに、順序の選択はユーザーの選択にあるようです。ユーザーが、たとえばアルファベット順から挿入時間順に切り替えることができるメソッドをデータ型に作成できなかった理由は何ですか？デフォルトの場合、ユーザーは特定の順序付けを選択し、それに従います。その場合、各順序付けメソッド用に特別なサブクラスを作成した場合と同様に、実装はそれほど効率的ではありません。また、使用頻度の低いケースでは、開発者は、アプリのコンテキストに応じて、同じデータに対していくつかの異なる順序のいずれかを実際に使用したい場合があります。 （このようなデータ構造を利用できるようにしたいと思っていた場所で、私が取り組んできた特定のプロジェクトを考えることができます。）

OrderedDictionaryと呼びます。それがまさにそれだからです。 （率直に言って、「Dictionary」という単語の使用には問題があります。というのは、その単語は順序付けを強く意味しているためです。そのようなものの一般的な実装では提供されませんが、それは私のpet望です。 「Dictionary」と言って、順序がアルファベット順であることを知ってください-それは辞書だからです-しかし、その引数は人気のある言語の既存の実装には遅すぎます。）そして、ユーザーが選択した順序でアクセスできるようにします。

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

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

大きな質問：「インデックス付き」ですまたは＆quot; indexable＆quot; 「注文済み」として曖昧または潜在的に混乱しますか？人々はデータベースのインデックスや本のインデックスなどを考えますか？配列を使用して実装されていると想定した場合、それは有害でしょうか、それともユーザーが機能を理解しやすくなる可能性がありますか？

編集： NSIndexSet 将来的に。 （NSArrayには -objectsAtIndexes： および特定のインデックスのオブジェクトのオブザーバーを追加/削除するためのメソッド。

KeyedArrayはどうですか？

最後の段落で述べたように、InsertionOrder（ed）Dict（ionary）はかなり曖昧ではないと思います。キーが挿入された順序で返される以外の方法でどのように解釈できるかわかりません。

インデックス化された順序を挿入順序から分離することにより、これは単純に配列と辞書を単一のオブジェクトに保持することになりませんか？このタイプのオブジェクトに対する私の投票は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？

一見すると、最初の返信であるInsertionOrderDictionaryがありますが、「InsertionOrder」が何であるかについては少しあいまいです。一目で意味します。

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

ただし、＆quot; CHMap＆quot;ドキュメントのリンクを見た後に悪い選択ではないかもしれません。

たぶん＆quot; CHMappedDictionary＆quot ;? =）

幸運を祈ります。

編集：説明のおかげで、毎日何か新しいことを学びます。 =）

allKeys が特定の順序でキーを返すのは唯一の違いですか？その場合、 allKeysSorted および allKeysOrderdByInsertion メソッドを標準の NSDictionary APIに追加するだけです。

この広告掲載順序辞書の目的は何ですか？プログラマーに対して配列に対してどのようなメリットがありますか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top