Ускорение сочетаний itertools с Cython - PullRequest
Новая
       8

Ускорение сочетаний itertools с Cython

0 голосов
/ 06 мая 2018

У меня есть следующий код для генерации всех возможных комбинаций в указанном диапазоне с помощью itertools, но я не могу добиться каких-либо улучшений скорости при использовании кода с cython. Оригинальный код: 

from itertools import *

def x(e,f,g):
    a=[]        
    for c in combinations(range(e, f),g):
        d = list((c))
        a.append(d)

и после объявления типов для Cython: 

from itertools import *

cpdef x(int e,int f,int g):        
    cpdef tuple c
    cpdef list a
    cpdef list d

    a=[]        
    for c in combinations(range(e, f),g):    
        d = list((c))
        a.append(d)

Я сохранил последний как test_cy.pyx и скомпилировал, используя cythonize -a -i test_cy.pyx

После компиляции я создал новый скрипт со следующим кодом и запустил его: 

import test_cy

test_cy.x(1,45,6)

Я не получил какого-либо значительного улучшения скорости, но занял примерно столько же времени, сколько и в оригинальном сценарии, около 10,8 с.

Что-то я не так сделал или itertools уже настолько оптимизирован, что его скорость не может быть улучшена?

1 Ответ

0 голосов
/ 06 мая 2018

Как уже указывалось в комментариях, вы не должны ожидать, что cython ускорит ваш код, потому что большую часть времени алгоритм тратит на itertools и создание списков.

Поскольку мне любопытно посмотреть, как общая реализация реализации itertools против уловок старой школы, давайте посмотрим на реализацию Cython "все подмножества k из n": 

%%cython

ctypedef unsigned long long ull

cdef ull next_subset(ull subset):
   cdef ull smallest, ripple, ones
   smallest = subset& -subset      
   ripple = subset + smallest    
   ones = subset ^ ripple    
   ones = (ones >> 2)//smallest 
   subset= ripple | ones    
   return subset


cdef subset2list(ull subset, int offset, int cnt):  
    cdef list lst=[0]*cnt #pre-allocate
    cdef int current=0;
    cdef int index=0
    while subset>0:
        if((subset&1)!=0):
            lst[index]=offset+current
            index+=1
        subset>>=1
        current+=1
    return lst

def all_k_subsets(int start, int end, int k):
    cdef int n=end-start      
    cdef ull MAX=1L<<n;
    cdef ull subset=(1L<<k)-1L;
    lst=[]
    while(MAX>subset):
         lst.append(subset2list(subset, start, k))
         subset=next_subset(subset)
    return lst

Эта реализация использует некоторые хорошо известные трюки и имеет ограничение, заключающееся в том, что она работает не более чем с 64 элементами.

Если мы сравним оба подхода: 

>>> %timeit x(1,45,6)
2.52 s ± 108 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit all_k_subsets(1,45,6)
1.29 s ± 5.16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ускорение фактора 2 весьма разочаровывает.

Однако узким местом является создание списков, а не сам расчет - легко проверить, что без создания списка расчет займет около 0,1 секунды.

Мой вывод: если вы серьезно относитесь к скорости, вам не следует создавать так много списков, а выполнять подмножество на лету (лучшее в Cython) - возможно ускорение более чем на 10. Если необходимо иметь все подмножества в виде списков, то вы не можете ожидать значительного ускорения.

...