更快的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優化調度技巧不夠好，理解和適應形式，它有或迭代代碼拿出我自己的優化。

任何幫助將不勝感激。

編輯：

L來源於熊貓數據幀，所以它可以也被看作是一個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但是矢量化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 

不確定如果這是以另一種方式進行矢量化的話，或者如果其中一個優化嚮導可以使此方法更快。

編輯：想出了另一種方式，但仍不能快於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