<p>最明显的方法是先排序后过滤,或者先过滤后排序。在</p>
<p>如果你每次都有相同的列表,那么首先排序显然是一种胜利,因为你只需要排序一次,而不是每次都排序。这也意味着你可以使用二进制搜索来过滤,而不是线性搜索(如<a href="https://stackoverflow.com/a/27027962/908494">ventsyv's answer</a>中所解释的那样),尽管除非你的列表比这张长得多,否则这可能不会有回报。在</p>
<p>如果你每次都有不同的列表,那么先过滤可能是一种胜利,因为排序可能是最慢的部分,而你用这种方式对一个较小的列表进行排序。在</p>
<p>但让我们停止猜测,开始测试。在</p>
<p>使用几千个浮动的列表,其中大约一半在范围内:</p>
<pre><code>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
</code></pre>
<p>因此,先过滤后排序是成功的;文森的算法确实弥补了部分差异,但并非全部。当然,如果我们只有一个列表可以排序,那么将其排序一次而不是数千次是一个明显的胜利:</p>
^{pr2}$
<p>所以,如果你有相同的列表一遍又一遍,显然要排序一次。在</p>
<p>否则,你可以测试你的真实数据…但是我们说的是在几毫秒的时间里减少22%。即使你做了几千次,也能节省你不到一秒钟的时间。只是键入不同实现的成本远远低于理解它们、泛化它们、调试它们和对它们进行性能测试的成本远不止这些。在</p>
<hr/>
<p>但实际上,如果您正在执行分布在数十万个值上的数百万个操作,并且速度很重要,那么您首先不应该使用列表,而应该使用<a href="http://numpy.org/" rel="nofollow noreferrer">NumPy</a>数组。NumPy可以只存储原始的<code>float</code>值,而不将它们作为Python对象装箱。除了节省内存(并改善缓存的局部性),这意味着,<code>np.sort</code>中的内部循环比<code>sorted</code>中的内部循环快,因为它不必进行最终涉及两个数字拆箱的Python函数调用,它只需直接进行比较。在</p>
<p>假设您首先将值存储在一个数组中,那么它是如何堆积起来的?在</p>
^{3}$
<p>因此,对于“不同列表”的情况,它比过滤和排序快4倍,甚至使用一个笨拙的算法(我在寻找可以塞进一行的东西,而不是最快或最可读的东西…)。对于“一次又一次的同一个列表”的情况,即使不进行平分,它也几乎和平分法一样快(但当然,你也可以用NumPy平分)。在</p>