Называть словарную структуру, которая хранит ключи в предсказуемом порядке?

Question

Примечание: Хотя мой конкретный контекст - Objective-C, мой вопрос фактически выходит за рамки выбора языка программирования. Кроме того, я отметил это как «субъективный», так как кто-то должен жаловаться иначе, но я лично думаю, что это почти полностью объективно. Кроме того, я знаю этот связанный вопрос SO , но, поскольку это была более серьезная проблема, я подумал, что лучше сделать этот вопрос отдельным. Пожалуйста, не критикуйте вопрос, не прочитав и не поняв его полностью. Спасибо!

Большинство из нас знакомы с словарем абстрактным типом данных , в котором хранятся ассоциации ключ-значение, независимо от того, назовем ли мы карту, словарь, ассоциативный массив, хэш и т. Д. на нашем языке по выбору. Простое определение словаря может быть обобщено тремя свойствами:

1. Значения доступны по ключу (в отличие от индекса, как массив).
2. Каждый ключ связан со значением.
3. Каждый ключ должен быть уникальным.

Любые другие свойства - это, вероятно, удобства или специализации для конкретной цели. Например, некоторые языки (особенно языки сценариев, такие как PHP и Python) стирают грань между словарями и массивами и обеспечивают упорядочение словарей. Как бы это ни было полезно, такие дополнения не являются фундаментальными характеристиками словаря. В чистом смысле фактические детали реализации словаря не имеют значения.

По моему вопросу, самое важное наблюдение состоит в том, что порядок, в котором перечислены ключи, не определен - словарь может предоставлять ключи в любом порядке, который он сочтет наиболее удобным, и это зависит от клиента. организовать их по желанию.

Я создал пользовательские словари , которые устанавливают определенные ключевые упорядочения, включая естественный отсортированный порядок (на основе сравнения объектов) и порядок вставки . Вполне очевидно назвать первый вариант для SortedDictionary (который я на самом деле уже реализовал), но последний более проблематичен. Я видел LinkedHashMap и LinkedMap (Java), OrderedDictionary (.NET), OrderedDictionary (Flash), OrderedDict (Python) и OrderedDictionary (Objective-C). Некоторые из них более зрелые, а некоторые более проверенные.

LinkedHashMap назван в соответствии с реализацией в традиции Java-коллекций - «связанный», поскольку он использует список с двумя связями для отслеживания порядка вставки, и «хэш», поскольку он подклассы HashMap. Помимо того, что пользователю не нужно беспокоиться об этом, имя класса на самом деле даже не указывает, что он делает. Использование упорядоченного кажется консенсусом среди существующего кода, но поиски в сети по этой теме также выявили понятную путаницу между «упорядоченным» и «отсортированным», и я чувствую то же самое. В реализации .NET даже есть комментарий о кажущемся неправильном значении, и предполагается, что вместо этого он должен быть «IndexedDictionary», так как вы можете извлекать и вставлять объекты в определенной точке в порядке.

Я разрабатываю фреймворк и API и хочу назвать класс максимально разумно. С моей точки зрения, indexed , вероятно, будет работать (в зависимости от того, как люди его интерпретируют и основываясь на рекламируемой функциональности словаря), order является неточным и имеет слишком много возможностей для путаницы, и связанный"прямо сейчас" (извинения Монти Пайтону). ; -)

Как пользователь, какое имя будет иметь для вас наибольшее значение? Есть ли конкретное имя, которое точно говорит, что делает класс? (Я не против использования более длинных имен, таких как InsertionOrderDictionary, если это уместно.)

Редактировать: Другая серьезная возможность (обсуждаемая в моем ответе ниже) - IndexedDictionary . Мне не очень нравится «порядок вставки», потому что не имеет смысла, если вы разрешаете пользователю вставлять ключи по определенному индексу, переупорядочивать ключи и т. Д.

Answer 1

Я голосую за OrderedDictionary по следующим причинам:

«Индексируется» никогда не используется в классах Какао, за исключением одного случая. Он всегда отображается как существительное (NSIndexSet, NSIndexPath, objectAtIndex: и т. Д.). Существует только один случай, когда «Index» отображается в виде глагола, который находится в «индексированном» свойстве NSPropertyDescription: isIndexed и setIndexed. NSPropertyDescription примерно аналогичен столбцу таблицы в базе данных, где «индексация» означает оптимизацию для ускорения времени поиска. Поэтому было бы разумно, если бы NSPropertyDescription входил в структуру Core Data, то isIndexed и setIndexed были бы эквивалентны индексу в базе данных SQL. Поэтому называть его «IndexedDictionary» представляется излишним, поскольку индексы в базах данных создаются для ускорения времени поиска, но словарь уже имеет время поиска O (1). Однако называть его «IndexDictionary» также неправильно, поскольку «индекс» в Какао относится к позиции, а не к порядку. Два семантически разные.

Я понимаю ваше беспокойство по поводу "OrderedDictionary", но прецедент уже установлен в Какао. Когда пользователи хотят поддерживать определенную последовательность, они используют «упорядоченный»: - [NSApplication orderDocuments], - [NSWindow orderIndex], - [NSApplication OrderWindows] и т. Д. Итак, Джон Пири в основном имеет правильную идею.

Однако вы не хотите, чтобы вставка в словарь была обузой для ваших пользователей. Они захотят создать словарь один раз и затем сохранить его в соответствующем порядке. Они даже не захотят запрашивать объекты в определенном порядке. Спецификация заказа должна быть выполнена во время инициализации.

