У меня есть требование построить таблицу поиска. Я использую словарь. Он содержит 45M long и 45M int. long как ключ и int как значение. размер коллекции равен (45M * 12), где long - 8 байт, а int - 4 байт. . Размер около 515 Мбайт. Но на самом деле размер процесса составляет 1,3 Гбайт. Процесс содержит только эту таблицу поиска. Мать, есть ли альтернатива словарю ??Альтернатива словарю для поиска
Thx
Вы можете использовать SortedList вместо словаря, который будет меньше памяти, но может быть немного меньше CPU эффективным, игнорируя вопросы об измерении памяти и почему вам нужно загрузить столько данных в 1 перейти в на первом месте :)
Сколько усилий вы готовы потратить?
Вы можете использовать
KeyValuePair<long,int>[] table = new KeyValuePair<long,int> [45 M];
затем разобраться в этом на первом столбце (long Key) и использовать бинарный поиск, чтобы найти значение.
, улучшение этой идеи состояло бы в том, чтобы определить структуру, содержащую long и int, а затем создать массив этой структуры. – hatchet
@hatchet - не улучшение скорости, но да, было бы более аккуратно. Кортеж просто дал мне написать 1-строчный ответ. –
Не думал о скорости, как о пространстве, поскольку с помощью Tuples массив будет массивом объектов, а затем у вас также будет пространство для самих объектов (long и int). – hatchet
Другой подход, предполагающий, что данные являются статическими: используйте два отсортированных массива - один из длинного и один из int. Убедитесь, что элемент с индексом N в одном является значением для ключа в индексе N в другом. Используйте Array.BinarySearch, чтобы найти ключевые значения, которые вы ищете.
Словари имеют базовый массив, который хранится на данных, но размер массива должен быть быть больше, чем количество элементов, которые у вас есть, именно здесь происходит скорость поиска словаря. Фактически размер базового массива должен быть немного больше, чем количество элементов (25 +%). Объедините это с тем фактом, что при добавлении элементов этот базовый массив де-распределяется и воссоздается (чтобы сделать его больше), у вас, вероятно, есть достаточное количество памяти, готовой для сбора мусора (это означает, что если вам действительно нужно больше памяти, GC восстановит его, но так как у вас в настоящее время достаточно, это не мешает).
Этот словарь содержит больше памяти, чем вы можете себе это позволить, или вам просто интересно, почему это больше, чем вы думали? Существуют и другие доступные вам варианты (в других ответах и комментариях перечислены некоторые), которые будут использовать меньше памяти, но также будут медленнее. У вас проблемы с памятью?
Если ваш диапазон ограничен максимальными длинными значениями 10^12, тогда проблема в отношении пространства заключается в том, что вы должны использовать длинные точки, потому что вам нужно всего несколько бит больше, чем может удерживать int. Если это так, вы могли бы сделать что-то вроде этого: хранить ваши данные в массиве 512 словаря
var myData = new Dictionary<int,int>[512];
ссылаться ИНТ, связанный с длительным значением (которое я буду называть «ключом» для этого примера) , вы могли бы сделать следующее:
myData[key & 511].Add((int) (key >> 9), intValue);
int result = myData[(int) (key & 511)][(int) (key >> 9)];
Просто сколько словарей можно создавать и количество битов, используемых в битовом пустячный, возможно, потребуется подогнать истинные контрсилами ваших данных. Использование этого подхода уменьшит использование памяти примерно на треть
_размер процесса 1,3 Гбайт_: это не проблема. Не используйте TaskManager для измерения использования памяти. –
Является ли размер процесса, вызывающего проблемы? Вы получаете исключения OOM (из памяти)? –
Вот почему у нас есть базы данных. Искать вещи! – banging