Python 2.6 оптимизирует вложенные циклы

Question

У меня есть функция, которая имеет словарь как входной сигнал и значение n. Каждый элемент словаря представляет собой набор с одним или несколькими значениями. Функция должна сортировать словарные ключи, и она должна извлекать и возвращать значения «n». Эта функция будет выполняться очень часто, поэтому я пытаюсь ее оптимизировать. Какие-либо предложения?

def select_items(temp_dict, n): 
    """Select n items from the dictionary""" 
    res = [] 
    sort_keys = sorted(temp_dict.keys()) 
    count = 0 

    for key in sort_keys: 
    for pair in temp_dict[key]: 
     if count < n: 
     res.append(pair) 
     count += 1 
     else: 
     return res 

    return res 

В этом коде у меня есть счетчик и оператор «if» для управления количеством выбранных значений. Есть ли способ оптимизировать этот код, используя некоторую функцию в itertools или что-то еще?

Answer 1

ответы, которые до сих пор не обсуждаются вне зависимости от спецификации пользователя.

Данные представляют собой словарь последовательностей, а желаемым результатом является список первых n элементов значений словаря, взятых в отсортированном порядке по ключу.

Таким образом, если данные:

{1: [1, 2, 3], 2: [4, 5, 6]} 

затем, если п = 5, то результат должен быть:

[1, 2, 3, 4, 5] 

Учитывая, что, вот скрипт, который сравнивает исходную функцию с (немного) оптимизирована новая версия:

from timeit import timeit 

def select_items_old(temp_dict, n): 
    res = [] 
    sort_keys = sorted(temp_dict.keys()) 
    count = 0 
    for key in sort_keys: 
    for pair in temp_dict[key]: 
     if count < n: 
     res.append(pair) 
     count += 1 
     else: 
     return res 
    return res 

def select_items_new(data, limit): 
    count = 0 
    result = [] 
    extend = result.extend 
    for key in sorted(data.keys()): 
     value = data[key] 
     extend(value) 
     count += len(value) 
     if count >= limit: 
      break 
    return result[:limit] 

data = {x:range(10) for x in range(1000)} 

def compare(*args): 
    number = 1000 
    for func in args: 
     name = func.__name__ 
     print ('test: %s(data, 12): %r' % (name, func(data, 12))) 
     code = '%s(data, %d)' % (name, 300) 
     duration = timeit(
      code, 'from __main__ import %s, data' % name, number=number) 
     print ('time: %s: %.2f usec/pass\n' % (code, 1000000 * duration/number)) 

compare(select_items_old, select_items_new) 

Выход:

test: select_items_old(data, 12): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1] 
time: select_items_old(data, 300): 163.81 usec/pass 

test: select_items_new(data, 12): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1] 
time: select_items_new(data, 300): 67.74 usec/pass 

Answer 2

Использование анализа списка и возврат генератора - это более чистая/более читаемая альтернатива, на мой взгляд. Использование среза массива позволяет избежать предложения if.

def select_items(dic, n): 
    return (dic[key] for key in sorted(dic.keys())[:n]) 

На скорости: Я думаю, что фактический sort вызов, вероятно, самое узкое здесь, хотя вы, вероятно, не должны беспокоиться об этом, пока не ударил большой размер для словаря. В этом случае вам, вероятно, следует задуматься о том, чтобы хранить словарь в первую очередь - вы платите цену за сложность при вставке, но поиск/выбор выполняется быстро. Пример: sorteddict. Другой альтернативой может быть древовидная структура данных.

В соответствии с бенчмарками. Первоначальная настройка, снят с хороший ответ Дэвида Wolever в:

test_dict = dict((x, "a") for x in range(1000)) 
test_n = 300 

Ваша версия:

%timeit select_items(test_dict, test_n) 
1000 loops, best of 3: 334 us per loop 

Эта версия:

%timeit select_items(test_dict, test_n) 
10000 loops, best of 3: 49.1 us per loop 

Answer 3

Вот моя первая попытка (см select_items_faster), что почти в два раза скорость:

In [12]: print _11 
import itertools 

def select_items_original(temp_dict, n): 
    """Select n items from the dictionary""" 
    res = [] 
    sort_keys = sorted(temp_dict.keys()) 
    count = 0 

    for key in sort_keys: 
    for pair in temp_dict[key]: 
     if count < n: 
     res.append(pair) 
     count += 1 
     else: 
     return res 

    return res 

def select_items_faster(temp_dict, n): 
    """Select n items from the dictionary""" 
    items = temp_dict.items() 
    items.sort() 

    return list(itertools.chain.from_iterable(val for (_, val) in itertools.islice(items, n))) 

