在给定字母的所有可能的4字符字符串中找到4字符字符串索引的有效方法

Question

这：

A = b'abcdefghijklmnopqrstuvwxyz0123456789!'
n = len(A)
def f(s):
t = 0
for i, c in enumerate(s):
t += A.index(c) * n ** (3 - i)
return t
print(f(b'aaaa'))  # first possible 4-char string, should be 0
print(f(b'aaab'))  # 2nd possible 4-char string, should be 1
print(f(b'!!!!'))  # last possible 4-char string, should be 37^4 - 1

在用字母表A组成的所有可能的4个字符串中查找4个字符字符串的索引，但由于有许多A.index()调用，这似乎并不有效。

如何在用字母表A组成的所有可能的4字符字符串中快速有效地找到4字符字符串的索引

Answer 1

我的意思是，我能想到的唯一方法是使用一个愚蠢的无分支公式来按原样计算索引，但我没有其他东西可以提供给你。

A = b'abcdefghijklmnopqrstuvwxyz0123456789!'
n = len(A)
def f(s,A):
t = 0
for i, c in enumerate(s):
t += A.index(c) * n ** (3 - i)
return t
def g(s,A):
t = 0
for i, c in enumerate(s):
t += (c - 97 + (c<97)*75 + (c<48)*25) * n ** (3 - i)
return t

print(f(b'aaaa',A),g(b'aaaa',A))  # first possible 4-char string, should be 0
print(f(b'aaab',A),g(b'aaab',A))  # 2nd possible 4-char string, should be 1
print(f(b'!!!!',A),g(b'!!!!',A))  # last possible 4-char string, should be 37^4 - 1
import timeit
ft = timeit.timeit(lambda: 'f(b"aop!")',number=1000000)
gt = timeit.timeit(lambda: 'g(b"aop!")',number=1000000)
print(f'f: {ft}, g: {gt}, factor: {ft/gt}')

输出：

0 0
1 1
1874160 1874160
f: 0.12712620000820607, g: 0.06313459994271398, factor: 2.0135741752312635

编辑：我尝试了另一件事：

def h(s):
arr = np.array(list(s))
return sum( (arr - 97 + (arr<97)*75 + (arr<48)*25) * n ** (3 - np.array([0,1,2,3])) )

输出：

0 0 0
1 1 1
1874160 1874160 1874160
f: 0.10835059999953955, g: 0.07444929995108396, h: 0.06341919989790767,
factor f/g: 1.4553608975602195, factor f/h: 1.7084826073801391

Answer 2

我不知道您为什么关心代码的速度效率。A.index()对于每个字符只执行一次，因此在您的示例中执行了4次。当然，你可以通过使用字典来提高速度。因此，首先创建一个字典，如：

alphabet_index_lookup = {'a': 0, 'b': 1, ..., '!': 37} 

然后使用它来查找字符的索引。这要快得多，因为python在内部使用哈希映射来查找密钥，而不仅仅是遍历列表。更多背景&比较：https://towardsdatascience.com/faster-lookups-in-python-1d7503e9cd38

但正如前面提到的：除非您将f()应用于真正长的字符串，否则不会产生显著的差异。