У меня есть миллионы случайных положительных и отрицательных 32-разрядных целых чисел, которые необходимо хранить в некоторой структуре данных. Функция должна выйти, если структура данных уже содержит это конкретное значение. Можете ли вы предложить некоторую высокоэффективную структуру данных с высокой памятью, которая этого достигнет? СпасибоСтруктура данных для хранения больших наборов данных
С точки зрения эффективности памяти трудно превзойти std::vector так как все данные упакованы вместе. И поскольку вы должны быть быстрым, это поиск, лучше хранить их отсортированные, чтобы вы могли бинарно искать их.
Если не вы можете:
В любом случае меньше памяти вы берете труднее будет иметь номер назад, который нужно найти (Это физический принцип, не связанные с программированием, но в теории информации)
Вы не сказали, необходимо ли сохранять элементы в несортированном порядке - я предполагаю, что нет.
Функция должна выйти, если структура данных уже содержит это конкретное значение.
У вас есть около 4 миллиардов возможных 32-битных значений, и вы говорите о некоторых, казалось бы, «немногих» миллионах чисел. Для меня, это говорит что-то вроде этого:
vector<uint16_t> bucket[65536];
Для Q миллиона элементов, вы будете в среднем 15 * Q элементов на ведро ... достаточно для накладных расходов в std::vector<> быть небольшой процент использования памяти, и но достаточно немногих, чтобы очень быстро пересортировать ковш после добавления или, альтернативно, выполнять линейные поиски.
Если вы считаете, что K будет больше, сделайте больше ведер, покрывающих меньшие диапазоны значений. Если вы не уверены, вам может понадобиться динамическая калибровка или вообще найти другой подход. Если K подходит к 128, вы можете использовать bitset для всего.
С учетом логического значения v вы можете использовать комбинацию маскировки от высоких бит (например, (uint32_t)v >> 16), чтобы указать ведро, с двоичным поиском или вставкой, например. v & 65535 внутри ведра ....
Если вы готовы принять ложные срабатывания, я бы предложил вам использовать Bloom Filter.
Используя всего лишь 10 бит на элемент и 7 хеш-функций, вероятность ложных срабатываний менее 1% и отсутствие ложных негативов вообще.
Dataset, данные * комплект *, может быть, какой-то [структура данных данных] (http://en.cppreference.com/w/cpp/container/unordered_set) можно использовать? По крайней мере, для начала. –
Когда вы говорите «миллионы», сколько их? 16 ГБ, который является общим объемом памяти на современных компьютерах, будет удерживать КАЖДЫЙ один из 4096 миллионов номеров в 32 битах.Используя растровое изображение, вы можете уменьшить его в 32 раза, так что 0,5 ГБ. –
_Random_ положительные и отрицательные 32-битные целые числа? _Если их хранение является проблемой, не делайте этого, когда нужно новое. (Хранение _all_ из них наивно занимает 16 ГБ - проблема?) Функция? Функция, которая не нуждается в выходе, если 'структура данных' делает _not_' содержать это конкретное значение'? Попытайтесь предоставить достаточную информацию для поиска решения: какие операции должны поддерживаться и в каком порядке (разрешать вставки и удаления между запросами, только вставками или без изменений значения). Какие операции происходят достаточно часто, чтобы быть в курсе эффективности, что-нибудь известно о помощи данных? – greybeard