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

StackOverflow https://stackoverflow.com/questions/128636

Вопрос

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

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

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

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

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

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

Это было полезно?

Решение

С верхней части моей головы:

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

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

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

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

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

Итак, реализации IDictionary (поддерживающие KeyValuePairs):* Hashtable * Словарь * SortedList * 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.

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

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

Массивы

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

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

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

Массивы могут быть одномерными, многомерными или составными (о зубчатых массивах стоит прочитать).Сами массивы не являются динамическими:после инициализации массив н размер оставляет достаточно места для хранения н количество объектов.Количество элементов в массиве не может увеличиваться или уменьшаться. 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 фиксированного размера, поскольку ArrayLists (по сравнению с Arrays) в этом случае работают заметно медленнее.

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

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

Список (из Т):Чем стал ArrayList (и надеялся стать)

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

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

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

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

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

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

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

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

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

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

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

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

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

На самом деле, я думаю MSDN помогает дать довольно хорошие ответы на все эти вопросы.Просто найдите коллекции .NET.

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

  • Множество
  • ArrayList
  • Список
  • Связанный список
  • Словарь
  • Хэшсет
  • Куча
  • Очередь
  • Сортированный список

С#.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 };

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

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]

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top