python - 将数字从一个列表移动到另一个列表的最快方法

Question

我有一个清单：

list1=[1,8,2,9,3,8,7,10]

我想知道将以上所有值拉到“7”并将它们放入新列表中的绝对最快方法。我不想使用 for 循环，当列表中有数亿个项目时，这会花费太长时间。

所以理想情况下是这样的：

list1=[1,8,2,9,3,8,7,10]
list2=AboveNumber(7,list1)
print list2
>>>[8,9,8,10]

感谢您的任何建议！处理时间赞赏！

Answer 1

我不会太担心维护排序顺序和使用numpy：

import numpy as np
a = np.arange(50)
print a[a >= 7]

#[ 7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49]

如果您有已排序的项目，则可以使用该bisect模块（或numpy有自己的方法来处理已排序的数据）：

import bisect

items = range(50)
index = bisect.bisect_left(items, 7)
print items[index:]
# [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]

并按排序顺序添加项目：

bisect.insort_left(items, 3)
print items
#[0, 1, 2, 3, 3, 4, 5, .. snip ...]

Answer 2

如上所述，第一个解决方案是对列表进行排序并仅保留感兴趣值之后的部分。使用 ipython 单元格 timeit

data = randint(10,size=2000)

天真的方法

%%timeit
[ i for i in data if i>7 ]
# 1.8 ms per loop

排序方法

data2 = sorted(data)
import bisect

%%timeit
data2[bisect.bisect(data2,7):]
# 13.6 us per loop

但总的来说，如果您必须处理数值数据，我强烈建议您使用numpy库。用朴素的方法已经几乎和排序方法一样快了

import numpy as np
adata = np.array(data)

%%timeit
adata[adata>7]
# 28.5 us per loop

但即使使用 numpy 数组，您也可以使用排序方法：

adata.sort()

%%timeit
adata[adata.searchsorted(7):]
# 2.1 us per loop

数组越大，numpy 数组的性能越好，它接近于优化的 C 例程（实际上，它们是一堆优化的 C 代码，你只需支付调用 python 包装器的重载）

编辑：

请注意，速度之间的关系随数组大小而变化。朴素的 numpy 方法和列表的排序方法对于大约 5*10^5 个元素的速度相同，而在相同的大小下，带有排序数组的 numpy 方法或多或少快 3000 倍。

Answer 3

AboveNumber 不能做任何魔术。如果列表是无序的，它必须遍历列表中的所有项目。

您可以通过按顺序维护列表来优化这一点，即确保列表始终在插入或擦除之后排序。

如果列表是有序的，您可能会通过二进制搜索找到您的“平均值”，这比遍历所有列表要快得多，然后在该位置剪切列表。