2

我想从我的代码中加速该函数，该代码被非常频繁地调用。此函数接收字符串的输入列表（通常长度为 4）并生成字符串列表，其中对应的条目替换为大写字母，顺序对应于输入字符串的字母数字顺序。然后这个列表组合成一个字符串。示例：输入列表['wwTv', 'NzkT', 'wwTv', 'JhXc']，输出字符串'C,B,C,A'。在实际示例中，每个列表中有许多重复项。

你能提出更有效的解决这个特定问题的方法吗？还是我的直截了当的算法足够好，无法显着改进？

下面是我的代码示例（Python 3.2）。这里输入数据的样本是随机创建的并传递给函数f。

import timeit
import string, random

dumb_label_set = ['A', 'B', 'C', 'D', 'E']

def a(labels):
    uniq_labels = sorted(set(labels))
    dumb_labels = [dumb_label_set[uniq_labels.index(a)] for a in labels]
    s_name = ','.join(dumb_labels)
    return(s_name)

def b(labels):
    uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
    dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]
    s_name = ','.join(dumb_labels)
    return(s_name)

labels = []
for i1 in range(100000):
    labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(4)])

start = timeit.default_timer()
res_a = [a(l) for l in labels]
print(timeit.default_timer() - start)

start = timeit.default_timer()
res_b = [b(l) for l in labels]
print(timeit.default_timer() - start)

print(res_a == res_b)

结果：

0.41835449560994675
0.4420497451417873
True

我的函数a稍微快一点，然后b由 Martijn Pieters 提出

4

2 回答 2

3

我会使用字典将标签映射到索引：

uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]

使用较小的labels集合来促进在更易于管理的时间内进行多次传递会给出：

>>> import timeit
>>> import string, random
>>> dumb_label_set = ['A', 'B', 'C', 'D', 'E']
>>> def f(labels):
...     uniq_labels = sorted(set(labels))
...     dumb_labels = [dumb_label_set[uniq_labels.index(a)] for a in labels]
...     s_name = ','.join(dumb_labels)
...     return(s_name)
... 
>>> def f_dict(labels):
...     uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
...     dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]
...     s_name = ','.join(dumb_labels)
...     return s_name
... 
>>> labels = []
>>> for i1 in range(100):
...     labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(4)])
... 
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f, labels', number=10000)
6.586822032928467
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f_dict as f, labels', number=10000)
7.633307933807373

但正如您所看到的，对于您的小输入集，您的方法更快。似乎设置映射比最多 4 次.index()查找需要更多时间。

如果您的标签序列包含（更多）元素，我的方法将获胜：

>>> dumb_label_set = string.ascii_uppercase
>>> labels = []
>>> for i1 in range(100):
...     labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(26)])
... 
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f, labels', number=1000)
3.069930076599121
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f_dict as f, labels', number=1000)
2.404794931411743

这里最重要的一课是使用timeit模块来比较不同的方法。该timeit模块使用适合您平台的最佳计时器，并比较被测代码的多次运行以消除外部调度影响（磁盘 I/O、其他进程等）。

即使只计时一次， usingtimeit.default_timer也比 using 更可取time.time；它可能仍然是同一个计时器，但它将成为您平台上最准确的时钟。

于 2012-12-30T10:03:40.070 回答
1

如果你真的想让它快速工作，也可以看看 cython。当然，一定要看看这里提出的其他算法，但是一旦你选择了最快的算法，cython 仍然可以给它一个很好的提升。

目前采用您的原始方法a，b我只是将它们移动到另一个模块并使用 cython 和 gcc (-O3) 编译。没有类型信息，我得到以下时间：

a:          0.4449379859997862
b:          0.48829928699888114
a (cython): 0.29741462399942975
b (cython): 0.2461447869991389

我敢肯定，标记变量的类型可以给它另一个推动力。

于 2013-05-11T19:57:19.297 回答