Python:如何在未排序列表(大型数据集)中查找大于某个数字的所有项目

Question

虽然，其他人也问过类似的问题，例如这里，但它们略有不同，并没有真正解决我的问题，所以我再来一次。

我有 N 个列表 （N>20,000

），每个列表包含 M 个列表 （ M>20,000），按以下方式（数据是虚拟的）：

Key1: [ [4,3,1], [5,1,0] ...... [43,21,0 ] ]   # List 1 with collection of M smaller lists
:
:
KeyN: [ [5,4,1], [55,1,1] ...... [ 221, 0, 0] ] # Nth list

数据未排序。一个接一个地迭代阈值列表，比如Threshold =[2, 3, 5, 7, 8]，其中阈值应用于中间元素，我想提取所有元素，对于所有键，大于阈值。例如，根据我上面写的数据，Threshold = 2会产生

 For Key1: [ [4,3,1], [43,21,0]]
 :
 : 
 For KeyN: [[5,4,1]]

其他阈值也是如此。由于列表太多，我的观察是排序会导致大量开销，因此我想避免它。在python中执行此操作的最佳方法是什么？另一个重要的一点是，我自己构建数据，因此可能有一个更好的数据结构来存储数据。我目前以PersistentList的形式将数据存储在ZODB的Btree容器中，这是在这里建议的。以下是用于它的代码片段：

for Gnodes in G.nodes():      # Gnodes iterates over N values 
    Gvalue = someoperation(Gnodes)
    for Hnodes in H.nodes():  # Hnodes iterates over N values 
        Hvalue =someoperation(Hnodes,Gnodes)
        score = SomeOperation on (Gvalue,Hvalue)
        btree_container.setdefault(Gnodes, PersistentList()).append([Hnodes, score, -1 ])
    transaction.savepoint(True)  
transaction.commit()

关于最有效的方法应该是什么的任何建议？排序优先真的是最佳方法吗？

Answer 1

使用生成器推导：

(sublist for sublist in Key1 if sublist[1] > Threshold)

生成器仅按需计算元素，并且由于它按顺序遍历列表的元素，因此无需排序。（也就是说，它在每个Keyn的长度上以线性时间运行，而不是 M*log（M） 进行排序。

等价地，在函数式风格中（仅在 Python 3 中等效;对于 Python 2，请使用 itertools.ifilter）：

filter(lambda sublist: sublist[1] > Threshold, Key1)

如果Keyn列表存储在列表（或其他可下标对象）中，则可以一次处理所有列表（显示一些替代样式）：

filtered_Keys = [(sublist for sublist in Key if sublist[1] > Threshold)
    for Key in Keys
]

或

filtered_Keys = list(map(
    lambda Key: filter(lambda sublist: sublist[1] > Threshold, Key1),
    Keys
))

此方法相对于排序的性能

此方法是否比排序快取决于 M 和您拥有的阈值 T 的数量。运行时间（对于每个Key列表）为 O（M * T）。如果对列表进行排序（O（M * log（M））），则可以对每个阈值使用二进制搜索，给出 O（M * log（M） + T * log（M）） = O（max（M， T） * log（M））的总运行时间。当 T 相对于 M 足够大时，排序速度更快。我们无法先验地知道常量，因此请测试两种方法，看看给定数据时是否更快。

如果两者都不够快，请考虑编写自己的线性时间排序。例如，基数排序可以推广为处理（非负）浮点数。如果你真的关心这里的性能，你可能不得不把它写成C或Cython扩展。

Answer 2

在numpy中，您可以使用NxMx3数组轻松执行此操作：

data = array([
    [ [4,3,1], [5,1,0],  [43,21,0]    ],
    [ [5,4,1], [55,1,1], [ 221, 0, 0] ]
    ])
data[ data[:,:,1]>2 ]

这将返回：

array([[ 4,  3,  1],
   [43, 21,  0],
   [ 5,  4,  1]])

如果需要超过阈值的元素的位置，请使用 argwhere（）。

编辑：

也可以同时进行多个阈值比较：

>>> mask = data[:,:,1,np.newaxis] > array([[[2, 3, 4]]])
>>> data[mask[...,0]]
array([[ 4,  3,  1],
   [43, 21,  0],
   [ 5,  4,  1]])
>>> data[mask[...,1]]
array([[43, 21,  0],
   [ 5,  4,  1]])
>>> data[mask[...,2]]
array([[43, 21,  0]])