Быстрое numpy-решение вместо itertools.combinations?

Question

Я использую itertools.combinations() следующим образом:

import itertools 
import numpy as np 

L = [1,2,3,4,5] 
N = 3 

output = np.array([a for a in itertools.combinations(L,N)]).T 

что дает мне выход мне нужно:

array([[1, 1, 1, 1, 1, 1, 2, 2, 2, 3], 
     [2, 2, 2, 3, 3, 4, 3, 3, 4, 4], 
     [3, 4, 5, 4, 5, 5, 4, 5, 5, 5]]) 

Я использую это выражение неоднократно и чрезмерно в среде многопроцессорной и мне нужно, чтобы быть как можно быстрее.

От this post Я понимаю, что itertools основанного кода не является самым быстрым решением и использование numpy может быть улучшением, однако я не достаточно хорошо numpy optimazation уловок, чтобы понять и адаптировать повторяющийся код, который там написан или придумайте мою собственную оптимизацию.

Любая помощь была бы принята с благодарностью.

EDIT:

L происходит от панд dataframe, так что он может так же рассматриваться как Numpy массива:

L = df.L.values 

Answer 1

Вот тот, который немного быстрее, чем itertools UPDATE: и один (nump2), что на самом деле совсем немного быстрее:

import numpy as np 
import itertools 
import timeit 

def nump(n, k, i=0): 
    if k == 1: 
     a = np.arange(i, i+n) 
     return tuple([a[None, j:] for j in range(n)]) 
    template = nump(n-1, k-1, i+1) 
    full = np.r_[np.repeat(np.arange(i, i+n-k+1), 
          [t.shape[1] for t in template])[None, :], 
       np.c_[template]] 
    return tuple([full[:, j:] for j in np.r_[0, np.add.accumulate(
     [t.shape[1] for t in template[:-1]])]]) 

def nump2(n, k): 
    a = np.ones((k, n-k+1), dtype=int) 
    a[0] = np.arange(n-k+1) 
    for j in range(1, k): 
     reps = (n-k+j) - a[j-1] 
     a = np.repeat(a, reps, axis=1) 
     ind = np.add.accumulate(reps) 
     a[j, ind[:-1]] = 1-reps[1:] 
     a[j, 0] = j 
     a[j] = np.add.accumulate(a[j]) 
    return a 

def itto(L, N): 
    return np.array([a for a in itertools.combinations(L,N)]).T 

k = 6 
n = 12 
N = np.arange(n) 

assert np.all(nump2(n,k) == itto(N,k)) 

print('numpy ', timeit.timeit('f(a,b)', number=100, globals={'f':nump, 'a':n, 'b':k})) 
print('numpy 2 ', timeit.timeit('f(a,b)', number=100, globals={'f':nump2, 'a':n, 'b':k})) 
print('itertools', timeit.timeit('f(a,b)', number=100, globals={'f':itto, 'a':N, 'b':k})) 

Тайминги:

k = 3, n = 50 
numpy  0.06967267207801342 
numpy 2 0.035096961073577404 
itertools 0.7981023890897632 

k = 3, n = 10 
numpy  0.015058324905112386 
numpy 2 0.0017436158377677202 
itertools 0.004743851954117417 

k = 6, n = 12 
numpy  0.03546895203180611 
numpy 2 0.00997065706178546 
itertools 0.05292179994285107 

Answer 2

Это, безусловно, не быстрее, чем itertools.combinations но is vectorized numpy:

def nd_triu_indices(T,N): 
    o=np.array(np.meshgrid(*(np.arange(len(T)),)*N)) 
    return np.array(T)[o[...,np.all(o[1:]>o[:-1],axis=0)]] 

%timeit np.array(list(itertools.combinations(T,N))).T 
The slowest run took 4.40 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 8.6 µs per loop 

%timeit nd_triu_indices(T,N) 
The slowest run took 4.64 times longer than the fastest. This could mean that an intermediate result is being cached. 
10000 loops, best of 3: 52.4 µs per loop 

Не уверен если это векторизуется другим способом или если один из мастеров оптимизации здесь может сделать этот метод быстрее.

EDIT: Придумал другим способом, но до сих пор не быстрее, чем combinations:

%timeit np.array(T)[np.array(np.where(np.fromfunction(lambda *i: np.all(np.array(i)[1:]>np.array(i)[:-1], axis=0),(len(T),)*N,dtype=int)))] 
The slowest run took 7.78 times longer than the fastest. This could mean that an intermediate result is being cached. 
10000 loops, best of 3: 34.3 µs per loop