0

Хочу сделать реализацию поиска совпадений в стиле графов или ещё как-то. Есть много 16 байтовых строк, чтобы не проверять простым for хочу искать последовательно вглубь графа. Т.е. я это вижу приблизительно так, каждая нода содержит массив где ключ ссылается на другой массив. Первый байт помещаем в первый слой и делаем ммылку на следущий слой, где второй байт становится ключём. Грубо говоря это как многомерный массив где первый байт это первый уровень, и он ссылается на вложенный массив где лежат вторые байты и строк. В принципе есть два больших набора байтовых массивов фиксированной длинны, т.е. каждый элемент массива имеет одинаковый размер. Нужно искать совпадения, подскажите куда копать?

15
  • Ничего не понятно. Опишите проблему, покажите примеры, свои идеи
    – MBo
    3 окт 2022 в 3:04
  • Нет примеров, идея в том чтобы был своего рода многомерный массив где первфй байт будет иметь ссылку на другой массив, т.е. проверяем первый байт, если он есть то проверяем дальше в глубину, если его нет то дальше можно не искать
    – pnp2000
    3 окт 2022 в 3:08
  • Покажите, что нужно искать, на примере
    – MBo
    3 окт 2022 в 3:43
  • Есть два набора байтовых массивов фикированного размера, и нужно искать совпадения. Хочу избавиться от for потому что сликом много лишней работы.
    – pnp2000
    3 окт 2022 в 3:45
  • Пример на строках?
    – MBo
    3 окт 2022 в 3:46

1 ответ 1

1

Проще всего организовать set - в golang - на основе map из данных первого набора, и потом проверять значения из второго набора на наличие в этом множестве.

Хотя элементы данных не такие уж длинные, но всё-таки каждый 16-байтный массив второго набора будет обрабатываться полностью для вычисления хэша.

Поэтому стоит проверить и вашу идею про проверку первого байта, потом второго и т.д. Одна из лучших структур данных для этого - trie.

введите сюда описание изображения

Несовпадающие байты в большинстве своём будут отсекаться на ранней стадии, поэтому проверки должны быть довольно быстрыми. Вот произвольно взятая ссылка на реализацию trie на golang (выглядит не очень серьезно, но как отправная точка - подойдёт)

4
  • У меня в принципе такая-же идея, просто я не правильно назвал это, виесто дерева я обозвал это графом, хотя граф это немножечко другое. К стати тут сделано как я и думал, значит вектор идеи у меня верный.
    – pnp2000
    3 окт 2022 в 16:32
  • В принципе это и есть ответ, то что мне нужно называется "Trie data structure"
    – pnp2000
    3 окт 2022 в 16:39
  • Отлично. Посмотрел разновидности - просто trie для вашей задачи, видимо, лучший вариант.
    – MBo
    3 окт 2022 в 16:44
  • Я когда думал как искать менее затратно именно это и придумал, просто не знал как оно называется, поэтому и спросил.
    – pnp2000
    3 окт 2022 в 17:54

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.