контекст, стоящий за моей проблемой, не важен, поскольку сам мой вопрос довольно автономен.
В настоящее время я пытаюсь присвоить числа последовательностям битов. Таким образом, если я запрошу functionA
битовую последовательность 42, он вернет соответствующие биты, скажем, «0110101011…» (неправильно, просто пример), и если я задам functionB
последовательность «0110101011...», она мог бы дать мне номер 42.
В настоящее время я присваиваю номер каждой последовательности через шаблон
bits val
| 0 | 0 |
| 1 | 1 |
| 00 | 2 |
| 10 | 3 |
| 01 | 4 |
| 11 | 5 |
| 000 | 6 |
| 100 | 7 |
и так далее, и так далее. В настоящее время функции, которые я создал для этого, работают как таковые.
from itertools import product
def bit_lookup_num(lookup):
if lookup == '':
return -1
bits=[]
current_len=1
while lookup not in bits:
bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
current_len+=1
return bits.index(lookup)
def num_lookup_bit(lookup):
if lookup == -1:
return ''
bits=[]
current_len=1
while len(bits)-1<lookup:
bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
current_len+=1
return bits[lookup]
Где num_lookup_bit
действует как functionA
в моем предыдущем примере, а bit_lookup_num
служит как functionB
. Однако моя реализация становится довольно медленной для больших последовательностей битов, и это связано с тем, что я использую функцию product()
из itertools. Наверняка должен быть более быстрый способ сделать это, чем генерировать каждую возможность с помощью product()
и проверять ее положение в списке, увы, мне еще предстоит найти этот обходной путь.
Как я могу улучшить эти функции, избегая алгоритмов грубой силы?
Вы вынуждены использовать эту конкретную логику сопоставления? Например, является ли правильным отображением то, в котором вы перечисляете все продукты N-длины?
В любом случае, если у вас достаточно памяти, вы можете просто поддерживать гигантскую карту, которую создали заранее. Но я чувствую, что должно быть и аналитическое решение.
Ах! Это пойдет в порядке подсчета... ок...
Извините, вы хотите, чтобы 01
и 10
были разными, не так ли? Ваша таблица говорит об обратном
@cadolphs это порядок, да. и juanpa.arrivillaga, это объект str, который содержит 0 и 1. не фактическая строка байтов.
Последовательность вашего примера не соответствует выходному коду. 4 => 01
@juanpa.arrivillaga вы и Вудфорд правы, это была ошибка с моей стороны. я извиняюсь за любую путаницу, которая вызвала.
разве 01
не должно стоять перед 10
? Обновлено: о! не заметил perm[::-1]
@juanpa.arrivillaga нет, это было сделано намеренно. Он предназначен для восходящего счета, как двоичный, поэтому 01
произойдет после того, как 10
будет переполнен.
насколько большим может стать lookup
?
@juanpa.arrivillaga в моем случае достигает 256**3. Так что на данный момент ваше картографическое решение, вероятно, является моим лучшим выбором. Но я действительно чувствую, что должна быть какая-то комбинация арифметических функций, которая могла бы вообще избежать...
почти наверняка есть, по сути, вы можете индексировать в двоичную корзину, затем найти оттуда число и преобразовать целое число в двоичное, но у меня нет времени думать об этом в данный момент
Инкрементальный подход:
def num_lookup_bit(num):
x = 2
bits = ''
while num >= 0:
bits += '0' if num%x < x/2 else '1'
num -= x
x *= 2
return bits
def bit_lookup_num(bits):
x = 2
num = 0
for b in bits:
num += x//2 if b == '0' else x
x *= 2
return num-1
Вот неэлегантный способ сделать это:
import math
def num_lookup_bit(lookup: int) -> str:
log = int(math.log2(lookup))
diff = lookup - sum(2**i for i in range(1, log))
return f"{diff:0{log}b}"
def bit_lookup_num(lookup: str) -> int:
length = len(lookup)
return sum(2**i for i in range(1, length)) + int(lookup, 2)
Главное, что нужно понять, это то, что вы сначала индексируете «бункер», который соответствует двоичной цифре, а затем считаете оттуда!
Вероятно, есть очень очевидный и элегантный способ сделать это, но вышеописанное, похоже, работает для меня.
Ваши битовые последовательности просто, возьмите двоичное представление val+2, отрежьте начальный 1
и поменяйте местами то, что осталось:
def bit_sequence(val):
# [3:] removes the '0b1'
return bin(val+2)[3:][::-1]
# return bin(val+2)[:2:-1] would be a bit faster, but a bit harder to understand
def val_for_bit_sequence(bits):
binary = '1' + bits[::-1]
return int(binary, 2) - 2
как ты вообще это понял
Присвоение целых чисел битовым последовательностям обычно заканчивается чем-то вроде простого подсчета, поэтому я искал различия между этим шаблоном и обычным подсчетом в двоичном виде и выяснил, как компенсировать эти различия. Добавление цифры 1
делает значащие начальные нули больше не ведущими нулями, а реверсирование компенсирует тот факт, что ваши битовые последовательности подсчитываются с прямым порядком байтов, а не с обратным порядком байтов.
когда вы говорите «биты», вы имеете в виду
str
объект?