优化执行时间以检查单词的字符是否在列表中 python

Question

我正在编写 python2.7.15 代码来访问单词中的字符。我如何优化这个过程，以便检查每个单词是否都包含在外部列表中？

我已经尝试了两个版本的 python2 代码：版本 (1) 是我的代码必须执行的扩展版本，而在版本 (2) 中，我尝试了相同代码的压缩版本。

chars_array = ['a','b','c']

VERSION (1)
def version1(word):
    chars =[x for x in word]
    count = 0

    for c in chars:
        if not c in chars_array:
            count+=1

    return count

VERSION (2)
def version2(word):
    return sum([1 for c in [x for x in word] if not c in chars_array])

我正在分析一个大型语料库，对于版本 1，我获得了 8.56 秒的执行时间，而对于版本 2，它是 8.12 秒。

Answer 1

最快的解决方案（对于极长的字符串最多可以快 100 倍）：

joined = ''.join(chars_array)
def version3(word):
    return len(word.translate(None, joined))

与您的代码速度大致相同的另一个较慢的解决方案：

from itertools import ifilterfalse
def version4(word):
    return sum(1 for _ in ifilterfalse(set(chars_array).__contains__, word))

时间（s是一个随机字符串）：

In [17]: %timeit version1(s)
1000 loops, best of 3: 79.9 µs per loop

In [18]: %timeit version2(s)
10000 loops, best of 3: 98.1 µs per loop

In [19]: %timeit version3(s)
100000 loops, best of 3: 4.12 µs per loop # <- fastest

In [20]: %timeit version4(s)
10000 loops, best of 3: 84.3 µs per loop

Answer 2

chars_array = ['a', 'e', 'i', 'o', 'u', 'y'] 和 words 等于一个列表在 56048 个英语单词中，我在 IPython 提示符下使用类似于以下的命令测量了一些变体：

%timeit n = [version1(word) for word in words]

在每种情况下，它都报告“10 次循环，3 次中最好”，并且我已经显示了每次循环的时间在下面每个函数定义旁边的注释中：

# OP's originals:

def version1(word):  # 163 ms
    chars =[x for x in word]
    count = 0
    for c in chars:
        if not c in chars_array:
            count+=1
    return count

def version2(word):  # 173 ms
    return sum([1 for c in [x for x in word] if not c in chars_array])

现在让我们点击 version1 和 version2 三项优化：

删除冗余列表理解并直接遍历 word；
使用运算符 not in 而不是取反 in 运算符的结果；
检查 set 而非 list 的（非）成员资格。

_

chars_set = set(chars_array)

def version1a(word):  # 95.5 ms
    count = 0
    for c in word:
        if c not in chars_set:
            count+=1
    return count

def version2a(word):  # 104 ms
    return sum([1 for c in word if c not in chars_set])

所以多行代码实际上比列表推导更有优势。不过，这可能取决于单词长度：version2a 必须分配一个与单词长度相同的新列表，而 version1a 则不需要。让我们通过对生成器表达式而不是列表理解求和来进一步改进 version2a 以赋予它相同的优势：

def version2b(word):  # 111 ms
    return sum(1 for c in word if c not in chars_set)

令我惊讶的是，这实际上适得其反——但同样，这种影响可能取决于字长。

终于让我们体验一下.translate()的强大：

chars_str = ''.join(chars_set)

def version3(word):  # 40.7 ms
    return len(word.translate(None, chars_str))

我们有明显的赢家。

优化执行时间以检查单词的字符是否在列表中 python

Optimizing execution-time to check if chars of a word are in a list python

python

execution-time

python-2.7