时间戳

首页 > 解决方案 > 找到满足条件的元素数量的最快方法是什么？

python - 找到满足条件的元素数量的最快方法是什么？

问题描述

我想知道找到满足条件的列表中元素数量的最快方法，而不是元素本身，只是它们的计数。

让我解释一下：我已经知道如何尽可能快地找到满足条件的元素，即使用filter()方法。但filter返回一个没有__len__()方法的生成对象。要获得filter对象的长度，我们必须使用循环手动计算其元素，这需要大量时间，或者我们可以将对象转换为列表，如果对象包含太多，则将占用大量 RAM许多元素。

让我更好地说明这一点：我编写了一个蛮力函数，它通过使用像素对磁盘的面积求和来近似 pi。（我已经写了一个使用 Lebniz 方法的函数和另一个使用 Liu Hui 的函数。）

基本思想是，如果一个像素的 x^2+y^2<=r^2 则它在一个圆圈内。

这是代码：

from itertools import product

def pi(r):
    quardrant = product(range(r+1), repeat=2)
    quarterdisk = filter(lambda p: p[0]**2 + p[1]**2 <= r**2, quardrant)
    return (4*len(list(quarterdisk)) - 4*r + 4) / r**2

如果我输入 10000，前两行运行得非常快，但第三行需要很长时间，并且在 16 GiB RAM 中使用了多达 14 GB 的 RAM！

现在，如果我使用循环来获取长度，则它需要的 RAM 显着减少，但计算时间也更长！

那么在一个非常长的列表中找到满足要求的元素数量的最佳方法是什么？

标签： pythonpython-3.x

解决方案

首先，预先计算您多次使用的值，例如r**2. 在 r=1000 的情况下，这对我来说快了大约 30%（~1.1s → ~.85s 总运行时间）。

r_sq = r**2

接下来，为了节省内存，当您只需要知道它的长度时，不要列出过滤器。取而代之的是，对一个映射求和，或者更好的是，一个生成器表达式：

q = sum(x**2 + y**2 <= r_sq for x, y in quardrant)
return (4*q - 4*r + 4) / r_sq

这通过不构建列表节省了一些时间，但作为奖励，使用解包而不是索引也节省了惊人的时间——对我来说大约是 7%（~.74s → ~.69s 总运行时间）。

接下来，回到第一点，如果您考虑一下，您会得到xand y，product这意味着您正在计算每个数字的平方 0.. r， 2*r次。提前计算平方会更快。

quardrant_sq = product((x**2 for x in range(r+1)), repeat=2)
q = sum(a+b <= r_sq for a, b in quardrant_sq)

这带来了巨大的改进，大约快了 250%！（~.66s → ~.19s 总运行时间）。

最后，由于您只处理数字，您可以考虑使用NumPy来进一步优化您的代码。

推荐阅读