有人能帮我优化速度吗？

Question

以下是优化代码：

import random

rules = {
    'X': {
        1: 'FXFF+',
        2: '+XXF]',
    }
}

L_string = 'FX'

def next_char(c):
    isrule = rules.get(c, c)
    if not isrule == c:
        _, choice = random.choice(list(rules.get(c).items()))
        return choice
    else:
        return isrule

for _ in range(6):
    L_string = ''.join([next_char(c) for c in L_string])

这里发生的是字符串中字符的递归替换。所以一步一步：

1. 从“FX”开始
2. 遍历字符串并用随机规则替换每个“X”，即“FXFF+”或“+XXF]”。也就是说，对于每个“X”，一条规则是随机的。这不是一个随机规则，每次运行通过字符串。你知道吗
3. 重复5次

最后，结果是一个较长的字符串，由开头的“F”和规则“FXFF+”、“+XXF]”以某种随机组合形式组成。下表说明：

+------------+--------------------+--------------------+
| ITERATIONS |       STRING       | CHOSEN RULE VECTOR |
+------------+--------------------+--------------------+
|          1 | FFXFF+             | [rule 1]           |
|          2 | FF+XXF]FF+         | [rule 2]           |
|          3 | FF+FXFF++XXF]F]FF+ | [rule 1, rule 2]   |
|          4 | ...                | ...                |
|          5 | ...                | ...                |
+------------+--------------------+--------------------+

我读过回复sub是替换字符串的最快方法，但问题是每个字符的随机化。回复sub这不管用。你知道吗

谢谢大家！你知道吗

Answer 1

假设您的模式中没有出现字符{和}，您可以使用模板语言进行一些技巧，然后去掉大括号。这在我的机器上快了2.5倍：

def format_based():
    rules = {
        'X': lambda: random.choice(["{F}{X}{F}{F}+", "+{X}{X}{F}{J}]"]),
        'F': lambda: 'F',
        'J': lambda: 'J',
    }
    def get_callbacks():
        while True:
            yield {k: v() for k, v in rules.items()}
    callbacks = get_callbacks()
    L_string = "{F}{X}"
    for _ in range(5):
        L_string = L_string.format(**next(callbacks))
    return re.sub('{|}', '', L_string)

Answer 2

对消耗大部分运行时间的函数进行~4倍的简单加速。你知道吗

from random import random
from math import floor

def next_char2(c):
    if c not in rules:
        return c 

    d = rules[c]
    r = floor(random() * len(d))  # was int(...) before 
    # Rules start with key 1. 
    # Random brings a float between 0 and 1, therefore you need [r + 1] as key 
    return d[r + 1]


In [6]: %timeit next_char("X")
3.42 µs ± 32.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [7]: %timeit next_char2("X")
814 ns ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Edit: Changing the int with math.floor gives a little boost

In [10]: %timeit next_char2("X")                                                                
740 ns ± 8.57 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

可能还有很大的优化空间。也许某个地方的回忆录会给整个代码带来巨大的提升。你知道吗

Answer 3

新的递归方法，大约快1.6倍，另一种方法，大约快3.312倍在我的电脑上

import re
from random import random, choice
from timeit import timeit
from math import floor

# --- ORIGINAL ---
rules = {
    'X': {
        1: 'FXFF+',
        2: '+XXF]',
    }
}

def next_char(c):
    isrule = rules.get(c, c)
    if not isrule == c:
        _, _choice = choice(list(rules.get(c).items()))
        return _choice
    else:
        return isrule

# --- ORIGINAL END ---

def next_char2(c):
    if c not in rules:
        return c

    d = rules[c]
    r = floor(random() * len(d))  # was int(...) before
    # Rules start with key 1.
    # Random brings a float between 0 and 1, therefore you need [r + 1] as key
    return d[r + 1]

choices=['FXFF+', '+XXF]']
def next_substring(s, n):
    if s == '' or n == 0:
        return s

    first_char = s[:1]
    rest = s[1:]

    if first_char == 'X':
        first_char = choice(choices)

    if len(first_char) == 1:
        return first_char + (next_substring(rest, n) if 'X' in rest else rest)
    else:
        return (next_substring(first_char, n-1) if 'X' in first_char else first_char) + (next_substring(rest, n) if 'X' in rest else rest)

format_rules = {
    'X': lambda: choice(["{F}{X}{F}{F}+", "+{X}{X}{F}]"]),
    'F': lambda: 'F',
    'J': lambda: 'J',
}

def format_based():
    def get_callbacks():
        while True:
            yield {k: v() for k, v in format_rules.items()}
    callbacks = get_callbacks()
    L_string = "{F}{X}"
    for _ in range(6):
        L_string = L_string.format(**next(callbacks))
    return re.sub(r'{|}', '', L_string)


def method1():
    s = 0
    for i in range(100_000):
        L_string = 'FX'
        for _ in range(6):
            L_string = ''.join([next_char(c) for c in L_string])
        s += len(L_string)
    return s

def method1b():
    s = 0
    for i in range(100_000):
        L_string = 'FX'
        for _ in range(6):
            L_string = ''.join([next_char2(c) for c in L_string])
        s += len(L_string)
    return s


def method2():
    s = 0
    for i in range(100_000):
        L_string = 'FX'
        L_string = ''.join(next_substring(c, 6) if c=='X' else c for c in L_string)
        s += len(L_string)
    return s

def method3():
    s = 0
    for i in range(100_000):
        L_string = format_based()
        s += len(L_string)
    return s

rules2 = [
    ('FXFF+', '+XXF]')      # X=0
]

def new_method2(s='FX'):
    final = [s]
    s = ''
    for _ in range(6):
        for c in final[-1]:
            if c == 'X':
                s += rules2[0][floor(random() * len(rules2[0]))]    # rules2[0] because X=0
            else:
                s += c
        final.append(s)
        s = ''
    return final[-1]

def method4():
    s = 0
    for i in range(100_000):
        L_string = new_method2('FX')
        s += len(L_string)
    return s

print('Average length of result string (100_000 runs):')
print('{: <20}{: >20}'.format('Original:', method1() / 100_000))
print('{: <20}{: >20}'.format('New method:', method2() / 100_000 ))
print('{: <20}{: >20}'.format('@hilberts method:', method3() / 100_000 ))
print('{: <20}{: >20}'.format('new_method2 method:', method4() / 100_000 ))
print('{: <20}{: >20}'.format('altunyurt method:', method1b() / 100_000 ))

print('{: <20}{: >20}'.format('Timing original:', timeit(lambda: method1(), number=1)))
print('{: <20}{: >20}'.format('Timing new method:', timeit(lambda: method2(), number=1)))
print('{: <20}{: >20}'.format('Timing @hilberts method:', timeit(lambda: method3(), number=1)))
print('{: <20}{: >20}'.format('new_method2 method:', timeit(lambda: method4(), number=1)))
print('{: <20}{: >20}'.format('altunyurt method:', timeit(lambda: method1b(), number=1)))

结果是：

Average length of result string (100_000 runs):
Original:                       85.17692
New method:                     85.29112
@hilberts method:               85.20096
new_method2 method:             84.88892
altunyurt method:               85.07668
Timing original:       4.563865200005239
Timing new method:    2.6940059370026574
Timing @hilberts method:  1.9866539289942011
new_method2 method:   1.3680451929976698
altunyurt method:     1.7981422250013566

编辑：添加@hilberts方法

EDIT2:添加了另一个新方法，比原来的方法快3.32倍

EDIT3:添加@altunyurt方法