穿越特定列表的最快方法是什么？

Question

假设我有一个列表：

list=['plu;ean;price;quantity','plu1;ean1;price1;quantity1']

我希望能够遍历列表+通过";"拆分列表并加入if子句，就像这样：

for item in list:
    split_item=item.split(";")
    if split_item[0] == "string_value" or split_item[1] == "string_value":
        do something.....

我在想，这是最快的方法吗？假设我的初始列表更大（有更多的列表项）。我尝试使用列表推导式：

item=[item.split(";") for item in list if item.split(";")[0] == "string_value" or item.split(";")[1] == "string_value"]

但是这实际上给我带来了更慢的结果。第一种情况平均需要90毫秒，而第二种情况平均需要130毫秒。我是不是在列表推导式上做错了什么？有没有更快的解决方案？

- sale1902

---

第一种情况下，您只调用item.split(";")一次。在第二种情况下，您将调用item.split(";")三次。第二种情况肯定会更慢。 - wflynny

另外，如果您正在处理表格数据，那么值得考虑使用像pandas这样的库。当您可以向量化操作时，与纯Python循环相比，您可以获得显着的性能优势，尽管这当然完全取决于您未提及的问题部分。 - DSM

Answer 1

我在想，这是最快的方法吗？

当然不是。你可以使用手写汇编比在Python中实现更快。那又怎样呢？

如果“做某事…”不是微不足道的，并且有许多匹配项，则执行100000次所需的成本将比循环500000次的成本要高得多，因此找到最快的循环方式根本没有关系。

事实上，每次循环调用2-3次split而不是记住并重复使用结果将淹没迭代的成本，而在您只关心两个结果时不传递maxsplit参数也可能如此。

因此，您正在尝试优化错误的内容。但是，如果在修复其他所有内容之后，迭代的成本确实很重要怎么办？

好吧，您无法直接使用理解来加速，因为理解是用于返回值的表达式，而不是执行操作的语句。

但是，如果查看代码，您将意识到实际上正在做三件事：拆分每个字符串，然后过滤掉不匹配的字符串，然后执行“做某事”。因此，您可以为前两部分使用理解，然后仅对通过过滤器的值较小的列表使用缓慢的for循环。

看起来您已经尝试过了，但您犯了两个错误。

首先，使用生成器表达式而不是列表理解更好-您不需要一个列表，只需要迭代的东西，因此不要付出建立它的代价。

其次，您不想三次split字符串。您可能可以找到一些复杂的方法，在单个理解中一次完成split，但为什么要麻烦呢？只需将每个步骤编写为自己的步骤即可。

split_items = (item.split(';') for item in items)
filtered_items = (item for item in split_items 
                  if item[0] == "string_value" or item[1] == "string_value")
for item in filtered_items:
    do something...

这样做真的会更快吗？如果你能获得一些真实的测试数据和“操作...”代码，证明迭代是瓶颈，那么你可以在实际数据和代码上进行测试。在此之前，没有什么可以测试的。

- abarnert

---

filtered_items = (item for item in split_items if item[0] == "string_value" or item[1] == "string_value") - sale1902

它给出了与我的第一个案例相同的结果，但是你让我开了眼界:) - sale1902

@sale1902：谢谢你发现了这个问题。 - abarnert

Answer 2

只有当从str.split(';', 2)检索到的前两个项满足条件时，才能拆分整个字符串：

>>> strs = 'plu;ean;price;quantity'
>>> strs.split(';', 2)
['plu', 'ean', 'price;quantity']

仅当前两个项目满足条件时，才拆分第三个项目（'price;quantity'）：

>>> lis = ['plu;ean;price;quantity'*1000, 'plu1;ean1;price1;quantity1'*1000]*1000

普通的for循环，对列表中的每个项进行单独的字符串分割。

>>> %%timeit
for item in lis:
    split_item=item.split(";")
    if split_item[0] == "plu" or split_item[1] == "ean":pass
... 
1 loops, best of 3: 952 ms per loop

与上面的for循环等价的列表推导式：

>>> %timeit [x for x in (item.split(';') for item in lis) if x[0]== "plu" or x[1]=="ean"]
1 loops, best of 3: 961 ms per loop

按需拆分：

