Знайте свои структуры данных - List vs Dictionary vs HashSet
Есть ли случаи, когда не имеет значения, как структурированы ваши данные, если вы выполняете поставленную задачу? Или всегда важно использовать идеальную структуру данных для работы? Давайте разберемся!
У этих коллекций совершенно разные цели и варианты использования. В частности, списки следует использовать, когда все, что вам нужно сделать, это перечислить элементы или получить к ним случайный доступ через индекс.
Списки очень похожи на простые массивы. По сути, они представляют собой массив элементов, которые увеличиваются при превышении его текущей емкости. Это стандартная и, пожалуй, самая используемая коллекция. Доступ к элементам можно получить произвольно с помощью оператора [] в постоянное время. Добавление или удаление в конце также стоит O (1), кроме случаев, когда емкость превышена. Выполнение этого в начале или в середине требует, чтобы все элементы были перемещены.
Словари и HashSets - это специализированные коллекции, предназначенные для сценариев быстрого поиска. По сути, они сопоставляют элемент с ключом, построенным с использованием хеш-функции. Позже этот ключ можно использовать для быстрого получения связанного элемента.
У них обоих более или менее одинаковая асимптотическая сложность для всех операций. Настоящая разница заключается в том, что с помощью Dictionary мы можем создавать пары ключ-значение (с уникальными ключами), а с HashSet мы сохраняем неупорядоченный набор уникальных элементов.
Также чрезвычайно важно отметить, что при использовании HashSets элементы должны правильно реализовывать GetHashCode () и Equals ().
Вместо этого в словарях это очевидно необходимо для типа, используемого в качестве ключа.
Я написал очень маленькое приложение для профилирования, чтобы проверить время поиска List, Dictionary и Hashset. Давайте кратко рассмотрим, что это за коллекции. Сначала он генерирует массив Guids и использует его в качестве исходного набора данных при выполнении тестов.
Код написан на C # с использованием .NET Core 2.2 и был выполнен на Macbook Pro в середине 2012 года. Вот что у меня получилось:
СОЗДАНИЕ КОЛЛЕКЦИИ
Списки здесь работают определенно лучше, вероятно, потому, что словари и HashSets должны оплачивать стоимость создания хеша, используемого в качестве ключа для каждого добавленного элемента.
СОЗДАНИЕ КОЛЛЕКЦИИ И ПРОСМОТР
Здесь начинается интересное: первый случай показывает производительность создания и однократного поиска. Более или менее те же характеристики, что и у простого создания. Во втором случае поиск выполняется 1000 раз, что дает чистый выигрыш для Dictionary и HashSets. Очевидно, это связано с тем, что поиск в списке занимает линейное время (O (n)), вместо этого будучи постоянным (O (1)) для двух других структур данных.
ПОСМОТРЕТЬ ОТДЕЛЬНЫЙ ПРЕДМЕТ
В этом случае словари и HashSet выигрывают в обоих исполнениях, потому что коллекции были заполнены ранее.
ПОСМОТРЕТЬ ГДЕ ()
В последнем примере система перебирает существующий набор данных и выполняет поиск текущего элемента. Как и ожидалось, словари и HashSet работают определенно лучше, чем List.
Легко видеть, что почти во всех случаях не имеет значения, какая структура данных используется, если набор данных относительно небольшой, менее 10000 элементов. Единственный случай, когда выбор имеет значение, - это когда нам нужно пересечь две коллекции и выполнить поиск.
эта статья была опубликована также в моем блоге: https://www.davideguida.com/know-your-data-structures-list-vs-dictionary-vs-hashset/
