Эффективность словарей C #

14

Словари C # - это простой способ узнать, существует ли что-то и т. Д. У меня есть вопрос, как они работают. Допустим, вместо словаря я использую ArrayList. Вместо использования ContainsKey(или эквивалентного метода на другом языке) я перебираю ArrayList, чтобы проверить, существует ли там что-то (или выполняет двоичный поиск, если данные отсортированы или что-то подобное). Какая разница в эффективности? ContainsKeyИспользует ли метод какой-то более эффективный способ, нежели циклический просмотр ключей и проверку, существует ли то, что я ищу?

Если, скажем, я создал определенную хеш-функцию, которая соответствует типу данных, которые у меня есть, и специально разработана для этого набора данных, то да, эта хеш-функция действительно быстрее, чем циклически проходить по данным. Но словари являются общими. Метод ContainsKey не является специфичным для данных, которые он получает, это общий метод поиска.

В основном то, что я спрашиваю. Словари полезны для программистов. Они включают методы, которые помогают во многих вещах, и объединяют строки с целыми числами (ключами и значениями) и многими другими. Но что касается эффективности, что они предлагают? Какая разница в том, dictionaryпротив ArrayListизstructs(string,int)

Джон Деметриу
источник
Вы действительно сравниваете яблоки с апельсинами здесь. Я думаю, что ключевое слово, которое вы ищете - Data Structures эта ссылка на вики может быть вам более
полезна

Ответы:

22

Вам нужно немного покопаться, чтобы увидеть, как словарь реализован в C # - он не так очевиден, как HashMap (хэш-таблица) или TreeMap (отсортированное дерево) (или ConcurrentSkipListMap - список пропуска ).

Если вы покопаетесь в разделе «Замечания»:

Универсальный класс Dictionary обеспечивает сопоставление набора ключей с набором значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Извлечение значения с использованием его ключа выполняется очень быстро, близко к O (1), поскольку класс Dictionary реализован в виде хеш-таблицы.

И там у нас это есть. Это хеш-таблица . Обратите внимание, что я связал там статью из Википедии - ее довольно хорошо читают. Вы можете прочитать раздел о разрешении коллизий. Можно получить патологический набор данных, в котором поиск переходит в O (N) (например, все, что вы вставляете, попадает в одно и то же хеш-значение или индекс в хеш-таблице, и у вас остается линейное зондирование ).

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

Что касается эффективности различных поиска / содержит?

  • Ходить по несортированному списку: O (N)
  • Двоичный поиск отсортированного массива: O (log N)
  • Сортированное дерево: O (log N)
  • Хеш-таблица: O (1)

Для большинства людей хеш-таблица - это то, что они хотят.

Вы можете обнаружить, что вместо этого вам нужен SortedDictionary :

SortedDictionary<TKey, TValue>Общий класс представляет собой бинарное дерево поиска с O (журнал п) извлечения, где п число элементов в словаре. В этом отношении он похож на SortedList<TKey, TValue>общий класс. Два класса имеют похожие объектные модели, и оба имеют O (log n) извлечения.

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

Сам словарь является абстрактным типом данных . Вы даете мне словарь, и я знаю, что я могу с ним сделать, и все инструменты там для меня, чтобы использовать его по природе, как словарь. Если бы вы дали мне ArrayList, я бы написал свой собственный код для поиска, вставки или удаления элементов из списка. Это напрасно тратит мое время, а также означает, что вероятность ошибки увеличивается, поскольку я копирую код снова и снова с места на место.

Роберт Харви
источник
5
O (1) не обязательно «быстро». Цикл по списку может все же быть быстрее, чем хеш-таблица для размеров коллекций, с которыми имеет дело приложение.
whatsisname
5
@whatsisname ни в коем случае не утверждаю, что O (1) быстр. Это, безусловно, имеет потенциал быть самым быстрым. Итерации по ключам хеш-таблицы медленнее, чем у ArrayList (если только вы не используете что-то вроде LinkedHashMap , предоставляемое Java). Важно знать ваши данные и их поведение, а также выбирать для них подходящую коллекцию, а если ее нет, запишите ее. Предполагая, конечно, что такие усилия действительно стоят времени (сначала профиль!).
Ваша цитата говорит: «Получение значения с использованием его ключа выполняется очень быстро, близко к O (1), потому что класс Dictionary реализован в виде хеш-таблицы.», Поэтому OP может спутать две концепции. Другими словами, я хотел прояснить, что большой О не рассказывает всей истории о «скорости».
whatsisname
3
@whatsisname, это напрямую от Microsoft. Использование ключа для поиска значения, если только у вас нет патологической хеш-таблицы (которая решает коллизии хеш-функций с помощью другого механизма), будет быстрее, чем поиск его в дереве или отсортированном списке (или несортированном списке). Java, например, использует линейное зондирование (шаг 1) для разрешения коллизий - что может быть медленнее в случаях, когда таблица переполнена или слишком много хэшей сталкиваются. Для общего случая это достаточно хорошо.
В качестве релевантного примера я недавно оптимизировал некоторый код на c ++, который изначально использовал хеш-таблицу для наборов данных из примерно 20 записей и занимал около 400 мс. Переключение на двоичное дерево снизило это до 200 мс, потому что дерево проще для доступа. Но я смог сократить его еще больше, используя массив пар имя-значение и эвристическую функцию поиска, которая догадалась, с чего начать поиск, основываясь на прошлых шаблонах доступа. Таким образом, все зависит от того, сколько существует данных и какой тип паттерна имеется в доступах (например, локальность).
Жюль