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

Question

Мне нужно получить меньшее 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

Но эта функция не может разбить простую сортировку (items) [: 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. Операция insert () является дорогостоящей, поскольку списки Python не являются связанными списками.
2. sorted () - оптимизированная функция c, а моя - чистый python.

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

Заранее спасибо за ваши ответы.

Answer 1

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

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 вместо добавления и сортировки может еще больше ускорить это.

Answer 2

import heapq

nlesser_items = heapq.nsmallest(n, items)

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

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 loops, best of 3: 12.9 msec per loop
nsmallest_slott_list
100 loops, best of 3: 4.37 msec per loop
nsmallest_slott_bisect
100 loops, best of 3: 3.95 msec per loop

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

Можно использовать модуль 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

Answer 6

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

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

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

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]