Структуры данных .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Скорость, память и когда их использовать?

Question

.NET имеет много сложных структур данных. К сожалению, некоторые из них очень похожи, и я не всегда уверен, когда использовать один, а когда использовать другой. Большинство моих книг по C # и Visual Basic в определенной степени рассказывают о них, но они никогда не вдавались в подробности.

В чем разница между Array, ArrayList, List, Hashtable, Dictionary, SortedList и SortedDictionary?

Какие из них перечислимы (IList - может делать циклы 'foreach')? Какие из них используют пары ключ / значение (IDict)?

А как насчет памяти? Скорость вставки? Скорость поиска?

Есть ли еще какие-либо структуры данных, о которых стоит упомянуть?

Я все еще ищу дополнительную информацию об использовании памяти и скорости (обозначение Big-O).

Answer 1

с макушки головы:

• Array* - представляет массив памяти старой школы - своего рода псевдоним для обычного type[] массива. Могу перечислить. Не может расти автоматически. Я бы предположил очень быструю скорость вставки и восстановления.

• ArrayList - автоматически растущий массив. Добавляет больше накладных расходов. Может перечислять, возможно, медленнее, чем обычный массив, но все еще довольно быстро. Они часто используются в .NET

• List - один из моих избранных - можно использовать с дженериками, так что вы можете иметь строго типизированный массив, например, List<string>. Кроме того, действует очень похоже на ArrayList

• Hashtable - простая старая хэш-таблица. От O (1) до O (n) в худшем случае. Может перечислять значения и свойства ключей, а также делать пары ключ / вал

• Dictionary - то же самое, что и выше, только строго набирается через дженерики, такие как Dictionary<string, string>

• SortedList - отсортированный общий список. Замедлен на вставке, так как он должен выяснить, куда положить вещи. Может перечислять, вероятно, то же самое при извлечении, так как не нужно прибегать к нему, но удаление будет медленнее, чем обычный старый список.

Я склонен использовать List и Dictionary все время - как только вы начнете использовать их строго типизированные с генериками, действительно трудно вернуться к стандартным неуниверсальным.

Есть также много других структур данных - есть KeyValuePair, который вы можете использовать для некоторых интересных вещей, есть SortedDictionary, который также может быть полезен.

Answer 2

Если возможно, используйте дженерики. Это включает в себя:

• Список вместо ArrayList
• Словарь вместо HashTable

Answer 3

Во-первых, все коллекции в .NET реализуют IEnumerable.

Во-вторых, многие коллекции являются дубликатами, потому что дженерики были добавлены в версии 2.0 платформы.

Итак, хотя общие коллекции скорее всего добавляют функции, по большей части:

• List - это общая реализация ArrayList.
• Словарь - это обобщенная реализация Hashtable

Массивы - это коллекции фиксированного размера, в которых вы можете изменить значение, хранящееся в данном индексе.

SortedDictionary - это IDictionary, который сортируется на основе ключей. SortedList - это IDictionary, который сортируется на основе требуемого IComparer.

Итак, реализации IDictionary (те, которые поддерживают KeyValuePairs): * Хеш-таблица * Толковый словарь * SortedList * SortedDictionary

Еще одна коллекция, добавленная в .NET 3.5, - это Hashset. Это коллекция, которая поддерживает операции над множествами.

Кроме того, LinkedList - это стандартная реализация связанного списка (список - это список массивов для более быстрого поиска).

Answer 4

Хорошая шпаргалка с указанием сложностей для структур данных, алгоритмов и т. Д.

Answer 5

Вот несколько общих советов для вас:

• Вы можете использовать foreach для типов, которые реализуют IEnumerable. IList - это, по сути, IEnumberable со свойствами Count и Item (доступ к элементам с использованием индекса, начинающегося с нуля). IDictionary, с другой стороны, означает, что вы можете получить доступ к элементам по любому хеш-индексу.

• Array, ArrayList и List все орудия IList. Dictionary, SortedDictionary и Hashtable агрегат IDictionary.

• Если вы используете .NET 2.0 или выше, рекомендуется использовать универсальные аналоги упомянутых типов.

• В отношении временной и пространственной сложности различных операций над этими типами следует обратиться к их документации.

• .NET структуры данных находятся в System.Collections пространстве имен. Существуют библиотеки типов, такие как PowerCollections , которые предлагают дополнительные структуры данных.

• Чтобы получить полное представление о структурах данных, обратитесь к таким ресурсам, как CLRS .

Answer 6

.NET структуры данных:

Еще к разговору о том, почему ArrayList и List на самом деле отличаются

Массивы

Как утверждает один пользователь, массивы - это коллекция "старой школы" (да, массивы считаются коллекцией, хотя и не являются частью System.Collections). Но что такое «старая школа» в отношении массивов по сравнению с другими коллекциями, т. Е. Теми, которые вы перечислили в своем заголовке (здесь ArrayList и List (Of T))? Давайте начнем с основ, посмотрев на массивы.

