.Net Dictionary <int, int> исключение из памяти около 6 000 000 записей

Ответ 1

Обновление: Учитывая образ образца выборки OP, кажется, что максимальное количество элементов будет более 16 миллионов, а очевидно, даже это слишком много выделяется при создании словаря. Здесь я вижу три варианта:

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

Предыдущий ответ: проблема заключается в том, что вы не выделяете достаточно места для своего словаря. В какой-то момент, когда он расширяется, вы просто исчерпали память для расширения, но не обязательно для нового словаря.

Пример: у этого кода заканчивается память почти на 24 миллиона записей (на моем компьютере, работающем в 32-битном режиме):

Dictionary<int, int> count = new Dictionary<int, int>();
for (int i = 0; ; i++)
     count.Add(i, i);

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

Теперь, если мы изначально выделяем пространство для, скажем, 40 миллионов записей, оно работает без проблем:

Dictionary<int, int> count = new Dictionary<int, int>(40000000);

Поэтому попробуйте указать, сколько записей будет при создании словаря.

Из MSDN:

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

Ответ 2

Каждая запись словаря содержит два 4-байтовых целых числа: всего 8 байтов. 8 байтов * 6 миллионов записей - это всего лишь около 48 МБ, +/- некоторое пространство для накладных расходов объекта, выравнивание и т.д. Для этого достаточно места в памяти..Net обеспечивает виртуальное адресное пространство до 2 GB для каждого процесса. 48 МБ или около того не должно вызывать проблем.

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

Во-первых, автоматически расширяющаяся часть. В прошлый раз, когда я проверил (назад около .Net 2.0 ^*), коллекции в .Net обычно использовали массивы. Они назначили массив размером в конструкторе коллекции (например, 10 элементов), а затем использовали алгоритм удвоения для создания дополнительного пространства всякий раз, когда массив заполнялся. Все существующие элементы должны быть скопированы в новый массив, но тогда старый массив может быть собран в мусор. Сборщик мусора довольно надежен по этому поводу, и поэтому это означает, что вы оставите пространство в размере не более 2n - 1 элементов в коллекции.

Теперь часть уплотнения сборщика мусора. После определенного размера эти массивы попадают в секцию памяти, называемую кучей больших объектов. Мусорная коллекция все еще работает здесь (хотя и реже). Что здесь действительно не работает, это уплотнение (дефрагментация памяти). Физическая память, используемая старым объектом, будет выпущена, возвращена в операционную систему и доступна для других процессов. Однако виртуальное адресное пространство вашего процесса... таблица, которая отображает смещения памяти программы на адреса физической памяти, по-прежнему будет иметь (пустое) пространство.

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

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

Следующее мое предложение состоит в группировать цвета пикселей. Человек не может сказать и не волнует, если два цвета всего лишь один бит друг от друга в любом из компонентов rgb. Вы можете взглянуть на отдельные значения RGB для каждого пикселя и нормализовать пиксель, чтобы вы заботились только об изменениях более 5 или около того для значения R, G или B. Это даст вам от 16,5 миллионов потенциальных цветов вплоть до примерно 132 000, и данные, вероятно, будут более полезными. Это может выглядеть примерно так:

var colorCounts = new Dictionary<Color, int>(132651);
foreach(Color c in GetImagePixels().Select( c=> Color.FromArgb( (c.R/5) * 5, (c.G/5) * 5, (c.B/5) * 5) )
{
    colorCounts[c] += 1;
}

^{* IIRC, где-то в недавней или будущей версии .Net оба этих вопроса рассматриваются. Один из них позволяет вам принудительно сжимать LOH, а другой - с помощью набора массивов для хранилищ, поддерживающих коллекцию, вместо того, чтобы пытаться сохранить все в одном большом массиве}

Ответ 3

Предел максимального размера, предоставляемого CLR, составляет 2 ГБ

При запуске 64-разрядного управляемого приложения в 64-битной Windows операционной системы, вы можете создать объект размером не более 2 гигабайт (ГБ).

Вы можете лучше использовать массив.

Вы также можете проверить этот BigArray<T>, обойти ограничение размера массива 2 ГБ

Ответ 4

В 32-битной среде исполнения максимальное количество элементов, которое вы можете иметь в Dictionary<int, int>, находится в районе 61,7 миллиона. Для получения дополнительной информации см. мою старую статью.

Если вы работаете в 32-битном режиме, то все ваше приложение, а также любые биты ASP.NET и базового оборудования, все должны вписываться в память, доступную вашему процессу: обычно 2 ГБ в 32-битном во время выполнения.

Кстати, действительно дурацкий способ решить вашу проблему (но я бы не рекомендовал, если вы на самом деле не вредите памяти), будет следующим (предполагая 24-битное изображение):

• Вызовите LockBits, чтобы получить указатель на данные необработанного изображения.
• Сжатие строки для каждой строки сканирования, перемещая данные для каждой строки сканирования, чтобы заполнить предыдущую строку. В итоге вы получаете массив из 3-байтовых значений, за которым следует пучок пустого пространства (для выравнивания).
• Сортировка данных изображения. То есть сортируйте 3-байтовые значения. Вам придется писать пользовательский вид, но это было бы не так уж плохо.
• Пройдите последовательно через массив и подсчитайте количество уникальных значений.
• Выделите 2-мерный массив: int[count,2], чтобы удерживать значения и их количество вхождения.
• Продолжайте последовательно через массив, чтобы подсчитать вхождения каждого уникального значения и заполнить массив counts.

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

Ответ 5

Попробуйте использовать массив. Я сомневаюсь, что у него закончится память. 6 миллионов элементов массива int не имеют большого значения.