Хочу сделать реализацию поиска совпадений в стиле графов или ещё как-то. Есть много 16 байтовых строк, чтобы не проверять простым for хочу искать последовательно вглубь графа. Т.е. я это вижу приблизительно так, каждая нода содержит массив где ключ ссылается на другой массив. Первый байт помещаем в первый слой и делаем ммылку на следущий слой, где второй байт становится ключём. Грубо говоря это как многомерный массив где первый байт это первый уровень, и он ссылается на вложенный массив где лежат вторые байты и строк. В принципе есть два больших набора байтовых массивов фиксированной длинны, т.е. каждый элемент массива имеет одинаковый размер. Нужно искать совпадения, подскажите куда копать?
-
Ничего не понятно. Опишите проблему, покажите примеры, свои идеи– MBo3 окт 2022 в 3:04
-
Нет примеров, идея в том чтобы был своего рода многомерный массив где первфй байт будет иметь ссылку на другой массив, т.е. проверяем первый байт, если он есть то проверяем дальше в глубину, если его нет то дальше можно не искать– pnp20003 окт 2022 в 3:08
-
Покажите, что нужно искать, на примере– MBo3 окт 2022 в 3:43
-
Есть два набора байтовых массивов фикированного размера, и нужно искать совпадения. Хочу избавиться от for потому что сликом много лишней работы.– pnp20003 окт 2022 в 3:45
-
Пример на строках?– MBo3 окт 2022 в 3:46
1 ответ
Проще всего организовать set - в golang - на основе map
из данных первого набора, и потом проверять значения из второго набора на наличие в этом множестве.
Хотя элементы данных не такие уж длинные, но всё-таки каждый 16-байтный массив второго набора будет обрабатываться полностью для вычисления хэша.
Поэтому стоит проверить и вашу идею про проверку первого байта, потом второго и т.д. Одна из лучших структур данных для этого - trie.
Несовпадающие байты в большинстве своём будут отсекаться на ранней стадии, поэтому проверки должны быть довольно быстрыми. Вот произвольно взятая ссылка на реализацию trie на golang (выглядит не очень серьезно, но как отправная точка - подойдёт)
-
У меня в принципе такая-же идея, просто я не правильно назвал это, виесто дерева я обозвал это графом, хотя граф это немножечко другое. К стати тут сделано как я и думал, значит вектор идеи у меня верный.– pnp20003 окт 2022 в 16:32
-
В принципе это и есть ответ, то что мне нужно называется "Trie data structure"– pnp20003 окт 2022 в 16:39
-
Отлично. Посмотрел разновидности - просто trie для вашей задачи, видимо, лучший вариант.– MBo3 окт 2022 в 16:44
-
Я когда думал как искать менее затратно именно это и придумал, просто не знал как оно называется, поэтому и спросил.– pnp20003 окт 2022 в 17:54