Как оптимизировать str.replace () в Python

Question

Я работаю над двоичной строкой (то есть она содержит только 1 и 0), и мне нужно запустить функцию N раз.Эта функция заменяет любой экземпляр '01' в строке на '10'.Тем не менее, str.replace занимает слишком много времени для обработки выходных данных, особенно когда длина строки и N могут достигать 10 ^ 6.

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

Например, если для меня задана строка 01011, а N равно 1, то выход должен быть 10101. Аналогично, если N становится 2, выход становится 11010 и так далее.

Есть ли какие-либо оптимизации str.replace в python или есть какие-то битовые манипуляции, которые я мог бы сделать, чтобы оптимизировать мой код?

Answer 1

Давайте подумаем о входных данных как о битах, образующих целое число без знака, возможно очень большое. Например:

  1001 1011  # input number X
  0100 1101  # Y = X>>1 = X//2 -- to get the previous bit to the same column
  1001 0010  # Z1 = X & ~Y -- We are looking for 01, i.e. 1 after previous 0
  0001 0010  # Z2 = Z1 with the highest bit cleared, because we don't want
             # to process the implicit 0 before the number
  1010 1101  # output = X + Z2, this adds 1 where 01's are;
             # 1 + 01 = 10, this is what we want

Таким образом, мы можем обработать весь список с помощью всего лишь нескольких арифметических операций.

---

Обновление: пример кода, я попытался ответить на комментарий о ведущих нулях.

xstr = input("Enter binary number: ")
x = int(xstr, base=2)
digits = len(xstr)
mask = 2**(digits-1) - 1 
print("{:0{width}b}".format(x,width=digits))

while True:
    z2 = x & ~(x >> 1) & mask
    if z2 == 0:
        print("final state")
        break
    x += z2
    print("{:0{width}b}".format(x,width=digits))

Answer 2

Хотя это и не является ответом на вопрос о замене, мои предварительные исследования показывают, что правило переворачивания в конечном итоге организует все 1 в начале строки и все 0 в конце, поэтому следующая функция даст правильный ответ, если N близко к len(s).

from collections import Counter

def asymptote(s, N):
    counts = Counter(s)
    return '1'*counts['1'] + '0'*counts['0']

Я сравнил результаты с

def brute(s, N):
    for i in range(N):
        s = s.replace('01', '10')
    return s

Этот график показывает, где мы имеем согласие между методом грубой силы и асимптотическим результатом для случайных строк

Желтая часть - это то, где грубая сила и асимптотический результат совпадают. Таким образом, вы можете видеть, что вам нужно как минимум len(s)/2 сальто, чтобы получить асимптотический результат большую часть времени, а иногда вам нужно немного больше (красная линия - 3 * len (s) / 4).

Answer 3

Вот программа, о которой я говорил:

from typing import Dict

from itertools import product

table_1 = {
    "01": 1,
    "11": 0,
}

tables = {
    1: table_1
}


def _apply_table(s: str, n: int, table: Dict[str, int]) -> str:
    tl = n * 2
    out = ["0"] * len(s)
    for i in range(len(s)):
        if s[i] == '1':
            if i < tl:
                t = '1' * (tl - i - 1) + s[:i + 1]
            else:
                t = s[i - tl + 1:i + 1]
            o = table[t]
            out[i - o] = '1'
    return ''.join(out)


def _get_table(n: int) -> Dict[str, int]:
    if n not in tables:
        tables[n] = _generate_table(n)
    return tables[n]


def _generate_table(n: int) -> Dict[str, int]:
    def apply(t: str):
        return _apply_table(_apply_table(t, n - 1, _get_table(n - 1)), 1, table_1)

    tl = n * 2
    ts = (''.join(ps) + '1' for ps in product('01', repeat=tl - 1))
    return {t: len(apply(t).rpartition('1')[2]) for t in ts}


def transform(s: str, n: int):
    return _apply_table(s, n, _get_table(n))

Это не очень быстро, но transform имеет временную сложность O(M), где M - длина строки. Но сложность пространства и плохая временная сложность функции _generate_table делают ее непригодной для использования: - / (Тем не менее, возможно, что вы можете улучшить ее или внедрить ее в C для более быстрой скорости. (Это также улучшится, если вы хранить хеш-таблицы и не пересчитывать их каждый раз)