4

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

我有 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中执行此操作的最佳方法是什么?另一个重要的一点是,我自己构建数据,所以可能有更好的数据结构来存储数据。我目前将数据以容器的形式存储在PersistentListBtreeZODB这是在此处建议的。以下是用于它的代码片段:

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()

关于什么应该是最有效的方法的任何建议?首先排序确实是最佳方式吗?

4

2 回答 2

4

使用生成器理解:

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

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

等效地,在函数样式中(仅在 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(最大(M,T)* log(M))。当T相对于M足够大时,排序会更快。我们无法先验地知道常数,因此请测试两种方法,看看根据您的数据是否更快。

如果两者都不够快,请考虑编写自己的线性时间排序。例如,基数排序可以推广到(非负)浮点数上。如果您真的关心这里的性能,您可能必须将其编写为 C 或 Cython 扩展。

于 2012-07-01T01:58:19.920 回答
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]])
于 2012-07-01T02:30:15.670 回答