Foreversoft.ru

IT Справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Словарь си шарп

Словарь: класс Dictionary

представляет собой сложную структуру данных, позволяющую обеспечить доступ к элементам по ключу. Главное свойство словарей — быстрый поиск на основе ключей. Можно также свободно добавлять и удалять элементы, подобно тому, как это делается в List , но без накладных расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.

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

В .NET Framework предлагается несколько классов словарей. Главный класс, который можно использовать — это Dictionary .

Тип ключа

Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode() класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode().

Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. Мы не станем углубляться в подробности работы этого алгоритма. Единственное, что следует знать — это то, что он использует простые числа, так что емкость словаря всегда выражается простым числом.

Реализация метода GetHashCode() должна удовлетворять перечисленным ниже требованиям:

Один и тот же объект должен всегда возвращать одно и то же значение.

Разные объекты могут возвращать одно и то же значение.

Он должен выполняться насколько возможно быстро, не требуя значительных вычислительных затрат.

Он не должен генерировать исключений.

Он должен использовать как минимум одно поле экземпляра.

Значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int.

Хеш-код не должен изменяться на протяжении времени существования объекта.

Чем вызвана необходимость равномерного распределения значений хеш-кода по диапазону целых чисел? Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Понятно, что это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int.MinValue и int.MaxValue.

Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable .Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:

Если истинно А.Equals(В) , значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код.

Класс Dictionary

В классе Dictionary реализуются интерфейсы IDictionary, IDictionary , ICollection, ICollection >, IEnumerable, IEnumerable >, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости.

В классе Dictionary предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:

В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов.

В классе Dictionary определяется также ряд методов:

Add()

Добавляет в словарь пару «ключ-значение», определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException

ContainsKey()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false

ContainsValue()

Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false

Remove()

Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false

Кроме того, в классе Dictionary определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже:

Comparer

Получает метод сравнения для вызывающего словаря

Keys

Получает коллекцию ключей

Values

Получает коллекцию значений

Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа Dictionary .KeyCollection и Dictionary .ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.

Читать еще:  Рандом в си шарп

И наконец, в классе Dictionary реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary

Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в качестве индекса в данном случае служит ключ элемента, а не сам индекс. При перечислении коллекции типа Dictionary из нее возвращаются пары «ключ-значение» в форме структуры KeyValuePair . Напомним, что в этой структуре определяются два поля.

В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair не используется непосредственно, поскольку средства класса Dictionary позволяют работать с ключами и значениями по отдельности. Но при перечислении коллекции типа Dictionary , например, в цикле foreach перечисляемыми объектами являются пары типа KeyValuePair.

Давайте рассмотрим пример использования словарей:

Словарь на C++ как (Dictionary) на C#

На C# имеется удивительно быстрый словарь (Dictionary), хотелось бы узнать, а имеется ли такой же производительный только на C++ ? Пробовал unordered_map , hash_map , map , но производительность в разы ниже чем у Dictionary сишарповского. P.S: Пара имеет вид

4 ответа 4

На самом деле, сравнение языков — штука неблагодарная. Всегда найдутся тесты, на которых один из языков выиграет по сравнению с другим, и всегда найдутся люди, считающие, что данный тест не релевантен и подобный код никогда не будет встречаться в реальности.

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

Причиной такой разницы в производительности аллокатора является то, что объекты C++ невозможно перемещать в памяти, а значит, привычный алгоритм выделения памяти (который, как известно, поддерживает список свободных блоков, и ищет подходящий при аллокации) работает довольно медленно, и, хуже того, требует глобальной блокировки памяти (что ещё более ухудшает ситуацию в многопоточном сценарии). Кроме того, объекты в C++ имеют тенденцию освобождаться быстро как только можно, что приводит к дополнительной нагрузке на освобождение памяти, которое тоже требует глобальную блокировку.

В среде .NET же всё происходит по-другому. Объекты всегда выделяются на вершине heap-памяти, а значит, выделение не медленнее, чем InterlockedIncrement . .NET’у не нужно поддерживать список свободных блоков потому, что при сборке мусора происходит компактификация heap-памяти: объекты перемещаются, заполняя «дыры».

Кроме того, известия о том, что код на C++ вполне может быть медленнее аналогичного кода на C#, давно не новость. Вот, например, замечательная серия статей о простом приложении от мастеров нативного программирования, и резюме Джефа Этвуда:

Чтобы обойти по производительности версию на C#, Реймонду пришлось написать собственные процедуры ввода-вывода, переписать класс string , воспользоваться кастомным аллокатором, а также собственной процедурой отображения кодовых страниц.

Это подтверждается и бенчмарком, который приведён ниже: нативные контейнеры «из коробки» существенно проигрывают дотнетовским, (некоторые) самописные контейнеры выигрывают.

Теперь самое интересное: измерения.

Результаты измерений (release mode, 5 запусков подряд без отладчика):

elapsed time = 1138 ms, dictionary entries count = 10000000
elapsed time = 1127 ms, dictionary entries count = 10000000
elapsed time = 1133 ms, dictionary entries count = 10000000
elapsed time = 1134 ms, dictionary entries count = 10000000
elapsed time = 1129 ms, dictionary entries count = 10000000

