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

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

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

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

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

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

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

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

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

Итак, IDictionary реализации (те, которые поддерживают KeyValuePairs) являются: * коллекция Hashtable * Словарь * Парам * SortedDictionary

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

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

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

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

• Array,ArrayList и List все IList. Dictionary,SortedDictionary и Hashtable выполнить IDictionary.

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

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

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

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

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

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

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

подробнее о том, почему ArrayList и List на самом деле разные

массивы

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

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

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

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

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

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

опять же, самая большая помеха массивы-это то, что они не переизбираются. Они имеют "фиксированную" емкость. Введение ArrayList и List (of T) в нашу историю:

ArrayList-не общий список

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

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

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

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

List (of T): то, что ArrayList стал (и надеялся быть)

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

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

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

по существу, List (of T) является ArrayList, но лучше. Это "общий эквивалент" ArrayList. Как и ArrayList, он не гарантированно будет отсортирован до сортировки (go рисунок.) Список(Т) также имеет некоторые дополнительные функции.

Они довольно хорошо прописаны в intellisense. Просто введите

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

EDIT: на практике средняя временная сложность для поиска Hashtable / Dictionary составляет O(1).

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

важное замечание о Hashtable vs Dictionary для высокочастотной систематической торговой инженерии: проблема безопасности потоков

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

таким образом, Hashtable остается "стандартным" выбором в этом отношении.

вообще-то, я думаю MSDN обеспечивает довольно хорошие ответы на все эти вопросы. Просто посмотрите вверх .Чистый коллекций.

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

самые популярные структуры и коллекции данных C#

• массив
• ArrayList
• список
• LinkedList
• словарь
• HashSet
• стек
• очереди
• SortedList

C#.NET имеет много различных структур данных, например, одним из наиболее распространенных является массив. Однако C# поставляется со многими другими базовыми структурами данных. Выбор правильной структуры данных для использования является частью написания хорошо структурированного и эффективная программа.

в этой статье я рассмотрю встроенные структуры данных C#, в том числе новые, которые вводятся в C#.NET 3.5. Обратите внимание, что многие из этих структур данных применяются для других языков программирования.

массив

возможно, самой простой и наиболее распространенной структурой данных является массив. Массив C# - это в основном список объектов. Ее характерной особенностью является то, что все объекты одного типа (в большинстве случаев) и есть конкретная ряд из них. Природа массива обеспечивает очень быстрый доступ к элементам на основе их положения в списке (иначе известный как индекс). Массив C# определяется следующим образом:

[object type][] myArray = new [object type][number of elements]

примеры:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

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

ArrayList

структура данных C#, ArrayList, является динамическим массивом. Это означает, что ArrayList может иметь любое количество объектов и любого типа. Эта структура данных была разработана для упрощения процесса добавления новых элементов в массив. Под капотом ArrayList-это массив чей размер удваивается каждый раз, когда у него заканчивается пространство. Удвоение размера внутреннего массива является очень эффективной стратегией, которая уменьшает количество копирования элементов в долгосрочной перспективе. Мы не будем вдаваться в доказательства этого здесь. Структура данных очень проста в использовании:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

недостатком структуры данных ArrayList является то, что необходимо вернуть возвращенные значения в их исходный тип:

int arrayListValue = (int)myArrayList[0]

источники и дополнительную информацию вы можете найти здесь :

• Структуры Данных C#
• коллекции и структуры данных
• список против против против против интерфейса IQueryable интерфейс ICollection и IEnumerable интерфейс IDictionary