0

我有一个包含数千个浮点数的列表，我希望能够按最小值和最大值对其进行切片。

EG使用：

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

（我的实际列表是 400,000 个浮点数，但上面是一个工作示例）

我想要类似的东西

def listclamp(minn, maxn, nlist):

这样

print listclamp(3, 8, flist)

应该给我

[3.3333, 5.4325, 7.6855]

我还需要这样做 10,000 到 30,000 次，所以速度确实很重要。

（到目前为止，我没有尝试过的示例代码，因为这对我来说是新的 python 领域）

4

3 回答 3

4

显而易见的事情是排序然后过滤，或者过滤然后排序。

如果您每次都有相同的列表，那么首先排序显然是一种胜利，因为这样您只需要排序一次而不是每次都排序。这也意味着您可以使用二进制搜索而不是线性遍历进行过滤（如ventsyv 的回答中所解释的那样- 尽管除非您的列表比这个列表长得多，否则这可能不会得到回报。

如果您每次都有不同的列表，那么首先过滤可能是一种胜利，因为排序可能是缓慢的部分，而您正在以这种方式对较小的列表进行排序。

但是，让我们停止猜测并开始测试。

使用包含数千个浮点数的列表，其中大约一半在范围内：

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

因此，过滤然后排序获胜；ventsyn 的算法确实弥补了部分差异，但不是全部。但是当然，如​​果我们只有一个列表要排序，那么排序一次而不是数千次是明显的胜利：

In [1596]: l = sorted(flist)
In [1597]: %timeit l[bisect.bisect_left(l, 3):bisect.bisect_right(l, 8)]
10000 loops, best of 3: 29.2 µs per loop

因此，如果您一遍又一遍地拥有相同的列表，显然将其排序一次。

否则，您可以对您的真实数据进行测试……但我们正在谈论将需要几毫秒的时间减少高达 22% 的费用。即使您执行了数千次，也可以为您节省不到一秒钟的时间。仅仅键入不同实现的成本——更不用说理解它们、概括它们、调试它们以及对它们进行性能测试——远不止这些。

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

假设您首先将值存储在数组中，它是如何叠加的？

In [1607]: flist = np.random.random(5000) * 10
In [1608]: %timeit a = np.sort(flist); a = a[3 <= a]; a = a[a < 8]
1000 loops, best of 3: 742 µs per loop
In [1611]: %timeit c = b[3 <= b]; d = c[c < 8]
10000 loops, best of 3: 29.8 µs per loop

因此，对于“不同列表”的情况，它比过滤和排序快大约 4 倍，即使使用笨拙的算法（我一直在寻找可以塞进%timeit一行的东西，而不是最快或最易读的……）。对于“一遍又一遍的相同列表”的情况，即使没有平分，它也几乎与平分解决方案一样快（当然你也可以使用 NumPy 平分）。

于 2014-11-19T22:21:36.473 回答
1

对列表进行排序（如果您一遍又一遍地使用同一个列表，只需排序一次），然后使用二分搜索查找下限和上限的位置。想想看，有一个包可以 - bisect。

于 2014-11-19T22:05:57.327 回答
1

这将返回您想要的排序列表：

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)

一种更快的方法，使用列表推导：

def listclamp2(minn, maxn, nlist): 
    return sorted([x for x in flist if (minn <= and x<=maxn)])

print listclamp2(3, 8, flist)

请注意，根据您的数据，最好先过滤列表然后对其进行排序（就像我在上面的代码中所做的那样）。

有关性能的更多信息，请参阅此链接。

于 2014-11-19T22:07:46.287 回答