Если у меня есть массив ключей M и массив целей N, как я могу проверить, что M [i] существует в N, прежде чем искать его?

Question

Как видно из названия, я пытаюсь найти элементы M, которые существуют в большом постоянном массиве N. Большую часть времени в N не будет элемента M, поэтому подавляющее большинство запросов, выполненных на M,пустая трата времени.

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

Итак, какие приемы я могу использовать, чтобы сократить возможность поиска M без необходимости?

Это в основном вопрос, не зависящий от языка, но только для того, чтобынасколько это возможно, я использую C ++.

Answer 1

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

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

Answer 2

Вы можете создать хеш-таблицу со значениями N в качестве ключей.

Затем вы пытаетесь получить доступ к хешу [M [i]], если он возвращает значение, то оно существует, то есть O (1) (без учета коллизий.)

Answer 3

Так как N является статическим, вы можете рассмотреть возможность создания Perfect Hash функции для N. Это сделает ваш поиск гарантированным O (1) раз.

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

Вы всегда можете использовать общедоступную хеш-таблицу с ожидаемым O (1).

Я полагаю, вы храните некоторую дополнительную информациюкоторый вы хотите получить, зная, что он там есть?Как вы их храните?

В этом случае может оказаться полезным B-Tree (в отраслевых стандартных базах данных обычно используется какой-то вариант), который может даже служить индексом!Итак, вы ищете, и если вы найдете его, у вас есть данные / указатель на него.Вы найдете много реализаций для них в Интернете.