Ускорение поиска наилучшего бинарного совпадающего номера

Ответ 1

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

Для простоты подумайте о своих 256-битных числах как о векторах с 256 номерами (также двоичными, конечно). Имея дерево, подобное выше, вы можете найти, существует ли конкретный вектор в вашем наборе данных в 256 шагов или меньше, просто пройдя по дереву и тестируя, если существует следующая ветвь (либо "0", либо "1" ). Что-то вроде этого (код довольно сырой, но вы должны получить представление):

def exists(node, v, i):
    """Checks if subvector of v starting from index i exists in 
       sub-tree defined by node
    """
    if i == len(v): 
        return True
    elif v[i] == 0 and node.left: 
        return exists(node.left, v, i + 1)
    elif v[i] == 1 and node.right: 
        return exists(node.right, v, i + 1)
    else: 
        return False

На каждом шаге мы решаем, куда идти влево или вправо, исходя из текущего элемента значения v. Но вам также нужно обработать до K различных элементов. Итак, почему бы не использовать количество ошибок и обработать обе ветки?

def exists(node, v, i, err_left=K):
    """Checks if subvector of v starting from index i exists in 
       sub-tree defined by node with up to err_left errors.
    """
    if i == len(v): 
        return True
    elif v[i] == 0: 
        if node.left:
            return exists(node.left, v, i + 1, err_count)
        elif node.right: 
            return exists(node.left, v, i + 1, err_left - 1)  # proceed, but decrease 
                                                              #   errors left
        else: 
            return False            
    elif v[i] == 1: 
        if node.right:
            return exists(node.right, v, i + 1, err_count)
        elif node.left: 
            return exists(node.right, v, i + 1, err_left - 1)  # proceed, but decrease 
                                                               #   errors left
        else: 
            return False 
    else: 
        return False

Время работы этого алгоритма сильно зависит от ваших настроек. В худшем случае (K = 256) все равно O (n) (вам нужно проверить каждую ветвь), но это время быстро падает с уменьшением K (при малом K это почти O (log n)). С K ~ 128 это где-то посередине.

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

Trie сжатые данные в определенном смысле, но если у вас есть проблемы с памятью, попробуйте использовать представление таблицы вместо объектов и указателей.

Наконец, вы можете объединить его с bloom filters для фильтрации чисел, которые определенно не находятся в наборе в первую очередь, а затем проверьте остальные с помощью выше дерево.

Ответ 2

Алгоритм решения - O (n). Ваш единственный вариант - это цикл через массив, пока не найдет число, соответствующее вашей цели.

Теперь, как мы находим, соответствуют ли два числа?. Наиболее эффективным способом является использование побитовых операций. Например, я пишу код, который работает для 64-битных номеров:

int compare(long l1, long l2)
{
    //Use xor to get what bits are the same
    long xor = ~ (l1 ^ l2);

    //count the number of bits with value = 1
    int count = 0;
    while(xor != 0)
    {
        //check if the right bit is 1, using & operator beetween our number and 0000001
        if(xor & 1 > 0) count++;

        //shift right the bits
        xor = xor >> 1
    }

    return count;
}

Это сравнение может быть адаптировано в зависимости от того, как реализованы ваши 256-битные числа. Оптимизация может заключаться в том, чтобы разбить цикл while, когда вы достигнете count >= N.

Вы можете проверить этот вопрос, чтобы найти более эффективные способы подсчета бит со значением 1.

Надеюсь, что это поможет!