elapsed time = 8377 ms, dictionary entries count = 10000000
elapsed time = 8408 ms, dictionary entries count = 10000000
elapsed time = 8377 ms, dictionary entries count = 10000000
elapsed time = 8377 ms, dictionary entries count = 10000000
elapsed time = 8361 ms, dictionary entries count = 10000000

Среднее время: C# = 1132 мс, C++ = 8379 мс.

Я не утверждаю, что мои тесты идеальны. Кроме того, они релевантны лишь на моём компьютере. Если кто-то предложит лучшую методику измерения, я с удовольствием применю её тоже. Тем не менее, в моих условиях производительность System.Collections.Generic.Dictionary на добавление элементов существенно превосходит производительность std::map .

Обратите внимание, что Dictionary использует хэш-таблицы, в то время как std::map в моей имплементации использует красно-чёрное дерево в качестве несущей структуры данных. Хэш-таблицы обычно сами по себе быстрее, так что скорость аллокации — не единственная причина лучшей скорости у Dictionary .

Замена в C++ std::map на std::unordered_map по совету @Котик привела к значительному ускорению: 2230/2230/2230/2230/2246 (среднее 2233). Тем не менее, C++ всё ещё почти вдвое медленнее.

Заменил в C++ std::unordered_map на uthash по совету @igumnov. Результат немного хуже, чем std::unordered_map : 2963/2932/2948/2948/2932. Код:

Добавил capacity = 10000000 в C++ и для честного сравнения в C# тоже. Изменения:

Действительно, стало скорее:

  • C++: 1826/1856/1857/1841/1825, среднее 1841
  • C#: 790/786/801/790/791, среднее 792

По-прежнему C# более чем вдвое впереди.

По совету @KoVadim убрал вычисление seed (capacity оставил), теперь рабочий цикл таков:

  • C++: 1498/1514/1498/1498/1498, среднее 1501
  • C#: 129/129/135/133/132, среднее 132
Читать еще:  Паскаль размерность в си

По совету @igumnov добавил в бенчмарк khash. Код:

Результат: 577/577/608/577/577, среднее 583, массивный вин для нативного кода. Напомню, что лучший результат стандартного .NET-контейнера — 792 мс.

Кто предложит кастомный контейнер под .NET?

Попробовал имплементацию для .NET FastDictionary (проект MapReduce.NET). Получилось немного медленнее, чем встроенный Dictionary : 853/865/842/841/842, среднее 849.

  • C#: 58/54/28/55/55 (среднее 50)
  • C++: 407.719/400.693/401.674/401.926/399.976 (среднее 402.4)

Под капотом у Dictionary и ConcurrentDictionary

Некоторое время назад, я решил, что хочу знать больше подробностей о работе многопоточности в .NET и что я уделял этому незаслуженно мало внимания в прошлом. Информации на эту тему великое множество (отправной точкой я для себя выбрал этот раздел книги «C# in a nutshell»), но, как оказалось, только малая часть ресурсов пытаются объяснить что-то в деталях.

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

Итак, поехали.

Если вы уже знакомы с самим Dictionary, то можете пропустить следующий раздел.

Что такое Dictionary ?

Dictionary представляет собой реализацию стандартной Hashtable.
Здесь интересны следующие функции:

Инициализация

Инициализация происходит либо при создании (если передана начальный размер коллекции), либо при добавлении первого элемента, причем в качестве размера будет выбрано ближайшее простое число (3). При этом создаются 2 внутренние коллекции — int[] buckets и Entry[] entries. Первая будет содержать индексы элементов во второй коллекции, а она, в свою очередь, — сами элементы в таком виде:

Добавление элементов

При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции:

Выглядеть это будет примерно так:

Затем проверяется нет ли уже такого ключа в коллекции, если есть — то операция Add выбросит исключение, а присваивание по индексу просто заменит элемент на новый. Если достигнут максимальный размер словаря, то происходит расширение (выбирается новый размер ближайшим простым числом).
Сложность оперции соответственно — O(n).

Если происходит коллизия (то есть в корзине с индексов bucketNum уже есть элемент), то новый элемент добавляется в коллекцию, его индекс сохраняется в корзине, а индекс старого элемента — в его поле next.

Таким образом получаем однонаправленный связный список. Данный механизм разрешения коллизий называется chaining. Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии.

Удаление элементов

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

Сложность снова O(1) или O(n) в случае коллизии.

Другое

Так же стоит отметить 2 момента:
1) При очистке словаря, его внутренний размер не изменяется. То есть, потенциально, вы просто тратите место.
2) GetEnumerator просто возвращает итератор по коллекции entires (сложность O(1)). Если вы только добавляли элементы — они вернутся в том же порядке. Однако если вы удаляли элементы и добавляли новые — порядок соответственно изменится, поэтому на него полагаться не стоит (тем более, что в будущих версиях фреймворка это может измениться).

