Python中按值划分的float列表

2024-03-29 14:07:08 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个几千个浮动列表,我希望能够按最小值和最大值进行切片。在

例如,使用:

flist = [1.9842, 9.8713, 5.4325, 7.6855, 2.3493, 3.3333]

(我的实际列表是400000个floats long,但以上是一个有效的例子)

我想要一些

^{pr2}$

就这样

print listclamp(3, 8, flist)

应该给我

[3.3333, 5.4325, 7.6855]

我还需要做10000到30000次,所以速度很重要。在

(到目前为止,我还没有尝试过的示例代码,因为这对我来说是一个新的python领域)


Tags: 代码示例列表切片速度领域long例子
3条回答

对列表进行排序(如果反复使用同一个列表,则只对其排序一次),然后使用二进制搜索来查找上下界的位置。 想想看,有一个包是两半的。在

最明显的方法是先排序后过滤,或者先过滤后排序。在

如果你每次都有相同的列表,那么首先排序显然是一种胜利,因为你只需要排序一次,而不是每次都排序。这也意味着你可以使用二进制搜索来过滤,而不是线性搜索(如ventsyv's answer中所解释的那样),尽管除非你的列表比这张长得多,否则这可能不会有回报。在

如果你每次都有不同的列表,那么先过滤可能是一种胜利,因为排序可能是最慢的部分,而你用这种方式对一个较小的列表进行排序。在

但让我们停止猜测,开始测试。在

使用几千个浮动的列表,其中大约一半在范围内:

In [1591]: flist = [random.random()*10 for _ in range(5000)]
In [1592]: %timeit sorted(x for x in flist if 3 <= x < 8)
100 loops, best of 3: 3.12 ms per loop
In [1593]: %timeit [x for x in sorted(flist) if 3 <= x < 8]
100 loops, best of 3: 4 ms per loop
In [1594]: %timeit l=sorted(flist); l[bisect.bisect_left(l, 3):bisect.bisect_right(l, 8)]
100 loops, best of 3: 3.36 ms per loop

因此,先过滤后排序是成功的;文森的算法确实弥补了部分差异,但并非全部。当然,如果我们只有一个列表可以排序,那么将其排序一次而不是数千次是一个明显的胜利:

^{pr2}$

所以,如果你有相同的列表一遍又一遍,显然要排序一次。在

否则,你可以测试你的真实数据…但是我们说的是在几毫秒的时间里减少22%。即使你做了几千次,也能节省你不到一秒钟的时间。只是键入不同实现的成本远远低于理解它们、泛化它们、调试它们和对它们进行性能测试的成本远不止这些。在


但实际上,如果您正在执行分布在数十万个值上的数百万个操作,并且速度很重要,那么您首先不应该使用列表,而应该使用NumPy数组。NumPy可以只存储原始的float值,而不将它们作为Python对象装箱。除了节省内存(并改善缓存的局部性),这意味着,np.sort中的内部循环比sorted中的内部循环快,因为它不必进行最终涉及两个数字拆箱的Python函数调用,它只需直接进行比较。在

假设您首先将值存储在一个数组中,那么它是如何堆积起来的?在

^{3}$

因此,对于“不同列表”的情况,它比过滤和排序快4倍,甚至使用一个笨拙的算法(我在寻找可以塞进一行的东西,而不是最快或最可读的东西…)。对于“一次又一次的同一个列表”的情况,即使不进行平分,它也几乎和平分法一样快(但当然,你也可以用NumPy平分)。在

这将返回所需的已排序列表:

flist = [1.9842, 9.8713, 5.4325, 7.6855, 2.3493, 3.3333]

def listclamp(minn, maxn, nlist): 
    return sorted(filter(lambda x: xminn <= x <= maxn, nlist))

print listclamp(3, 8, flist) 

一种使用list comprehensions更快的方法:

^{pr2}$

请注意,根据您的数据,最好先过滤列表,然后对其进行排序(正如我在上面的代码中所做的那样)。在

有关性能的详细信息,请参阅this link。在

相关问题 更多 >