Python: How to find all the items greater than some number in an unsorted list (large data set)

Question

Although, similar type of questions have been asked by others, for ex. here, but they differed slightly and didn't really get solve my problem, so here I go again.

I have N lists (N>20,000) and each list contains M lists ( M >20,000), in the following manner ( data is dummy):

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

Data is unsorted. Iterating over a list of threshold values one by one, say Threshold =[2, 3, 5, 7, 8], where threshold is applied over middle element, I want to extract all the elements, for all the keys, greater than the threshold value. For ex. going by the data I wrote above, Threshold = 2 would yield

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

And similarly for other threshold values too. Since, there are too many lists, my observation is that sorting is contribute to lot of overhead and hence I want to avoid it. What is the optimum method of doing this in python ?. One additional important point is that, I am constructing the data myself, so possibly there is a better data structure to store the data to begin with. I am currently storing the data in the form of PersistentList within a Btree container in ZODB, which was suggested here . Following is a snippet of the code used for it:

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

Any suggestions on what should be the most efficient way of doing it? Is sorting first indeed the optimum way ?

Answer 1

Use a generator comprehension:

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

A generator only computes elements on demand, and since it goes through the elements of the list in order, there's no need to sort. (That is, it runs in linear time on the length of each Keyn, rather than M*log(M) for sorting.)

Equivalently, in functional style (only equivalent in Python 3; for Python 2, use itertools.ifilter):

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

If your Keyn lists are stored in a list (or other subscriptable object), you can process them all at once (some alternative styles shown):

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

or

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

Performance of this method relative to sorting

Whether this method is faster than sorting depends on M and the number of thresholds T you have. The running time (for each Key list) is O(M * T). If you sort the list (O(M * log(M))), then you can use binary search for each threshold, giving an overall running time of O(M * log(M) + T * log(M)) = O(max(M, T) * log(M)). Sorting is faster when T is sufficiently large relative to M. We can't know the constants a priori, so test both ways to see whether one is faster given your data.

If neither is fast enough, consider writing your own linear-time sort. For example, radix sort can be generalized to work on (non-negative) floats. If you're really concerned about performance here, you might have to write this as a C or Cython extension.

Answer 2

In numpy you can do this easily with an NxMx3 array:

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

This returns:

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

If you need the locations of the elements that crossed threshold, use argwhere().

Edit:

It's also possible to do multiple threshold comparisons simultaneously:

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