Так и что же с ConcurrentDictionary?

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

В Microsoft пошли более оптимальным путем и Dictionary притерпел некоторые изменения. Так, благодаря внутренней структуре словаря и его корзин, блокировка осуществляется по ним, с помощью метода

В то же время обычный словарь не смог бы работать с этой схемой, потому что все корзины используют один и тот же массив entries, поэтому корзины стали представлять собой обычный single linked list: volatile Entry[] m_buckets (поле объявлено как volitale, чтобы обеспечить неблокирующую синхронизацию в ситуации когда один поток пытается выполнить какую-то операцию, а другой в этот момент изменяет размер коллекции).

В итоге корзины стали выглядеть вот так:

lockNo — это индекс в новом массиве, который содержит объекты синхронизации — object[] m_locks. Его использование позволяет разным потокам изменять разные корзины в одно и то же время. Размер этой коллекции зависит от параметра ConcurrencyLevel который можно задать через конструктор. Он определяет примерное число потоков которые будут одновременное работать с коллекцией (по умолчанию это число_процессоров * 4). Чем выше это значение, тем проще будут происходить операции записи, но так же станут гораздо дороже операции, которые требуют полной блокировки всей коллекции (Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear). Также этот параметр определяет сколько элементов коллекции приходится на один lock (как отношение числа корзин к размеру этой коллекции) и когда элементов становится больше, чем надо — коллекция расширяется, потому что в противном случае поиск элемента требует не O(1), а уже O(n) за счет обхода связных списков. Чтобы немного снизить число первоначальных расширений коллекции, начальный размер словаря уже не 3, а 31.

Читать еще:  Язык си логические операции

Все операции приобрели вид:

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

Впрочем, для некоторых операций блокировка не нужна в принципе — это TryGetValue, GetEnumerator, ContainsKey и индексация. Почему? Потому что все изменения размера корзин видны за счет того что поле volatile, любые добавления или изменения элементов происходят путем создания нового элемента и замены им старого, а удаления происходят просто заменой указателя на следующий узел.

Другое

лучше использовать dictionary.Select(x => x.Value).ToArray(), чем dictionary.Values.ToArray()

И это не совсем верно — вместо «лучше» тут должно быть «быстрее» — за счет отсутствия блокировок, но надо принять во внимание, что данные подходы могут вернуть разные данные.

Dictionary

Дата изменения: 09.10.2017

Класс Dictionary представляет словарь, таблицу состоящую из пар ключ/значение.

Коллекция динамическая, способная изменять свой размер при добавлении/удалении элемента. Доступ к каждому элементу производится по ключу. Коллекция объявлена в пространстве имен System.Collections.Generic и является универсальной, это главное ее отличии от коллекции Hashtable в остальном их функционал идентичен.

Класс реализует следующие интерфейсы:

Чтобы понять реализацию доступа по ключу к значениям в таблице необходимо рассмотреть структуру самого элемента таблицы.

Структура элемента таблицы

У каждого элемента словаря есть индекс. Но добавление и удаление элементов из словаря производится по ключу. Только ключ однозначно идентифицирует элемент. Для того что ассоциировать индекс с нужным значением вычисляется хеш-код.

Хеш-код вычисляется на основе ключа и является числовой ассоциацией между индексом и значением элемента. Как только хеш-код вычислен в индекс помещается ссылка на значение элемента.

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

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

Сам тип элемента – это KeyValuePair , структура. Ее, например возвращает индексатор при использовании.

Создание объекта класса и инициализация

Для создания объекта класса Dictionary предусмотрено 7 разных конструкторов. Все их рассматривать не имеет смысла, поскольку, они различаются типом инициализации, их применения похоже на применение конструкторов IList .

Самые распространенные способы создания и инициализации объекта:

Начиная с версии С# 5.0 допустима инициализация готовыми парами значений:

6.0 версия языка допускает следующий вид инициализации:

Члены класса и их использование

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

Методы общего назначения:

Add() и Remove() – служат, чтобы добавлять или удалять элемент(пару ключ/значение) в коллекцию или удалять из нее, соотвественно;

ContainsKey() и ContainsValue() – проверяют содержится ли в словаре указанный им в параметре ключ или значение. Если содержится возвращают true, иначе false.

При попытке добавить в коллекцию элемент с уже существующим ключом будет сгенерировано исключение. Поэтому блок с использованием метода Add нужно изолировать конструкцией try/catch.

Метод Remove производит удаления ключа, если такого ключа в коллекции нет, то метод вернет false, иначе – удалит и вернет true.

Кроме того, класс содержит три собственных свойства:

  • Values – возвращает значение из структуры элемента;
  • Keys – возвращает ключ;
  • Comparer – указывает компаратор (метод сравнения);

Для автоматического добавления новых пар в коллекцию в классе предусмотрен индексатор. Но работает он не на основе индекса, а на основе ключа. Вот его сигнатура:

При использовании он работает с парами значение/ключ как со структурой KeyValuePair .

Использование свойств и методов класса демонстрируется в следующем примере:

Ссылка на основную публикацию
Adblock
detector