C # словарь для большого количества предметов

Question

Я хотел бы понять стоимость хранения большого количества элементов в памяти в C #. Структура данных, которую мне нужно использовать, это словарь или аналогичный. Допустим, количество предметов, которые я хотел бы иметь, составляет около 100 миллионов, но приложение не сразу достигнет этого числа. Это займет много времени, пока мы не достигнем предела.

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

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

Это разумный подход? Мой анализ правильный или словарь C # будет работать лучше, я думаю по какой-то причине? Есть ли другое решение, которое было бы лучше? Я ищу структуру данных, которая имеет ту же сложность времени, что и словарь C #.

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

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

Должно быть возможно разместить все элементы в памяти. Элементы маленькие, около 50 байтов данных каждый. Поэтому структура данных не должна иметь слишком много накладных расходов для каждого элемента.

Answer 1

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

Answer 2

ОБНОВЛЕНИЕ: я редактировал это, так как я отправил это:

• Хранить объект фиксированного размера (байт [50] с каждым проходом,
• предварительно выделите все это перед добавлением в словарь (вместо создания объектов в цикле)
• запустите GC.Collect () после предварительного выделения материала.
• gcAllowVeryLargeObjects установлено в true.
• определенно установлен для x64 (это было раньше, но потом я переключился на 'Release', чтобы собрать и запустить вне VS ... и он сбросился, так что упс.)
• пробовал с предварительным выделением размера словаря и без него.

Вот код сейчас:

var arrays = new byte[100000000][];
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
for (var i = 0; i<100000000; i++)
{
    arrays[i] = new byte[50];
}
stopwatch.Stop();
Console.WriteLine($"initially allocating arrays took {stopwatch.ElapsedMilliseconds} ms");
stopwatch.Restart();

GC.Collect();
Console.WriteLine($"GC after array allocation took {stopwatch.ElapsedMilliseconds} ms");

Dictionary<int, byte[]> dict = new Dictionary<int, byte[]>(100000000);
//Dictionary<int, byte[]> dict = new Dictionary<int, byte[]>();

for (var c = 0; c < 100; c++)
{
    stopwatch.Restart();
    for (var i = 0; i < 1000000; i++)
    {
        var thing = new AThing();
        dict.Add((c * 1000000) + i, arrays[(c*100000)+i]);
    }
    stopwatch.Stop();
    Console.WriteLine($"pass number {c} took {stopwatch.ElapsedMilliseconds} milliseconds");
}

Console.ReadLine();

Вот вывод, когда я НЕ выделяю размер словаря заранее:

initially allocating arrays took 14609 ms
GC after array allocation took 3713 ms
pass number 0 took 63 milliseconds
pass number 1 took 51 milliseconds
pass number 2 took 78 milliseconds
pass number 3 took 28 milliseconds
pass number 4 took 32 milliseconds
pass number 5 took 133 milliseconds
pass number 6 took 41 milliseconds
pass number 7 took 31 milliseconds
pass number 8 took 27 milliseconds
pass number 9 took 26 milliseconds
pass number 10 took 45 milliseconds
pass number 11 took 335 milliseconds
pass number 12 took 34 milliseconds
pass number 13 took 35 milliseconds
pass number 14 took 71 milliseconds
pass number 15 took 66 milliseconds
pass number 16 took 64 milliseconds
pass number 17 took 58 milliseconds
pass number 18 took 71 milliseconds
pass number 19 took 65 milliseconds
pass number 20 took 68 milliseconds
pass number 21 took 67 milliseconds
pass number 22 took 83 milliseconds
pass number 23 took 11986 milliseconds
pass number 24 took 7948 milliseconds
pass number 25 took 38 milliseconds
pass number 26 took 36 milliseconds
pass number 27 took 27 milliseconds
pass number 28 took 31 milliseconds
..SNIP lots between 30-40ms...
pass number 44 took 34 milliseconds
pass number 45 took 34 milliseconds
pass number 46 took 33 milliseconds
pass number 47 took 2630 milliseconds
pass number 48 took 12255 milliseconds
pass number 49 took 33 milliseconds
...SNIP a load of lines which are all between 30 to 50ms...
pass number 93 took 39 milliseconds
pass number 94 took 43 milliseconds
pass number 95 took 7056 milliseconds
pass number 96 took 33323 milliseconds
pass number 97 took 228 milliseconds
pass number 98 took 70 milliseconds
pass number 99 took 84 milliseconds

Вы можете четко видеть точки, в которых оно должно перераспределяться. Я предполагаю, просто удваивая размер списка и копируя текущие элементы списка, так как в конце есть длинный отрезок, где он этого не делает. Некоторые из них очень дорогие (30+ секунд! Ой)

и вот вывод, если я предварительно выделю размер словаря:

initially allocating arrays took 15494 ms
GC after array allocation took 2622 ms
pass number 0 took 9585 milliseconds
pass number 1 took 107 milliseconds
pass number 2 took 91 milliseconds
pass number 3 took 145 milliseconds
pass number 4 took 83 milliseconds
pass number 5 took 118 milliseconds
pass number 6 took 133 milliseconds
pass number 7 took 126 milliseconds
pass number 8 took 65 milliseconds
pass number 9 took 52 milliseconds
pass number 10 took 42 milliseconds
pass number 11 took 34 milliseconds
pass number 12 took 45 milliseconds
pass number 13 took 48 milliseconds
pass number 14 took 46 milliseconds
..SNIP lots between 30-80ms...
pass number 45 took 80 milliseconds
pass number 46 took 65 milliseconds
pass number 47 took 64 milliseconds
pass number 48 took 65 milliseconds
pass number 49 took 122 milliseconds
pass number 50 took 103 milliseconds
pass number 51 took 45 milliseconds
pass number 52 took 77 milliseconds
pass number 53 took 64 milliseconds
pass number 54 took 96 milliseconds

.. SNIP лоты между 30-80 мс ... проход № 77 занял 44 миллисекунды проход № 78 занял 85 миллисекунд проход № 79 занял 142 миллисекунды проход № 80 занял 138 миллисекунд проход № 81 занял 47 миллисекунд проход № 82 занял 44 миллисекунды ..SNIP лоты между 30-80 мс ... проход № 93 занял 52 миллисекунды проход № 94 занял 50 миллисекунд проход № 95 занял 63 миллисекунды проход № 96 занял 111 миллисекунд проход № 97 занял 175 миллисекунд проход номер 98 занял 96 миллисекунд проход номер 99 занял 67 миллисекунд

Использование памяти возрастает до чуть более 9 ГБ, при первоначальном создании массивов, до примерно 6,5 ГБ после GC.Collect, снова увеличивается до 9 ГБ при добавлении в словарь, затем после того, как все сделано (и он находится в ожидании). в консоли. Readline ()) через некоторое время возвращается к ~ 3,7 ГБ и остается там.

