Python: как найти все элементы больше некоторого числа в несортированном списке (большой набор данных)

Хотя подобные вопросы задавали и другие, например. Заголовок здесь, но они немного отличались и на самом деле не решили мою проблему, так что вот еще раз.

У меня есть 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 в контейнере Btree в ZODB, что было предложено здесь . Ниже приведен фрагмент кода, используемого для этого:

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

Любые предложения о том, что должно быть наиболее эффективным способом сделать это? Является ли сортировка первой действительно оптимальным способом?


python search sorting zodb
person R.Bahl    schedule 01.07.2012    source источник
comment
Каков источник данных? Файл? Являются ли они однородными целыми числами или целыми числами и числами с плавающей запятой?   -  person the wolf    schedule 01.07.2012
comment
Как указано в исходном сообщении, я генерирую данные, используя вышеупомянутый код. Как только список для одного ключа готов, он временно записывается на диск методом savepoint(). Элементы во внутреннем меньшем списке имеют следующий формат: [int, float, zero or 1]. Диапазон переменной int составляет от 0 до M, и все целые числа между ними уже отображаются в порядке возрастания, то есть от 0 до M из-за способа записи данных.   -  person R.Bahl    schedule 01.07.2012

Ответы (2)


arrow_upward
4
arrow_downward

Используйте понимание генератора:

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

or

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.

person Mechanical snail    schedule 01.07.2012
comment
Я думал об этом, но разве это не должно быть менее эффективно, чем первая сортировка? Я не уверен, хотя, и если вы можете прокомментировать, это будет здорово! - person R.Bahl; 01.07.2012
comment
Кроме того, обратите внимание, что мне нужно сделать это для многих разных пороговых значений, поэтому использование этого метода будет означать, что мне придется многократно проходить весь список для каждого порогового значения. Не должно ли это влиять на производительность? - person R.Bahl; 01.07.2012
comment
Как filter() python 3 только? Вы имеете в виду тот факт, что filter() возвращает генератор в python 3? Если это так, я бы также включил версию 2.x: itertools.ifilter. - person Joel Cornett; 01.07.2012
comment
Спасибо за советы по производительности. Чтобы дать оценку порядка, скажем, у меня есть 10 000 ключей, каждый из которых имеет 10 000 меньших списков, тогда количество необходимых мне пороговых значений будет около 400 в порядке возрастания, скажем, T=[ .1 .2 .3 ...... ] - person R.Bahl; 01.07.2012
comment
@R.Bahl: Это всего 40 миллионов записей, что должно быть достаточно быстро в любом случае. - person Mechanical snail; 01.07.2012
comment
@JoelCornett: это то, что я имел в виду. Спасибо. - person Mechanical snail; 01.07.2012
comment
Проблема в том, что это будет расти довольно быстро, поэтому я беспокоюсь о производительности. - person R.Bahl; 01.07.2012

arrow_upward
2
arrow_downward

В 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]])
person Luke    schedule 01.07.2012
comment
Интересный. Я не думал об этом. У вас есть оценка производительности этого по сравнению с сортировкой или решением, упомянутым механической улиткой? - person R.Bahl; 01.07.2012
comment
Я думаю, что NumPy требует, чтобы все элементы array были одного типа. Это не делает этот метод недействительным (поскольку floats может точно представлять все маленькие целые числа), но не забывайте приводить результаты обратно к int, когда это необходимо. - person Mechanical snail; 01.07.2012
comment
Или просто используйте dtype=numpy.int64 при построении массива. - person Chinmay Kanchi; 01.07.2012
comment
Я не знаю, как будет производительность, так как я не уверен, как numpy реализует это в фоновом режиме. Тем не менее, мне было бы интересно увидеть некоторые тесты. Сортировка, безусловно, может помочь, но, как уже упоминалось, это зависит от деталей ваших данных и пороговых значений. - person Luke; 01.07.2012
comment
Учитывая, что Numpy, как правило, очень быстр в массиве, это определенно будет интересно. Позвольте мне пойти дальше и поэкспериментировать с ним. Дам знать, как пойдет. Спасибо за все предложения! - person R.Bahl; 01.07.2012