Python性能优化：从列表中删除元素

Question

Python性能优化：从列表中删除元素

12

我有一个长度为370000的列表。在这个列表中，有一些像"a", "y", "Y", "q", "Q", "p", "P"这样的项，这些项是单词的列表，但有时会出现这些单个字符。

我想从列表中删除这些字符。虽然我在Python方面还比较新手，但我脑海中首先想到的是：

for word in words:
    if word== 'm' or  word== 'y' or word== 'Y' or word== 'p' or word== 'Q' or word== 'q' or word== 'a' or word== 'uh':
        words.remove(word)

在一个拥有370,000个项目的列表中，这种方法需要花费很长时间。说真的，非常长。

有没有其他更好的想法来提高性能呢？

提前谢谢。

- NachoMiguel

6

这不仅会有性能问题，而且你也会跳过一些单词。请参见循环“忘记”删除某些项目。 - Martijn Pieters

你从哪里获取数据？ - Padraic Cunningham

随机文本。只是为了好玩。 - NachoMiguel

6个回答

3

你可以使用列表推导式，例如：

words = [word for word in words if word not in ["a", "y", "Y", "q", "Q", "p", "P", "uh"]]

列表推导通常会带来更好的性能。

编辑（感谢 Cong Ma 的结果）：

似乎使用 set 作为过滤序列可以获得最佳性能，因此您可能需要类似于以下内容：

words = [word for word in words if word not in set(("a", "y", "Y", "q", "Q", "P", "uh"))]

- Paul Evans

是的，应该比“filter()”快一点。 - Cong Ma

我想在列表推导式中创建集合可能不是非常高效的方式，而且 words[:] = ... 会改变原始列表。 - Padraic Cunningham

1

尝试使用生成器管道; 这个例子有一个简单的应用。生成器具有良好的性能，并且通常会导致更少的内存使用，因为管道不会创建巨大的临时列表（尽管我的最终列表违反了这个原则）。

bad_list = ["a", "y", "Y", "q", "Q", "p", "P", "uh"]

# here is the generator "comprehension"
good_word_stream = (word for word in open("lexicon") if word not in bad_list)

# ... and use the output for something
print [len(word) for word in good_word_stream]

- Prune

1

但是有时我会遇到那些单个字符。

我认为这里的逻辑很差。在插入单词到列表中时，应该将其排除。在长列表之后删除它是一个糟糕的选择。

我也遇到了同样的问题，起初我的解决方案是使用pypy。

我认为当时pypy存在问题（我的代码突然退出），所以我改变了代码逻辑，使用普通的Python。

- nafsaka

1

如果内存足够，那么在运行时修改列表并不是一个好主意，很容易出现错误，就像评论中所说的一样。

至于性能，list.remove 是一个O(n)操作，因此你的代码是O(N^2)。

列表推导式要快得多，因为它占用更多的空间 - 在Python 3中创建一个新的列表/或生成器，使用一个小黑名单来过滤最终结果。虽然我不确定它是否会每次都创建 ["a", "y", "Y", "q", "Q", "p", "P", "uh"]，但 Cong Ma 的删除答案提到了首先创建这个小集合（是的，集合中的a操作是O(1)操作！），这可能有助于提高性能。

而且，根据我的先前测试，列表推导式比 map 或 list(map(something)) 慢约25％，我现在无法证明，但您可能需要进行测试。

如果所有可以在Python中完成的事情都已完成，而性能仍未达到生产要求，则Pypy/Cython将是最终解决方案。

- SnoopyGuo

我暂时删除了我的答案以防止编辑。我添加了一些基准测试（虽然是虚假的，因为我使用了一些数字而不是字符串，因为我们没有原始数据）。 - Cong Ma

@CongMa，你介意帮我测试一下map和列表推导式吗？我现在离开了台式机/笔记本电脑。 - SnoopyGuo

-1

translate 1.5 faster than list comprehensions it seems
tested in 10000 runs

def remove_chars(string_, word_):
    # 10000 0.112017
    string_ += string_.upper()
    vowels_table = dict.fromkeys(map(ord, string_))
    return word_.translate(vowels_table)


def remove_chars2(string_,word_):
    # 10000 0.166002
    return [c for c in word_ if not c in string_]

- LetzerWille

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cong Ma · Accepted Answer

我在IPython中尝试了一些bogo基准测试。

import random
# Don't know how to generate your words, use integers as substitute.
words = [random.randint(0, 25) for i in xrange(370000)]
badlist = range(7)
badtuple = tuple(badlist)
badset = set(badlist)
# List comprehension
%timeit [w for w in words if w not in badlist]
10 loops, best of 3: 59.2 ms per loop
%timeit [w for w in words if w not in badtuple]
10 loops, best of 3: 64.7 ms per loop
%timeit [w for w in words if w not in badset]
10 loops, best of 3: 30.3 ms per loop
# Filter
%timeit filter(lambda w: w not in badlist, words)
10 loops, best of 3: 85.6 ms per loop
%timeit filter(lambda w: w not in badtuple, words)
10 loops, best of 3: 92.1 ms per loop
%timeit filter(lambda w: w not in badset, words)
10 loops, best of 3: 50.8 ms per loop

结论：使用not in <set>作为过滤条件的列表推导可能是最佳选择。

但正如我所说，这个基准测试是虚假的，您需要在实际遇到的数据类型上重复一些基准测试，以确定哪种方法更好。

关于为什么列表推导+“not in set”可能是最优选择的一些想法。

filter vs 列表推导： filter 实际上会调用输入可调用对象，而在Python中调用可调用对象本身就有开销（创建堆栈帧等）。与之不同的是，列表推导的条件检查（if ...子句）比调用具有较少的开销。它只是表达式评估，没有Python调用栈的全部功能。
在平均情况下，测试集成员资格的时间复杂度为O(1)，而在最坏情况下为O(n)，但列表/元组成员资格的时间复杂度始终为O(n)。