Какой самый быстрый способ выяснить, является ли указатель частью набора в C?

Имея указатель на структуру, мне нужно очень быстро определить, является ли она частью набора (который я должен определить/реализовать самостоятельно). Я могу подумать о такой технике, как Фильтр Блума, но не знаю, как это сделать на указатель.

Решение должно работать на 32- и 64-битной машине.

Редактировать: Все эти указатели (2k-5k из них) указывают на различные случайные адреса памяти, поскольку они нацелены на элемент двусвязного списка, который я не могу контролировать. Это можно перефразировать так: «Как найти в элементе часть доступного только для чтения двухсвязного списка, создав другую структуру в стороне?»

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


c set bloom-filter
person Patrick Allaert    schedule 17.06.2014    source источник
comment
объяснить часть набора? Какой набор? Вы имеете в виду, узнать, указывает ли указатель на структуру на элемент данного массива этих структур?   -  person M.M    schedule 17.06.2014
comment
Тем временем я обновлю свой вопрос, чтобы быть более точным: все эти структуры (2k-5k из них) появляются в виде двусвязного списка, над которым у меня нулевой контроль, однако мне нужно создать этот набор самостоятельно, помимо существующей DLL   -  person Patrick Allaert    schedule 17.06.2014
comment
Фильтры Блума являются вероятностными... вы согласны с этим?   -  person Dietrich Epp    schedule 17.06.2014
comment
Вы хотите что-то более быстрое, чем обход списка, проверяющий, соответствует ли каждый узел указателю? Если это так, вы также можете хранить каждый указатель-кандидат в структуре данных, которую можно быстро найти (например, в дереве поиска). Конечно, это означает, что вы должны поддерживать дерево поиска каждый раз, когда вы вносите изменения в связанный список (или, конечно, перестраиваете его перед использованием).   -  person M.M    schedule 17.06.2014
comment
Отвечая на часть, не знаю, как это сделать с указателем, приведите к (uintptr_t) (это приведение гарантированно будет биекцией) и используйте любую технику, которую вы использовали бы для целого числа   -  person M.M    schedule 17.06.2014
comment
@DietrichEpp Да, я согласен с этим, у меня будет намного больше лжи, чем правды. Следовательно, я буду использовать что-то более медленное, но не вероятностное, если это правда.   -  person Patrick Allaert    schedule 17.06.2014
comment
@MattMcNabb Да, я хочу что-то быстрее, чем обход всего списка. Дерево поиска, возможно, то, что мне нужно. Двусвязный список может расти, а множество — нет. Что касается актерского состава uintptr_t, это может быть очень хорошим началом! Теперь мне нужно выяснить, какую технику (вероятностную или нет) использовать для целого числа.   -  person Patrick Allaert    schedule 17.06.2014
comment
На самом деле непонятно, о чем вы спрашиваете. Заголовок как найти указатель в наборе. Затем сначала вы говорите, что у вас есть указатель, который может быть частью набора. Отлично. Но затем вы говорите, что эти указатели нацелены на элементы двойного связанного списка, которые не связаны с набором. И тут вы вдруг спрашиваете, как найти элемент в двусвязном списке.   -  person Lundin    schedule 17.06.2014
comment
@Lundin: Пусть у нас есть связанный список из 26 элементов: a <-> b <-> c <-> ... <-> z, у каждого из этих элементов есть адрес в памяти (указатель): 0x0000040: a, 0x0000060: b, 0x0001010: c, ... 0x00a0b50: z. Теперь мне нужно реализовать набор указателей, например: {0x0000040, 0x0001010, 0x00a0b50} (соответствует: a, c и z), и мне нужно очень быстро выяснить, является ли адрес частью этого набора, например. 0x00a0b50 часть этого? =› да (z), это 0xffa0b50 часть? =› нет   -  person Patrick Allaert    schedule 17.06.2014
comment
Вы можете что-нибудь сказать о диапазоне адресов этих указателей? Насколько велик этот диапазон?   -  person meaning-matters    schedule 17.06.2014
comment
@meaning-matters: к сожалению, я не знаю, однако я могу вычислить его, поскольку набор будет фиксированным с самого начала.   -  person Patrick Allaert    schedule 17.06.2014

Ответы (1)


arrow_upward
1
arrow_downward

Со страницы, на которую вы ссылались:

Блум предложил этот метод для приложений, в которых объем исходных данных потребовал бы непрактично большой области хеширования в памяти, если бы применялись «обычные» безошибочные методы хеширования. Он привел пример алгоритма расстановки переносов для словаря из 500 000 слов, из которых 90 % следуют простым правилам расстановки переносов, а остальные 10 % требуют дорогостоящего доступа к диску для извлечения определенных шаблонов расстановки переносов.

Если у вас всего 2k-5k элементов, то я сомневаюсь, что вы говорите о «непрактично большой хеш-области в памяти».

Короче говоря, я бы рекомендовал хеш-таблицу. Вам нужно будет выполнить один O(n) проход по данным для построения таблицы, а затем поиск будет O(1).

person ams    schedule 17.06.2014
comment
Спасибо @ams за ваш ответ. К сожалению, я немного боюсь, что это решение может быть медленным. Дело не в том, что O(1) не быстро, а в том, что мне приходится выполнять эту операцию столько раз (около 50 000–400 000 раз) за прогон, и один прогон определенно не может занять больше 0,1 мс. Поэтому мне нужно что-то, что можно сделать менее чем за 1e-10 секунд. - person Patrick Allaert; 17.06.2014
comment
В настоящее время меня беспокоит то, что и хеш-таблицы, и фильтры Блума требуют хеширования, и даже если это выполняется один раз (иногда больше с фильтрами Блума (k)), это может быть узким местом. Я должен был быть более ясным с самого начала в аспекте производительности, извините. - person Patrick Allaert; 17.06.2014
comment
@PatrickAllaert Попытайтесь выяснить, возможно ли вообще то, что вы хотите, теоретически. - person meaning-matters; 17.06.2014
comment
@PatrickAllaert Подходящая хэш-функция для одного целого числа (указателя) вряд ли будет очень медленной. Вероятно, вы могли бы просто сдвинуть младшие биты (которые всегда равны нулю, потому что malloc возвращает выровненную память) и обнулить большинство верхних битов, и этого будет достаточно. Это даст вам размер стола, равный степени двойки. Если частота столкновений окажется слишком высокой, вам понадобится что-то умнее/медленнее, но попробовать стоит. В любом случае, небольшая игра с числами в регистре, безусловно, быстрее, чем обход дерева поиска в памяти. - person ams; 17.06.2014
comment
@PatrickAllaert Кстати, 0,1 мс на процессоре с тактовой частотой 2 ГГц составляет всего 200 тыс. циклов ЦП. Сделать что-нибудь 400 тысяч раз за такое количество циклов будет непросто! - person ams; 20.06.2014