test_dict = dict((x, ["a"] * int(x/500)) for x in range(1000)) 
test_n = 300 


In [13]: %timeit select_items_original(test_dict, test_n) 
1000 loops, best of 3: 293 us per loop 


In [14]: %timeit select_items_faster(test_dict, test_n) 
1000 loops, best of 3: 203 us per loop 

Замена itertools.islice с [:n] не помогает вещи:

def select_items_faster_slice(temp_dict, n): 
    """Select n items from the dictionary""" 
    items = temp_dict.items() 
    items.sort() 

    return list(itertools.chain.from_iterable(val for (_, val) in items[:n])) 

In [16]: %timeit select_items_faster_slice(test_dict, test_n) 
1000 loops, best of 3: 210 us per loop 

И ни делает sorted:

In [18]: %timeit select_items_faster_sorted(test_dict, test_n) 
1000 loops, best of 3: 213 us per loop 


In [19]: print _17 
def select_items_faster_sorted(temp_dict, n): 
    """Select n items from the dictionary""" 
    return list(itertools.chain.from_iterable(val for (_, val) in itertools.islice(sorted(temp_dict.items()), n))) 

Но сочетание map и __getitem__ гораздо быстрее:

In [22]: %timeit select_items_faster_map_getitem(test_dict, test_n) 
10000 loops, best of 3: 90.7 us per loop 

In [23]: print _20 
def select_items_faster_map_getitem(temp_dict, n): 
    """Select n items from the dictionary""" 
    keys = temp_dict.keys() 
    keys.sort() 
    return list(itertools.chain.from_iterable(map(temp_dict.__getitem__, keys[:n]))) 

Замена list(itertools.chain.from_iterable) некоторыми волшебными скоростями с до совсем немного:

In [28]: %timeit select_items_faster_map_getitem_list_extend(test_dict, test_n) 
10000 loops, best of 3: 74.9 us per loop 

In 29: print _27 
def select_items_faster_map_getitem_list_extend(temp_dict, n): 
    """Select n items from the dictionary""" 
    keys = temp_dict.keys() 
    keys.sort() 
    result = [] 
    filter(result.extend, map(temp_dict.__getitem__, keys[:n])) 
    return result 

и замена карты и кусочек с itertools функций выдавить чуть-чуть больше скорости:

In [31]: %timeit select_items_faster_map_getitem_list_extend_iterables(test_dict, test_n) 
10000 loops, best of 3: 72.8 us per loop 

In [32]: print _30 
def select_items_faster_map_getitem_list_extend_iterables(temp_dict, n): 
    """Select n items from the dictionary""" 
    keys = temp_dict.keys() 
    keys.sort() 
    result = [] 
    filter(result.extend, itertools.imap(temp_dict.__getitem__, itertools.islice(keys, n))) 
    return result 

И это примерно так же быстро, как я думаю, что он может получить, потому что в CPython функции Python работают довольно медленно, и это минимизирует количество вызовов функций Python, которые выполняются во внутреннем цикле.

Примечание:

• Поскольку ОП не предусматривает каких-либо намека на то, что выглядят входные данные, как, так что я должен был догадаться. Я мог бы уйти, и это может кардинально изменить значение «быстро».
• Каждая из моих реализаций возвращает n - 1 элементов, а не n.

Edit: Используя тот же метод к профилю 'Код s:

In [2]: %timeit select_items_heapq(test_dict, test_n) 
1000 loops, best of 3: 572 us per loop 

In [3]: print _1 
from itertools import * 
import heapq 

def select_items_heapq(temp_dict, n): 
    return list(islice(chain.from_iterable(imap(temp_dict.get, heapq.nsmallest(n, temp_dict))),n)) 

И TokenMacGuy' JF Sebastian Код s:

In [5]: %timeit select_items_tokenmacguy_first(test_dict, test_n) 
1000 loops, best of 3: 201 us per loop 

In [6]: %timeit select_items_tokenmacguy_second(test_dict, test_n) 
1000 loops, best of 3: 730 us per loop 

In [7]: print _4 
def select_items_tokenmacguy_first(m, n): 
    k, v, r = m.keys(), m.values(), range(len(m)) 
    r.sort(key=k.__getitem__) 
    return [v[i] for i in r[:n]] 

import heapq 
def select_items_tokenmacguy_second(m, n): 
    k, v, r = m.keys(), m.values(), range(len(m)) 
    smallest = heapq.nsmallest(n, r, k.__getitem__) 
    for i, ind in enumerate(smallest): 
     smallest[i] = v[ind] 
    return smallest 

Answer 4

from itertools import * 
import heapq 
islice(chain.from_iterable(imap(temp_dict.get, heapq.nsmallest(n, temp_dict))),n)