Для начала, Массивы в Microsoft .NET - это «механизмы, позволяющие обрабатывать несколько [логически связанных] элементов как одну коллекцию» (см. Связанную статью). Что это значит? Массивы хранят отдельные элементы (элементы) последовательно, один за другим в памяти с начальным адресом. Используя массив, мы можем легко получить доступ к последовательно хранимым элементам, начиная с этого адреса.

Помимо этого и вопреки программированию 101 общей концепции, массивы действительно могут быть довольно сложными:

Массивы могут быть одномерными, многомерными или зазубренными (о неровных массивах стоит прочитать). Сами массивы не являются динамическими: после инициализации массив размером n резервирует достаточно места для хранения n количества объектов. Количество элементов в массиве не может увеличиваться или уменьшаться. Dim _array As Int32() = New Int32(100) резервирует достаточно места в блоке памяти для массива, чтобы он содержал 100 объектов примитивного типа Int32 (в этом случае массив инициализируется, чтобы содержать 0 с). Адрес этого блока возвращается к _array.

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

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

Опять же, самым большим препятствием для массивов является то, что они не могут быть изменены. Они имеют «фиксированную» емкость. Представляем ArrayList и List (Of T) в нашей истории:

ArrayList - неуниверсальный список

ArrayList (наряду с List(Of T) - хотя здесь есть некоторые критические различия, объясненные ниже) - возможно, лучше всего рассматривать как следующее дополнение к коллекциям (в широком смысле). ArrayList наследуется от интерфейса IList (потомок ICollection). ArrayLists сами по себе громоздкие - требуют больше служебных данных - чем списки.

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

Из моего чтения ArrayLists не может быть зубчатым: «Использование многомерных массивов в качестве элементов ... не поддерживается». Опять еще один гвоздь в гробу ArrayLists. Списки ArrayList также не являются «типизированными» - это означает, что ArrayList, расположенный под всем, представляет собой просто динамический массив объектов: Object[]. Это требует много коробок (неявных) и распаковок (явных) при реализации ArrayLists, что снова увеличивает их накладные расходы.

Необоснованная мысль: мне кажется, я помню, как читал или слышал от одного из моих профессоров, что ArrayLists являются своего рода ублюдочным концептуальным потомком попытки перейти от массивов к коллекциям типа списка, то есть когда-то будучи Это большое улучшение для массивов, они больше не лучший вариант, так как дальнейшее развитие было сделано в отношении коллекций

Список (Of T): каким ArrayList стал (и надеялся)

Разница в использовании памяти достаточно значительна, поскольку List (Of Int32) потребляет на 56% меньше памяти, чем ArrayList, содержащий тот же тип примитива (8 МБ против 19 МБ в приведенной выше демонстрации связанных джентльменов: опять же, связанный здесь ) - хотя это результат, составленный 64-битной машиной. Это различие действительно демонстрирует две вещи: во-первых (1) «объект» в виде типа Int32 (ArrayList) в штучной упаковке намного больше, чем чистый тип примитива Int32 (List); во-вторых (2), разница является экспоненциальной в результате внутренней работы 64-битной машины.

Итак, в чем разница и что такое List (Of T) ? MSDN определяет List(Of T) как "... строго типизированный список объектов, к которым можно получить доступ по индексу". Здесь важен бит «строго типизированный»: List (Of T) «распознает» типы и сохраняет объекты как их типы. Таким образом, Int32 сохраняется как Int32, а не как Object. Это устраняет проблемы, вызванные боксом и распаковкой.

MSDN указывает, что это различие вступает в силу только при хранении примитивных типов, а не ссылочных типов. Слишком различие действительно имеет место в большом масштабе: более 500 элементов. Что еще интереснее, документация MSDN гласит: «В ваших интересах использовать реализацию класса List (Of T) для конкретного типа вместо использования класса ArrayList ....»

По сути, List (Of T) - это ArrayList, но лучше. Это «универсальный эквивалент» ArrayList. Как и ArrayList, сортировка не гарантируется, пока не будет отсортирована (см. Рисунок). Список (Of T) также имеет некоторые дополнительные функции.

Answer 7

Я сочувствую вопросу - я тоже нашел (нахожу?) Этот выбор изумительный, поэтому я с научной точки зрения решил выяснить, какая структура данных самая быстрая (я провел тест с использованием VB, но я думаю, что C # будет таким же, поскольку оба языка делают одно и то же на уровне CLR). Вы можете увидеть некоторые результаты сравнительного анализа, проведенные мной здесь (также есть обсуждение того, какой тип данных лучше использовать в каких обстоятельствах).

Answer 8

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

Answer 9

Хеш-таблицы / словари имеют производительность O (1), что означает, что производительность не зависит от размера. Это важно знать.

РЕДАКТИРОВАТЬ: На практике средняя сложность времени для поиска Hashtable / Dictionary <> составляет O (1).

Answer 10

Они хорошо прописаны в intellisense. Просто введите System.Collections. или System.Collections.Generics (предпочтительно), и вы получите список и краткое описание того, что доступно.