Получение меньших n элементов списка в Python

Мне нужно получить меньше n номеров списка в Python. Мне нужно, чтобы это было очень быстро, потому что это очень важно для производительности, и его нужно повторять много раз.

n обычно не превышает 10, и список обычно имеет около 20000 элементов. При каждом вызове функции список всегда меняется. Сортировка не может быть выполнена.

Первоначально я написал эту функцию:

def mins(items, n): mins = [float('inf')]*n for item in items: for i, min in enumerate(mins): if item < min: mins.insert(i, item) mins.pop() break return mins 

Но эта функция не может побить простые отсортированные (элементы) [: n], которые сортируют весь список. Вот мой тест:

 from random import randint, random import time test_data = [randint(10, 50) + random() for i in range(20000)] init = time.time() mins = mins(test_data, 8) print 'mins(items, n):', time.time() - init init = time.time() mins = sorted(test_data)[:8] print 'sorted(items)[:n]:', time.time() - init 

Результаты:

 mins(items, n): 0.0632939338684 sorted(items)[:n]: 0.0231449604034 

sorted () [: n] в три раза быстрее. Я считаю, что это происходит потому, что:

  1. Вставка () является дорогостоящей, потому что списки Python не связаны списками.
  2. sorted () – оптимизированная функция c, а my – чистый python.

Есть ли способ побить отсортированный () [: n]? Должен ли я использовать расширение C, или Pyrex или Psyco, или что-то в этом роде?

Заранее благодарю за ваши ответы.

6 Solutions collect form web for “Получение меньших n элементов списка в Python”

Вы действительно хотите отсортированную последовательность минут.

 mins = items[:n] mins.sort() for i in items[n:]: if i < mins[-1]: mins.append(i) mins.sort() mins= mins[:n] 

Это выполняется намного быстрее, потому что вы даже не смотрите на минуты, если у него явно не больше значения, чем данный элемент. Примерно 1/10 времени оригинального алгоритма.

Это закончилось нулевым временем на моей Dell. Я должен был запустить его 10 раз, чтобы получить измеримое время работы.

 mins(items, n): 0.297000169754 sorted(items)[:n]: 0.109999895096 mins2(items)[:n]: 0.0309998989105 

Использование bisect.insort вместо добавления и сортировки может ускорить это.

 import heapq nlesser_items = heapq.nsmallest(n, items) 

Вот правильная версия алгоритма С. Лотта :

 from bisect import insort from itertools import islice def nsmallest_slott_bisect(n, iterable, insort=insort): it = iter(iterable) mins = sorted(islice(it, n)) for el in it: if el <= mins[-1]: #NOTE: equal sign is to preserve duplicates insort(mins, el) mins.pop() return mins 

Представление:

 $ python -mtimeit -s "import marshal; from nsmallest import nsmallest$label as nsmallest; items = marshal.load(open('items.marshal','rb')); n = 10"\ "nsmallest(n, items)" 
 nsmallest_heapq
 100 циклов, лучше всего 3: 12,9 мс за цикл
 nsmallest_slott_list
 100 циклов, лучше всего 3: 4,37 мсек за цикл
 nsmallest_slott_bisect
 100 циклов, лучше всего 3: 3,95 мс за цикл

nsmallest_slott_bisect в 3 раза быстрее, чем nsmallest (для n = 10, len (items) = 20000). nsmallest_slott_list лишь незначительно медленнее. Непонятно, почему napallest от heapq настолько медленный; его алгоритм почти идентичен приведенному выше (при малом n).

Мне нравится идея кучи Эриксона. Я тоже не знаю Python, но здесь есть консервированное решение: heapq – алгоритм очереди с кучей

Возможность использования модуля bisect :

 import bisect def mins(items, n): mins = [float('inf')]*n for item in items: bisect.insort(mins, item) mins.pop() return mins 

Однако для меня это немного быстрее:

 mins(items, n): 0.0892250537872 sorted(items)[:n]: 0.0990262031555 

Использование psyco ускоряет его:

 import bisect import psyco psyco.full() def mins(items, n): mins = [float('inf')]*n for item in items: bisect.insort(mins, item) mins.pop() return mins 

Результат:

 mins(items, n): 0.0431621074677 sorted(items)[:n]: 0.0859830379486 

Если скорость вызывает наибольшую озабоченность, самый быстрый способ будет состоять из c. Psyco имеет первоначальную стоимость, но может оказаться довольно быстрой. Я бы рекомендовал Cython для python -> c компиляции (более актуальной для pp Pyrex).

Ручное кодирование в c будет лучшим и позволит вам использовать структуры данных, специфичные для вашего проблемного домена.

Но обратите внимание:

«Компиляция неправильного алгоритма в C не может быть быстрее, чем правильный алгоритм в Python» @ S.Lott

Я хотел добавить комментарий С.Лотта, чтобы его заметили. Python – отличный язык прототипов, где вы можете сгладить алгоритм, который вы намереваетесь позже перевести на язык более низкого уровня.

почему бы просто не вызвать элемент select_n_th в O (N) времени, а затем разделить массив на две части на элемент n_th, это должно быть самым быстрым.

ps: Этот алгоритм O (N) работает, если вы не укажете порядок n-самых маленьких элементов. Нижеприведенная ссылка делает алгоритм выбора. http://code.activestate.com/recipes/269554-select-the-nth-smallest-element/

Предполагая, что массив не имеет повторяющихся элементов, код работает для меня. Эффективность по-прежнему зависит от масштаба задачи, если n <10, вероятно, достаточно алгоритма O (logn * N).

 import random import numpy as np def select(data, n): "Find the nth rank ordered element (the least value has rank 0)." data = list(data) if not 0 <= n < len(data): raise ValueError('not enough elements for the given rank') while True: pivot = random.choice(data) pcount = 0 under, over = [], [] uappend, oappend = under.append, over.append for elem in data: if elem < pivot: uappend(elem) elif elem > pivot: oappend(elem) else: pcount += 1 if n < len(under): data = under elif n < len(under) + pcount: return pivot else: data = over n -= len(under) + pcount def n_lesser(data,n): data_nth = select(data,n) ind = np.where(data<data_nth) return data[ind] 
  • Сортировка строк по второму слову в каждой строке текстового файла, а затем отображение его
  • Сортировка списков на основе определенного элемента - Python
  • Как отсортировать список, только сортировка строк?
  • Сортировка строк массива другим массивом в python
  • Сортировка Python в отсортированном списке
  • Сортировка Python по максимуму первого элемента, затем min второго элемента
  • Как я могу отсортировать список координат для прямоугольника против часовой стрелки?
  • Сортировка ключей одинаковых значений в алфавитном порядке
  • python, сортировка списка с помощью ключа, который является подстрокой каждого элемента
  • Естественно отсортируйте список альфа-числовых кортежей с помощью первого элемента кортежа в Python
  • Как эффективно обрабатывать временные ряды данных в пандах
  • Python - лучший язык программирования в мире.