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




performance generics (8)

Список использует массив внутри, а словарь использует хеш-таблицу.

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

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

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

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

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

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

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

Любые идеи / предложения?

Изменить: я знаю основные базовые структуры данных 101 и почему Linked List лучше добавлять / удалять, а HashTable лучше для Random Access.

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

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

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

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


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


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

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


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


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

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

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

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

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


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

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


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


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

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





memory