Сравните два числа для "подобия"

Это часть функции поиска на веб-сайте. Поэтому я пытаюсь найти способ как можно быстрее достичь конечного результата.

Имеет двоичное число, в котором имеет порядок цифр.

Входной номер = 01001

Имеет базу данных других двоичных чисел с одинаковой длиной.

01000, 10110, 00000, 11111

Я не знаю, как писать то, что я делаю, поэтому я собираюсь сделать это более визуально ниже.

// Zeros mean nothing & the location of a 1 matters, not the total number of 1's.    
input num > 0 1 0 0 1 = 2 possible matches
number[1] > 0 1 0 0 0 = 1 match = 50% match
number[2] > 1 0 1 1 0 = 0 match = 0% match
number[3] > 0 0 0 0 0 = 0 match = 0% match
number[4] > 1 1 1 1 1 = 2 match = 100% match

Теперь, очевидно, вы можете пойти по цифре, по номеру и сравнить его таким образом (используя цикл, а что нет). Но я надеялся, что может быть алгоритм или что-то, что поможет. В основном, потому что в приведенном выше примере я использовал только 5-значные числа. Но я собираюсь регулярно сравнивать около 100 000 номеров с 200 цифрами каждый, что много вычисляет.

Я обычно имею дело с php и MySQL. Но если что-то впечатляющее появляется, я всегда могу учиться.

Ответ 1

Если можно каким-то образом нарезать свои бистроны в целых размерах, некоторые элементарные логические арифметики будут делать, и такие инструкции, как правило, довольно быстро

$matchmask = ~ ($inputval ^ $tomatch) & $inputval

Что это делает:

xor определяет бит, которые различаются в inputval и tomatch
отрицание дает значение, в котором все биты, которые равны в inputval и tomatch, установлены
и что с inputval и только биты, которые равны 1 как в inputval, так и в tomatch, остаются установленными.

Затем подсчитайте количество бит, установленное в результате, посмотрите Как подсчитать количество установленных битов в 32-разрядном целое? для оптимального решения, легко переводится на php

Ответ 2

Хорошо, первое, что я могу придумать, это просто поразрядное И между двумя числами; вы можете проанализировать результат, чтобы получить процент соответствия:

if( result >= input ) 
    //100% match
else {
    result ^= input;

    /* The number of 1 in result is the number of 1 of "input" 
     * that are missing in "result".
     */
}

Конечно, вам нужно реализовать свою собственную функцию AND и XOR (это будет работать только для 32-битных целых чисел). Обратите внимание, что он работает только с неподписанными номерами.

Ответ 3

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

То есть для ввода

01001, итерация по базе данных и определение того, является ли number1[0] & input ненулевым, а (number1[3] >> 8) & input отличным от нуля, считая 0 в качестве индекса LSB. Однако, как вы быстро получаете бит-сдвиг, а также большие числа на вас. Если вы обнаружите 1 × 0 на входе, вы всегда можете инвертировать вход и проверить нуль для обнаружения покрытия.

Это даст вам скромное улучшение, но в лучшем случае проблему с уменьшением постоянной продолжительности. Если большая часть ваших входов сбалансирована между 0 и 1 сек, вы сократите вдвое количество требуемых операций. Если он будет более предвзятым, вы получите лучшие результаты.

Ответ 4

Предположим, что номер входа называется A (поэтому в вашем примере A = 01001), а другой - x. У вас будет 100% -ное совпадение, если x & A == A. В противном случае для частичных совпадений количество 1 бита будет (взято из взлома хакера):

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);

Обратите внимание, что это будет работать для 32-битных целых чисел.

Ответ 5

Предположим, что у вас есть функция bit1count, то из того, что вы описали, формула "подобия" должна быть:

100.0 / min(bit1count(n1), bit1count(n2)) * bit1count(n1 & n2)

Если n1 и n2 являются двумя числами и & являются логическими и операторами.

bit1count может быть легко реализован с использованием цикла или, более элегантным, с использованием алгоритма, предоставленного в ответе BigBears.

В mysql фактически есть BIT_COUNT, поэтому что-то вроде этого должно работать:

SELECT 100.0 / IF(BIT_COUNT(n1) < BIT_COUNT(n2), BIT_COUNT(n1), BIT_COUNT(n2)) * BIT_COUNT(n1 & n2) FROM table