Это ясно намного быстрее в работе для предварительного выделения словаря.

*** Для справки, оригинал ниже ****

Я только что написал этот маленький тест. Я понятия не имею, ЧТО вы храните, поэтому я только что создал небольшой бессмысленный класс с небольшим количеством информации и использовал int в качестве ключа, но два моих вывода из этого:

1. кажется, что при добавлении в словарь он не становится все медленнее, пока не наберет около 40 миллионов единиц. Выполнение сборки «Release» для x64 потребовало около 500 мс на каждый миллион вставок, а затем с 41 по 46 потребовалось больше, например, 700–850 мс (заметный скачок в этот момент)

2. Это дало куда-то более 46 000 000 элементов, съело около 4 ГБ ОЗУ и упало с исключением «Недостаточно памяти».

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

код:

class AThing
{
    public string Name { get; set; }
    public int id { get; set; }
}
class Program
{
    static void Main(string[] args)
    {
        Dictionary<int, AThing> dict = new Dictionary<int, AThing>();

        for (var c = 0; c < 100; c++)
        {
            DateTime nowTime = DateTime.Now;
            for (var i = 0; i < 1000000; i++)
            {
                var thing = new AThing { id = (c * 1000000) + i, Name = $"Item {(c * 1000000) + i}" };
                dict.Add(thing.id, thing);
            }
            var timeTaken = DateTime.Now - nowTime;
            Console.WriteLine($"pass number {c} took {timeTaken.Milliseconds} milliseconds");
        }

    }
}