Поиск последовательности битов в целом числе в Python
У меня есть два целых числа, назовем их haystack и needle. Мне нужно проверить это, если двоичное представление needle произошло в haystack [и НЕОБЯЗАТЕЛЬНО найти позицию первого вхождения]
Пример
haystack = 0b10101111010110010101010101110
needle = 0b1011001 # occurred in position 13
needle = 0b111011 # not occurred
Я ищу наименьшую возможную временную сложность, я не могу написать код со временной сложностью лучше, чем O(h), где h — количество бит в стоге сена. Вы можете увидеть мой код ниже.
Мне нужно проверить появление предопределенного needle (которое никогда не меняется, и это нечетное число) в миллиардах случайных целых чисел haystack (поэтому мы не можем предварительно обработать haystack для оптимизации скорости)
Поскольку поиск позиции необязателен, если вы можете написать код с большей временной сложностью, чтобы просто возвращать логическое значение, указывающее вхождение, это тоже идеально. Потому что в миллиардах проверок я знаю, что этого не произошло, и когда это произошло, я могу использовать следующий код, чтобы найти позицию.
Хороший вероятностный алгоритм с ложными положительными результатами тоже подойдет.
def find_needle_in_haystack(haystack, needle):
n = needle.bit_length() # calculate the number of bits in needle
mask = (1 << n) - 1 # create a mask with n bits
i = 0
while haystack != 0:
x = haystack & mask # bitwise AND with mask to get first n bits
if x == needle:
return i
i += 1
haystack >>= 1 # shift haystack to the right by 1 bit
return -1 # needle not found in haystack
Для иглы это предопределено, мы вольны выбирать любые биты, скажем 64 или что-то еще. стог сена очень большой и неопределенный. считать миллион бит. Я могу уменьшить стог сена, если у вас есть идея
если это поможет, haystack на самом деле является потоком случайных битов. его длина составляет миллиарды бит. так как он не помещается в оперативной памяти, я разбил его на миллион бит, и в моем вопросе haystack это его кусок (я также могу разбить его на меньшее количество бит, но поскольку мне нужно сгенерировать следующие биты haystack, это будет быстрее, если я выберу большое количество битов) В цикле while True, когда я генерирую поток haystack, мне нужно остановить цикл, найдя вхождение needle, и это происходит после миллиардов циклов
Хорошо, это многое проясняет. Ничего сразу в голову не приходит, но я подумаю.
Вы смотрели на реализацию find в модуле bitstring? pypi.org/project/bitstring
Так что насчет длины иглы? Он всегда/обычно короткий?
@MBo Я могу сгенерировать иглу любого размера, она может быть любой желаемой длины.
Извините, я не понимаю. Если длина иглы NL, вы можете сделать маски NL сдвинутых игл (0b1011001, 0b10110010, 0b101100100...) и проверить их параллельно
@MBo Да, я думал об этом, но как? рассмотрим 1011001 как иглу, она имеет 7 бит, если мы умножим ее на (1<<7)+1, получится два повторения иглы с 10110011011001, давайте назовем ее two_needle, обычно мы можем произвести n_needle, но для простоты рассмотрим two_needle на данный момент, как проверить их параллельно?
если я это сделаю haystack ^ (n_needle << y) Он может сгенерировать последовательность 0s, если я выберу правильный y (числа сдвигов, 0<=y<7). в моем примере стог сена, если мы выберем y=6, результат будет 10101111010110010101010101110 ^ 10110011011001000000, который равен 10101111000000001110011101110, и у нас есть семь нулей в позиции вхождения, как это обнаружить ?! как правильно выбрать y?
@DanNagle Я прочитал это, оно основано на регулярном выражении для моего варианта использования, потому что выравнивание по байтам равно False github.com/scott-griffiths/bitstring/blob/main/…
Ответы 2
Итак, у меня есть немного нестандартного решения — вы можете попробовать преобразовать двоичное представление в строку, а затем использовать метод str.find.
Например:
In [7]: haystack = 10101111010110010101010101110
In [8]: needle = 1011001
In [9]: str_haystack = str(haystack)
In [10]: str_needle = str(needle)
In [11]: str_haystack.find(str_needle)
Out[11]: 9
Спасибо за ваш ответ. Временная сложность вашего решения не лучше моего. На самом деле мое собственное решение намного быстрее и использует меньше памяти. Преобразование int в строку использует больше памяти и занимает O(N) время
возможно, вы правы, если основной целью является оптимизация памяти и времени, ваше решение будет лучше. Я хотел поделиться чем-то простым и читаемым, что может быть достаточно хорошим
Во-первых, Python — плохой выбор языка для этого. Так или иначе, вы будете много вертеть. Python — это язык высокого уровня с медленными уровнями абстракции для удобства программиста. Это добавляет много накладных расходов на любой простой на вид трюк.
Тем не менее, я бы рекомендовал использовать для этого предварительно вычисленную таблицу поиска. Идея заключается в следующем. Нам нужен массив по количеству совпадающих битов, по следующему байту, по количеству совпавших битов в данный момент. Это может быть сохранено в массиве длины bits * 256. При этом значение в позиции 256*a + b представляет собой число, сообщающее вам, что если вы ранее сопоставили a бит, а b является следующим байтом, сколько битов вы СЕЙЧАС сопоставили.
И теперь ваша логика выглядит примерно так (без учета приведения):
matched = 0
for b in bytes:
matched = lookup[256*matched + int(b)]
if matched == length_of_needle:
return True
return False
Вот пример кода, демонстрирующий эту идею. Обратите внимание, что я добавил 0 к концу битов, чтобы получить четное число байтов.
# Assuming that needle is an array of bits.
def needle_to_lookup (needle):
ord2bits = []
for j in range(256):
bits = []
k = j
for _ in range(8):
bits.append(k % 2)
k = k // 2
ord2bits.append(tuple(reversed(bits)))
lookup = []
for i in range(len(needle) + 1):
for bits in ord2bits:
# Do we successfully keep matching?
matched = i
for j in range(8):
if i + j == len(needle):
matched = i+j
break
elif needle[i+j] == bits[j]:
matched = i+j
else:
matched = 0
break
if 0 == matched: # Failed to extend for a byte.
for j in range(8):
for k in range(8 - j):
if k == len(needle):
matched = k
break
elif needle[k] == bits[j+k]:
matched = k+1
else:
matched = 0
break
if 0 < matched:
break
lookup.append(matched)
return lookup
def find_needle(needle, byte_list):
lookup = needle_to_lookup(needle)
matched = 0
for byte in byte_list:
matched = lookup[256*matched + byte]
if matched == len(needle):
return True
return False
print(find_needle([1, 0, 1, 1, 0, 0, 1], bytes([175, 89, 85, 184])))
print(find_needle([1, 1, 1, 0, 1, 1], bytes([175, 89, 85, 184])))
Я вообще не понял твоего решения! Что вы имеете в виду под bits, a и b?! Какова временная сложность вашего решения?
Учтите, что haystack — это СЛУЧАЙНОЕ целое число.
@WebMaster Под bits я имею в виду how many bits have you matched at this point. И вы сказали, что мы можем рассматривать haystack как поток случайных битов, который, в свою очередь, можно рассматривать как поток случайных байтов. Обработка байтов выполняется быстрее, чем обработка битов, потому что одна операция ЦП выполняет 8 бит. Временная сложность O(number of bytes) оптимальна, но с хорошей константой.
Я думаю, что я не могу рассматривать это как байт, если я перешлю needle=0b1011001 как байт, это 0b01011001, потому что мне нужно иметь 8 бит. в этом случае моя иголка не попала в мой стог сена, что неверно. Также O(number of bytes) это что-то вроде O(number of bits/8) в данном случае с для меня не большая разница
Нет, не относитесь к иголке как к байту, относитесь к стогу сена как к байту.
Я добавил реализацию, показывающую, что именно я имею в виду. Если у вас есть двоичный файл, вы можете открыть его в режиме rb, чтобы прочитать его напрямую как поток байтов, которые можно передать этой функции.
Большое спасибо, я прочитал ваш код несколько раз. Я не могу понять, как это работает! Не могли бы вы рассказать мне 1-Почему у нас есть 256? 2-Можем ли мы проверять несколько байтов одновременно, вместо обработки стога сена как байта, рассматривать его как n-байты 3-Имеет ли этот алгоритм поиска имя? Можете ли вы порекомендовать мне ресурс, мне интересно узнать о нем больше
Причина, по которой 256 заключается в том, что 1 байт имеет 8 бит, может представлять любое число от 0 до 255. ЦП имеют встроенные инструкции для очень быстрой работы с байтами. В принципе, вы можете сделать это с любым количеством байтов, но тогда таблица поиска станет большой. gist.github.com/jboner/2841832 показывает, почему вы хотите, чтобы таблица помещалась в кеш L1, который часто составляет 32 КБ. Идея таблицы смутно вдохновлена алгоритмом Бойера-Мура. Который, с большой сложностью, можно было бы адаптировать, чтобы еще больше ускорить это для длинных игл.
Какое максимальное количество бит в стоге сена? А макс для иглы?