>>> %timeit [[x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== "plu" or y=="ean"]
1 loops, best of 3: 508 ms per loop

当然，如果列表和字符串很小，那么这种优化就不重要了。

- Ashwini Chaudhary

---

我同意这是问题所在：如果你只需要前两个元素，就不要将整个列表分开。 - nickie

这里的优势完全取决于混合。如果if条件几乎总是成功，那么你应该进行完整的分割；如果if条件“几乎从不”成功，那么你应该先分离前两个元素并测试它们。交叉点的位置取决于诸如列表的平均长度以及部分分割所需时间与完全分割所需时间的比较等因素。 - Michael Lorton

这是最好的解决方案，至少对于我的情况来说，在我的测试列表中降低到了80毫秒。由于我的结果（来自if条件）将始终是唯一的，在那种情况下，这是目前最好的解决方案。 - sale1902

Answer 3

我在这里找到了一个不错的替代方案。

你可以使用 map 和 filter 的组合。尝试这样做：

>>>import itertools
>>>splited_list = itertools.imap(lambda x: x.split(";"), your_list)
>>>result = filter(lambda x: filter(lambda x: x[0] == "plu" or x[1] == "string_value", lista)

第一个项目将创建元素的迭代器。第二个项目将对其进行过滤。 我在我的IPython笔记本shell中运行了一个小型基准测试，并得到了以下结果：

第一项测试:

对于小尺寸的情况，单行解决方案效果更好。

第二个测试：

如果列表更大，使用map/filter的解决方案会稍微更好一些。

第三个测试：

使用具有大型元素的大列表,map/filter方法更好。

随着列表大小的增加，性能差异不断增加，直到在10000个元素的测试中达到66％的高峰。

map/filter解决方案与列表推导式解决方案之间的差异在于对.split()的调用次数。前者每个项目调用3次，后者仅一次，因为列表推导式只是将map/filter结合在一起的Pythonic方式。我过去经常使用列表推导式，并认为自己不知道lambda的全部内容。直到我发现map和列表推导式是相同的东西。

如果你不关心内存使用，可以使用常规的map而不是imap。它会一次性创建带有拆分的列表。它将使用更多内存来存储它，但速度稍快。

实际上，如果您不关心内存使用，可以使用2个列表推导式编写map/filter解决方案，并获得完全相同的结果。请查看：

- Lucas Ribeiro

---

imap和ifilter与生成器表达式的作用相同，只是它们接受一个_函数_而不是一个表达式。对于map和filter与列表推导式也是如此。如果你的表达式只是“调用这个函数”，那就没有问题；事实上，这是一个好处。但是，如果你的表达式是x[0] == "plu" or x[1] == "string_value"，将其包装在一个函数中会减慢速度（因为每次循环都要多一次函数调用），并且使事情变得更加难以阅读（因为那个lambda x:只会妨碍你）。 - abarnert

但是你绝对可以在懒惰（imap/ifilter/genexpr）和严格（map/filter/listcomp）之间取得平衡。如果你正在过滤以保留N个值中的M个，那么在严格变体中浪费的M个列表构建步骤的成本很容易被懒惰变体中不必经过N个迭代器协议步骤的好处所抵消，因此如果M << N，则filter或listcomp通常会获胜。 - abarnert

最后，测试非常小心。如果你的最后一步只是构建一个genexpr/imap/ifilter, 但你从未迭代它，那么你还没做什么！请确保在timeit中循环它(或者为了尽可能少的测试开销，将其提供给一个 collections.deque(max_len=0) )。 - abarnert

但我将imap生成器传递给过滤器。遍历整个生成器就足够了，不是吗？ - Lucas Ribeiro

是的，只要最后一步严格执行，一切都没问题。我并不认为你是偶然得到了正确结果；我想这是有意为之，但我想为其他读者（特别是那些习惯于 Python 3 的人，其中 map 和 filter 是惰性的）澄清一下。 - abarnert

Answer 4

编辑：事实证明正则表达式缓存对竞争有些不公平。我的错。正则表达式只比较快一点点。

如果你追求速度，hcwhsa的答案应该足够好了。如果你需要稍微更快一些，可以考虑使用re模块。

import re
from itertools import chain

lis = ['plu;ean;price;quantity'*1000, 'plu1;ean1;price1;quantity1'*100]*1000

matcher = re.compile('^(?:plu(?:;|$)|[^;]*;ean(?:;|$))').match
[l.split(';') for l in lis if matcher(l)]

时间安排，对于大多数积极的结果来说（也就是说，split 是减慢速度的主要原因）：

SETUP="
import re
from itertools import chain
matcher = re.compile('^(?:plu(?:;|$)|[^;]*;ean(?:;|$))').match

lis = ['plu1;ean1;price1;quantity1'+chr(i) for i in range(10000)] + ['plu;ean;price;quantity' for i in range(10000)]
"

python -m timeit -s "$SETUP" "[[x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== 'plu' or y=='ean']"
python -m timeit -s "$SETUP" "[l.split(';') for l in lis if matcher(l)]"

我们看到我的速度稍微快一点。

10 loops, best of 3: 55 msec per loop
10 loops, best of 3: 49.5 msec per loop

对于大多数负面结果（大部分内容都被过滤）：

SETUP="
import re
from itertools import chain
matcher = re.compile('^(?:plu(?:;|$)|[^;]*;ean(?:;|$))').match

lis = ['plu1;ean1;price1;quantity1'+chr(i) for i in range(1000)] + ['plu;ean;price;quantity' for i in range(10000)]
"

python -m timeit -s "$SETUP" "[[x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== 'plu' or y=='ean']"
python -m timeit -s "$SETUP" "[l.split(';') for l in lis if matcher(l)]"

引线稍微高一点。

10 loops, best of 3: 40.9 msec per loop
10 loops, best of 3: 35.7 msec per loop

---

如果结果始终唯一，请使用：

next([x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== 'plu' or y=='ean')

或者更快的正则表达式版本

next(filter(matcher, lis)).split(';')

(在Python 2中使用itertools.ifilter).

时间:

SETUP="
import re
from itertools import chain
matcher = re.compile('^(?:plu(?:;|$)|[^;]*;ean(?:;|$))').match

lis = ['plu1;ean1;price1;quantity1'+chr(i) for i in range(10000)] + ['plu;ean;price;quantity'] + ['plu1;ean1;price1;quantity1'+chr(i) for i in range(10000)]
"

python -m timeit -s "$SETUP" "[[x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== 'plu' or y=='ean']"
python -m timeit -s "$SETUP" "next([x] + [y] + z.split(';') for x, y, z in (item.split(';', 2) for item in lis) if x== 'plu' or y=='ean')"

python -m timeit -s "$SETUP" "[l.split(';') for l in lis if matcher(l)]"
python -m timeit -s "$SETUP" "next(filter(matcher, lis)).split(';')"

结果：

10 loops, best of 3: 31.3 msec per loop
100 loops, best of 3: 15.2 msec per loop
10 loops, best of 3: 28.8 msec per loop
100 loops, best of 3: 14.1 msec per loop

所以这对两种方法都有很大的提升。

- Veedrac

---

哇，正则表达式不是我的强项，但这将其降至40毫秒。由于在我的情况下，除了1件事被过滤掉，这绝对是最好的解决方案。 - sale1902

我想知道你是否取消了这个操作？如果是，为什么？另外，我有一个新的方法，可以更快地找到唯一解决方案，包括使用和不使用正则表达式。 - Veedrac

原来正则表达式缓存有些不公平。无论如何，您可能想重新查看我答案的最后一部分。 - Veedrac

嘿，伙计，我不知道为什么这个被拒绝了。也许是我不小心做错了。你的解决方案对我来说是最好的。因为我正在将我的代码移植到Windows移动设备（使用Python 2.5的PyCe端口），这就是我需要性能的原因：）。再次感谢。 - sale1902

由于Python 2.5中没有包含itertools，因此我使用了以下代码，目前为止给出了最佳结果：[next(l.split(';') for l in list if matcher(l))]。我尝试了在stackoverflow上找到的多种解决方案，但目前这个代码给出了最佳结果。 - sale1902

这在移动设备上仍然有点慢（640MHz ARM CPU :()，但比以前快得多。是否可能在某些其他数据结构上执行更快的循环/查找数据，而不是列表？我没有找到这个... - sale1902