通过字符串中的大量字符优化迭代

Question

如何通过字符串中的大量字符优化迭代？想象一下情况：

a = []
b = []
for char in characters:   # characters are string of 300 different characters (integers and letters)
if char.isalpha() and char.islower():
a.append(char)
else:
b.append(char)

如果characters中有 300 个字符(整数和字母(，如何加快执行速度？ 我尝试使用a = ''和a += char但事实证明，当我计时时，使用 list 会更快。

这是我想出的代码。它可以工作，但太慢了：

def scramble(s1, s2):
for char in s2:
if char not in s1:
return False
s2_chars, s1_chars = [], []
duplicate_chars_s2 = []
duplicate_chars_s1 = []
found_all_duplicates = True
for char in s2:
if char in s2_chars:
duplicate_chars_s2.append(char)
s2_chars.append(char)
for char in s1:
if char in s1_chars:
duplicate_chars_s1.append(char)
s1_chars.append(char)
for char in duplicate_chars_s2:
if char not in duplicate_chars_s1:
found_all_duplicates = False
return True if found_all_duplicates else False

现在尝试在s1和s2是 300 个长字符串时运行该函数。

该函数的目的是确定s1中的字符是否可以在s2中构建字符串。意义。。。我需要一段代码来计算重复字符并确定s1中是否有足够的重复项来构建所需的字符串。

Answer 1

另一个更快的解决方案，在 11.x 秒内被接受。@chepner显示的正常Counter解决方案在大约 1 秒内被接受。

def scramble(s1, s2):
it = iter(sorted(s1))
return all(c in it for c in sorted(s2))

顺便说一句，问题来了：https://www.codewars.com/kata/55c04b4cc56a697bb0000048/train/python

Answer 2

列表中的in操作可能很昂贵。如果您有很多in操作，则应使用set而不是list。您可以在python文档中阅读有关set的更多信息。简而言之，查找时间在set中为 O(1(，而list中的查找时间为 O(n(。

Python 文档还说点很昂贵，因为每次迭代都必须重新评估。您可以使用以下内容摆脱它们：

a = []
a_append = a.append
a_append('string')

这将使添加到列表中的速度更快。然后你可以把它转换成一个集合，然后做in操作，然后你应该很高兴了。

Answer 3

假设显示的代码是瓶颈(我对此表示怀疑，但让我们继续使用它(，您可以做的最昂贵的事情是重复的属性查找。

a = []
b = []
# Cache the bound methods
add_to_a = a.append
add_to_b = b.append
# Cache the unbound methods
is_alpha = str.isalpha
is_lower = str.islower
for char in characters:
if is_alpha(char) and is_lower(char):
add_to_a(char)
else:
add_to_b(char)

在涉及从string.ascii_lowercase、string.ascii_uppercase、string.digits和string.punctuation中随机选择的300个字符的测试中，上述字符需要35微秒，而原始代码需要54微秒。

不过，我会写下您的scramble，如下所示：

from collections import Counter

def scramble(s1, s2):
c1 = Counter(s1)
c2 = Counter(s2)
return all(c2[c] <= c1[c] for c in s2)

您可以从s1中的字符构建s2，只要s2中的每个字符在c1中出现的次数至少与在c2中出现的次数一样多。 用C语言实现的Counter应该能够比任何等效的Python代码更快地计算字符数。

Answer 4

我的PC上三种解决方案的基准测试(以及一些恕我直言的有趣分析(：

scramble1 0.235 seconds
scramble2 0.232 seconds
scramble3 0.054 seconds

他们的"性能测试">

是十个测试，仅描述为">测试两个字符串，最多 600000 个字符">，问题文本说"仅使用小写字母 (a-z("。因此，在我的基准测试中，我从 a-z 中s1了一串 600,000 个随机字母，并对其进行了s2随机排列。这太难了。

现在。。。所有三个解决方案在提交时都会在大约 10-12 秒内被接受(并非总是如此，由于运行时变化(。为什么第三个解决方案在那里没有更快？我有一个怀疑。正如在讨论中提到的，Python 2 解决方案不起作用，因为判断器崩溃：

Traceback (most recent call last):
File "main.py", line 51, in <module>
do_test()
File "main.py", line 17, in do_test
from random import randint, choices, shuffle
ImportError: cannot import name 'choices'

所以我想他们的法官使用choices和shuffle与我的方式相似。让我们来衡量一下：

t0 = time.perf_counter()
s1 = ''.join(random.choices(string.ascii_lowercase, k=600_000))
a2 = list(s1)
random.shuffle(a2)
s2 = ''.join(a2)
t1 = time.perf_counter()
print(t1 - t0)

大约需要 0.65 秒。远远超过解决方案所需的 0.05 到 0.24 秒！因此，我怀疑总时间包括法官生成输入的时间，到目前为止，这是总时间的大部分。

基准代码：

import string
import random
from timeit import timeit
from collections import Counter
def scramble1(s1, s2):
c1 = Counter(s1)
c2 = Counter(s2)
return all(c2[c] <= c1[c] for c in s2)
def scramble2(s1, s2):
it = iter(sorted(s1))
return all(c in it for c in sorted(s2))
def scramble3(s1, s2):
return all(s1.count(c) >= s2.count(c) for c in set(s2))
# Generate hardest test case
s1 = ''.join(random.choices(string.ascii_lowercase, k=600_000))
a2 = list(s1)
random.shuffle(a2)
s2 = ''.join(a2)
# Run the benchmarks
for _ in range(3):
for scramble in scramble1, scramble2, scramble3:
seconds = timeit(lambda: scramble(s1, s2), number=1)
print(scramble.__name__, '%.3f' % seconds, 'seconds')
print()

还有一件事：迄今为止最快的解决方案是遍历每个字符串 26 次的解决方案。当它完成 4.6 倍的工作时，它怎么能快26倍?!?嗯，这是因为在字符串中搜索单个字符的速度快得令人难以置信。我不久前测量了一下(虽然我认为它是index，而不是count(，发现它每秒检查 50 亿个字符。是的，b·伊利恩！更令人震惊的是，它使用的是 4 GHz CPU！它如何检查每个 CPU 周期的多个字符?!?我检查了源代码，如果我没记错的话，它在内部使用 C 的memchr，而 C 又使用一些多字节 CPU 指令同时检查多个字节。