Повысить скорость нахождения строки (целочисленные столбцы)

Question

У меня 15 целочисленных столбцов с 5 000 000 строк в таблице. Учитывая входную запись, содержащую 15 целых чисел, мне нужно сравнить входную запись с таблицей записей 5 000 000 и получить все соответствующие строки.

Примечание 1: все целые числа в строке уникальны
Примечание 2: порядок сопоставления столбцов и входной записи не важен.
например: 1, 10, 15, 23, 9, 22, 99, 11, 19, 32, 45, 21, 76, 12, 33 и 33, 10, 15, 99, 11, 19, 32, 45, 21 , 23, 9, 22, 76, 12, 1 должны дать результат матча

Можно ли реализовать функцию хеширования / побитовую операцию для генерации уникального индекса для каждой строки. Функция может возвращать один и тот же индекс для 2 строк, если значения в записях совпадают

Answer 1

Это не так много, но вы должны начать.

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

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

Answer 2

Выполняйте работу правильно, сортируйте целые числа в каждой строке и сортируйте строки в таблице.В течение срока использования таблицы стоимость сортировки будет меньше, чем все хеширование и хеширование, к которым вы склоняетесь.И пока вы занимаетесь этим, создайте индекс в таблице, вероятно, из первых 2 или 3 целых чисел в каждой строке.

Answer 3

Точно так же, как предложил «Знак высокой эффективности» (+1 с моей стороны) - действительно, это правильный подход. Вы должны сохранять отсортированные строки (чтобы 15 целых чисел были в столбцах в отсортированном порядке). Таким образом, сравнивая две строки, вы легко можете определить, идентичны они или нет (начинайте с любого конца и продолжайте, пока не найдете несоответствие - если все 15 чисел совпадают, значит, это совпадение).

Если вам просто нужна хеш-функция для индексации, то вам поможет и та же идея: отсортировать 15 чисел подряд и создать хеш, равный:

Сумма для i = от 1 до 15 (a_i * k ^ i) // k - положительное целое число - см. Ниже

Это дает вам довольно приличный индекс. Если вы можете сохранить k как очень большое, это становится доказуемо свободным от столкновений, но размер индексированного значения увеличивается. Даже если k равно 2, он в значительной степени свободен от столкновений для 5 миллионов строк и 15 столбцов, предполагая, что целочисленный диапазон равен 2 ^ 16.

Другая идея - поскольку вы в основном рассматриваете эвристику, вы также можете рассмотреть более простой подход:

Оставьте еще 3 столбца для min, max и суммы 15 столбцов. Проверка, совпадают ли эти 3 для 2 строк, устранит БОЛЬШОЕ количество истинных негативов. Некоторые ложные срабатывания все равно останутся. (Нетрудно заметить, что использование k = 1 в приведенной выше схеме аналогично сохранению суммы столбцов в качестве значения индекса, которое является одним из 3 значений, упомянутых в этом решении.)

[Возможно, закрытый вопрос - гибкий ли дизайн вашей БД? Это не выглядит стабильным дизайном, так как столбцы, кажется, представляют дочерние объекты, но у меня нет деталей, чтобы сказать это окончательно.]

Answer 4

Для быстрых запросов вы можете предварительно обработать таблицу. Я хотел бы создать HashMap, где отсортированный массив из 15 значений является ключом, и список индексов столбцов, где результаты сортировки по одному массиву являются значениями. Например, запись может выглядеть так:

[1,9,10,11,12,15,19,21,22,23,32,33,45,76,99] => [12, 33]

, поэтому 15 значений находятся в столбце 12, а 33.

Для ключа необходимо создать собственную функцию хеширования и равенства.

• Простой метод хеширования: сортируйте запрос и вычисляйте hash *= 120941 + x для каждой записи. Смотрите, например здесь для гораздо лучших хеш-функций.
• Для проверки равенства просто сравните номера каждого индекса отсортированного запроса с ключом.