Сравните два числа для "сходства" - PullRequest
Новая
       12

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

10 голосов
/ 06 сентября 2011

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

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

Входной номер = 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.Но если случится что-то впечатляющее, я всегда смогу научиться.

Ответы [ 5 ]

4 голосов
/ 06 сентября 2011

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

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

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

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

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

1 голос
/ 06 сентября 2011

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

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

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

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

1 голос
/ 06 сентября 2011

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

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

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

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

0 голосов
/ 06 сентября 2011

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

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

, где n1 и n2 - это два числа, а & является логическим и оператором.

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

На самом деле BIT_COUNT в MySQL, так что-то вроде этого должно работать: 

SELECT 100.0 / IF(BIT_COUNT(n1) < BIT_COUNT(n2), BIT_COUNT(n1), BIT_COUNT(n2)) * BIT_COUNT(n1 & n2) FROM table
0 голосов
/ 06 сентября 2011

Предположим, что входной номер называется 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-битных целых чисел.

...