Döngüyü en iyileştirme/çıkarma

Question

Aşağıdakileri kullanarak numpy kullanarak, tercihen döngüyü kaldırarak optimize etmek istediğim bir kod parçasına sahibim. Ona nasıl yaklaşacağımı göremiyorum, bu yüzden herhangi bir öneri yardımcı olabilir.

endeksleri, bir (N, 2) sayısal tamsayı dizisidir, N birkaç milyon olabilir. Kod, ilk sütunda tekrarlanan indisleri buluyor. Bu endeksler için, ikinci sütundaki karşılık gelen indekslerin iki kombinasyonunu yapıyorum. Sonra onları ilk sütundaki endeksle birlikte toplarım.

index_sets = [] 
uniques, counts = np.unique(indices[:,0], return_counts=True) 
potentials = uniques[counts > 1] 
for p in potentials: 
    correspondents = indices[(indices[:,0] == p),1] 
    combs = np.vstack(list(combinations(correspondents, 2))) 
    combs = np.hstack((np.tile(p, (combs.shape[0], 1)), combs)) 
    index_sets.append(combs) 

Answer 1

İşte N üzerinde vektörize edilen bir çözümdür. Bir döngü için hala bir tane içerdiğini unutmayın, ancak her bir 'anahtar çokluklar grubu' üzerinde bir döngüdür. en fazla birkaç düzine).

N = 1.000.000 için, çalışma zamanı pc'imde bir saniye büyüklüğündedir.

import numpy_indexed as npi 
N = 1000000 
indices = np.random.randint(0, N/10, size=(N, 2)) 

def combinations(x): 
    """vectorized computation of combinations for an array of sequences of equal length 

    Parameters 
    ---------- 
    x : ndarray, [..., n_items] 

    Returns 
    ------- 
    ndarray, [..., n_items * (n_items - 1)/2, 2] 
    """ 
    return np.rollaxis(x[..., np.triu_indices(x.shape[-1], 1)], -2, x.ndim+1) 

def process(indices): 
    """process a subgroup of indices, all having equal multiplicity 

    Parameters 
    ---------- 
    indices : ndarray, [n, 2] 

    Returns 
    ------- 
    ndarray, [m, 3] 
    """ 
    keys, vals = npi.group_by(indices[:, 0], indices[:, 1]) 
    combs = combinations(vals) 
    keys = np.repeat(keys, combs.shape[1]) 
    return np.concatenate([keys[:, None], combs.reshape(-1, 2)], axis=1) 

index_groups = npi.group_by(npi.multiplicity(indices[:, 0])).split(indices) 
result = np.concatenate([process(ind) for ind in index_groups]) 

Yasal Uyarı: Ben numpy_indexed paketin yazarıyım.

Answer 2

az gelişmeler önerilebilir:

• , bir dizi ile başlatma kendisi için her bir gruba tekabül eden depolama kombinasyonları için gerekli sıralar tahmini sayısı önceden hesaplayabilir. N elemanlarıyla, her grup için kombinasyon uzunluklarını bize vermek için olası kombinasyonların toplam sayısı N*(N-1)/2 olacaktır. Ayrıca, çıkış dizisindeki toplam satır sayısı, tüm bu aralık uzunluklarının toplamı olacaktır. Bir döngüye girmeden önce mümkün olduğunca çok sayıda nesneyi önceden vektörleştirilmiş şekilde önceden hesaplayın.

• Düzensiz desen nedeniyle vektörleştirilemeyen kombinasyonları almak için bir döngü kullanın. Döşemeyi simüle etmek için np.repeat kullanın ve her grup için ilk öğeyi ve dolayısıyla çıkış dizisinin ilk sütununu vermek için döngüden önce yapın.

bunların ışığında tüm bu iyileştirmeler ile, bir uygulama şu şekilde görünecektir -

# Remove rows with counts == 1 
_,idx, counts = np.unique(indices[:,0], return_index=True, return_counts=True) 
indices = np.delete(indices,idx[counts==1],axis=0) 

# Decide the starting indices of corresponding to start of new groups 
# charaterized by new elements along the sorted first column 
start_idx = np.unique(indices[:,0], return_index=True)[1] 
all_idx = np.append(start_idx,indices.shape[0]) 

# Get interval lengths that are required to store pairwise combinations 
# of each group for unique ID from column-0 
interval_lens = np.array([item*(item-1)/2 for item in np.diff(all_idx)]) 

# Setup output array and set the first column as a repeated array 
out = np.zeros((interval_lens.sum(),3),dtype=int) 
out[:,0] = np.repeat(indices[start_idx,0],interval_lens) 

# Decide the start-stop indices for storing into output array 
ssidx = np.append(0,np.cumsum(interval_lens)) 

# Finally run a loop gto store all the combinations into initialized o/p array 
for i in range(idx.size): 
    out[ssidx[i]:ssidx[i+1],1:] = \ 
    np.vstack(combinations(indices[all_idx[i]:all_idx[i+1],1],2)) 

diziler listesinden bölünmüş çıktı dizisi büyük (M, 3) şekilli dizi olacağını unutmayın ve lütfen Orijinal kod tarafından üretildiği gibi. Hala böyle gerekiyorsa, aynı için np.split kullanabilirsiniz. Ayrıca, hızlı çalışma zamanı testleri önerilen kodla pek fazla gelişme olmadığını göstermektedir. Yani, muhtemelen çalışma zamanının büyük bir kısmı kombinasyonları elde etmek için harcanıyor. Bu nedenle, bu tür bağlantıya yönelik sorunlara daha iyi uyum sağlayabilmesi için özel olarak uygun olan networkx ile alternatif bir yaklaşım gibi görünmektedir.