Поэтому я рекомендую сделать OrderedDictonary кластером классов с закрытыми подклассами InsertionOrderDictionary и NaturalOrderDictionary и CustomOrderDictionary. Затем пользователь просто создает OrderedDictionary примерно так:

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

Для CustomOrderDictionary вы можете сделать так, чтобы они предоставили вам селектор сравнения или даже (если они работают 10.6) блок. Я думаю, что это обеспечит максимальную гибкость для будущего расширения при сохранении соответствующего имени.

Answer 2

Я голосую за InsertionOrderDictionary. Вы прибили это.

Answer 3

Сильный голос за OrderedDictionary.

Слово «заказано» означает именно то, что вы рекламируете: что при переборе списка элементов существует определенный порядок выбора этих элементов. «Индексируется» - это слово реализации - оно больше говорит о том, как достигается порядок. Индекс, связанный список, дерево ... пользователю все равно; этот аспект структуры данных должен быть скрыт. «Заказано» - это точное слово для дополнительной функции, которую вы предлагаете, независимо от того, как вы ее выполняете.

Кроме того, похоже, что выбор порядка может быть на усмотрение пользователя. Любая причина, почему вы не можете создать методы для вашего типа данных, которые позволяют пользователю переключаться, скажем, с алфавитного порядка на порядок вставки по времени? В случае по умолчанию пользователь выбирает конкретный порядок и придерживается его, и в этом случае реализация будет не менее эффективной, чем если бы вы создали специализированные подклассы для каждого метода упорядочения. А в некоторых менее часто используемых случаях разработчик может захотеть использовать любой из нескольких разных порядков для одних и тех же данных, в зависимости от контекста приложения. (Я могу вспомнить конкретные проекты, над которыми я работал, где бы мне хотелось иметь такую ​​структуру данных.)

Назовите его OrderedDictionary, потому что это именно то, что он есть. (Честно говоря, у меня больше проблем с использованием слова «словарь», потому что это слово в значительной степени подразумевает упорядочение, когда популярные реализации такого не обеспечивают, но это моя любимая мозоль. Вы действительно должны просто иметь возможность произнесите «Словарь» и знайте, что порядок алфавитный - потому что таков словарь, - но этот аргумент слишком поздний для существующих реализаций на популярных языках.) И разрешите пользователю доступ в том порядке, который он выберет.

Answer 4

После публикации этого вопроса я начинаю склоняться к чему-то вроде IndexedDictionary или IndexableDictionary . Хотя полезно иметь возможность поддерживать произвольное упорядочение ключей, ограничение этого порядка упорядочением при вставке кажется лишь ненужным ограничением. Кроме того, мой класс уже поддерживает indexOfKey: и keyAtIndex:, которые (целенаправленно) аналогичны NSArray indexOfObject: и objectAtIndex:. Я настоятельно рекомендую добавить insertObject:forKey:atIndex:, что соответствует NSMutableArray insertObject:atIndex:.

Все знают, что вставка в середину массива неэффективна, но это не значит, что в тех редких случаях нам нельзя допускать, чтобы это было действительно полезно. (Кроме того, реализация может тайно использовать двусвязный список или любую другую подходящую структуру для отслеживания порядка при необходимости ...)

Большой вопрос: «индексируется» или «индексируется» как расплывчатый или потенциально запутанный как «упорядоченный»? Будут ли люди думать об индексах базы данных, индексах книг и т. Д.? Будет ли это вредным, если они предположят, что он реализован с помощью массива, или это может упростить понимание пользователем функциональности?

---

Редактировать: Это имя имеет еще больший смысл, учитывая тот факт, что я рассматриваю возможность добавления методов, которые будут работать с NSIndexSet в будущем. (NSArray имеет -objectsAtIndexes:, а также методы для добавления / удаления наблюдателей для объектов с заданными индексами.)

Answer 5

А как насчет KeyedArray?

Answer 6

Отключая индексированный порядок от порядка вставки, разве это не сводится к тому, чтобы хранить массив и словарь в одном объекте? Я предполагаю, что мой голос за этот тип объекта - 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?

Answer 7

На первый взгляд, я с первым ответом - InsertionOrderDictionary, хотя это немного двусмысленно относительно того, что "InsertionOrder" означает на первый взгляд.

То, что вы описываете, звучит для меня почти так же, как карта C ++ STL. Насколько я понимаю, карта - это словарь, в котором есть дополнительные правила, в том числе порядок. STL просто называет это «картой», что я считаю вполне подходящим. Хитрость с картой заключается в том, что вы не можете по-настоящему дать намек на наследование, не сделав его избыточным - то есть «MapDictionary». Это слишком избыточно. «Карта» слишком проста и оставляет много места для неправильного толкования.

Хотя "CHMap" не может быть плохим выбором после просмотра ссылки на документацию.

Может быть, "CHMappedDictionary"? =)

Удачи.

Редактировать: Спасибо за разъяснения, вы узнаете что-то новое каждый день. =)

Answer 8

Единственная разница, что allKeys возвращает ключи в определенном порядке? Если это так, я бы просто добавил allKeysSorted и allKeysOrderdByInsertion методы к стандартному NSDictionary API.

Какова цель этого словаря порядка вставки? Какие преимущества это дает программисту против массива?

Answer 9

Как вы сказали в своем последнем абзаце, я думаю, что InsertionOrder (ed) Dict (ionary) довольно однозначен; Я не понимаю, как это можно интерпретировать каким-либо иным способом, кроме того, что ключи будут возвращены в порядке их вставки.