.Net 2.0 - Насколько эффективны общие списки?

Question

Я создаю приложение, которое хранит множество пользовательских данных в памяти, и в основном оно хранит все это в структурах List (и некотором словаре , когда мне нужен поиск).

И мне интересно ...

Насколько эффективны списки? Сколько памяти я получу за каждого из них? (то есть пространство памяти в дополнение к тому, что занимают содержащиеся в них объекты) Сколько штрафа я плачу каждый раз, когда я устанавливаю новый экземпляр?

Есть ли более эффективный способ?

Словари - это просто HashTables, верно? Или это менее эффективная структура данных?

Я бы хотел использовать массивы, но у меня есть типичная проблема добавления и удаления вещей из них все время, поэтому необходимость увеличивать / уменьшать их было бы болезненно.

Есть идеи / предложения?

---

Редактировать: я знаю свои базовые структуры данных 101, и почему Связанный список лучше добавлять / удалять, а HashTable лучше для произвольного доступа.

Меня больше всего волнует идиосинкразия .Net. Сколько памяти тратит каждая из этих структур, например. И время было потрачено на их инициализацию / убийство.

Такие вещи, как, например, если создание экземпляра / GC a List занимает много времени, но не так много, чтобы его очистить, может быть, мне следует оставить небольшой пул списков в ожидании меня, очистить их и отправить обратно когда закончите, вместо того, чтобы просто разыменовывать их.

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

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

Answer 1

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

Answer 2

Если вы действительно хотите увидеть все подробности реализации List <> и Dictionary <,>, используйте удивительно полезный .NET Reflector .

См. Также документацию для превосходной универсальной библиотеки коллекций C5 , которая имеет очень хорошие реализации ряда типов коллекций, отсутствующих в BCL.

Answer 3

Для добавления и удаления объекта LinkedList потребуется меньше времени из-за природы связанных списков. Когда вы добавляете элемент, ему не нужно изменять размер массива, как это делает обычный список. Помимо этого улучшения, я подозреваю, что LinkedList будет работать примерно так же, как обычный список.

Смотрите это в Википедии: Связанные списки и массивы

Answer 4

Если вам нужна эффективность при вставке или удалении случайных мест в списке, существует структура данных LinkedList - в статье MSDN приведены подробности. Очевидно, что произвольный доступ из связанного списка не эффективен.

Answer 5

List использует массив для внутреннего использования, а Dictionary использует хеш-таблицу.

Они быстрее, чем старые неуниверсальные классы ArrayList и HashTable, потому что у вас нет затрат на преобразование всего в / из объекта (бокс, распаковка и проверка типов), а также потому, что MS оптимизировала их лучше, чем старые классы.

Answer 6

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

В противном случае они будут в основном такими же быстрыми, как массив.

Answer 7

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

• Все находится на диске, независимо от того, что
• Данные блокируются на «чанки»; каждый кусок знает, когда к нему последний раз обращались
• Куски перетаскиваются с диска в память, когда они необходимы
• Поток с низким приоритетом отслеживает использование памяти и удаляет наименее использованные материалы

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

Имейте в виду, что все в приложении .NET должно умещаться в пределах 2 ГБ памяти, и из-за того, как работает GC, и из-за накладных расходов вашего приложения, у вас, вероятно, есть несколько меньше, чем для работы.

Чтобы точно узнать, как выглядит ваша куча и кто ее выделяет, используйте CLR profiler : http://www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en

Answer 8

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

Ключ должен использовать FILE_FLAG_NO_BUFFERING и всегда читать / записывать данные только одного сектора.

Answer 9

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

Answer 10

.Net List не использует связанный список. Это массив, он начинается с 4 позиций по умолчанию, и я думаю, что он удваивается по мере добавления. Поэтому производительность может немного отличаться в зависимости от того, как вы ее используете.

---

Если вы используете VS 2008, запустите профилировщик, прежде чем вы окажетесь слишком далеко в этой крысиной норе. Когда мы на самом деле начали смотреть на то, где мы теряем время, это не заняло много времени, чтобы понять, что обсуждение тонкостей связанных списков просто не имеет значения.