लूप को अनुकूलित/हटा रहा है

Question

मेरे पास कोड का निम्न भाग है जिसे मैं numpy का उपयोग करके अनुकूलित करना चाहता हूं, अधिमानतः लूप को हटा रहा हूं। मैं नहीं देख सकता कि इसे कैसे पहुंचाया जाए, इसलिए कोई सुझाव उपयोगी होगा।

सूचकांक पूर्णांक की एक (एन, 2) numpy सरणी है, एन कुछ लाख हो सकता है। कोड पहले कोड में दोहराए गए सूचकांक को ढूंढ रहा है। इन सूचकांकों के लिए मैं दूसरे कॉलम में दो संबंधित सूचकांक के सभी संयोजन बना देता हूं। फिर मैं उन्हें पहले कॉलम में इंडेक्स के साथ इकट्ठा करता हूं।

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

यहां एक समाधान है जो एन पर ध्यान केंद्रित किया गया है। ध्यान दें कि इसमें अभी भी एक लूप है, लेकिन यह प्रत्येक 'समूह-कुंजी-गुणों के समूह' पर एक लूप है, जो कि बहुत छोटी संख्या (आमतौर पर) सबसे अधिक कुछ दर्जन)।

एन = 1.000.000 के लिए, रनटाइम मेरे पीसी पर एक सेकंड का आयाम है।

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]) 

अस्वीकरण: मैं numpy_indexed पैकेज का लेखक हूं।

Answer 2

कुछ सुधार का सुझाव दिया जा सकता है:

• प्रारंभ उत्पादन सरणी, जिसके लिए हम प्रत्येक समूह के लिए इसी भंडारण संयोजन के लिए आवश्यक पंक्तियों की अनुमानित संख्या पहले से गणना कर सकते हैं। हम जानते हैं कि N तत्वों के साथ, प्रत्येक समूह के लिए संयोजन लंबाई हमें देने के लिए संभावित संयोजनों की कुल संख्या N*(N-1)/2 होगी। इसके अलावा, आउटपुट सरणी में पंक्तियों की कुल संख्या उन सभी अंतराल की लंबाई का योग होगा।

• एक लूप में जाने से पहले एक वेक्टरकृत तरीके से जितना संभव हो उतना सामान पूर्व-कैलकुएट करें।

• संयोजन प्राप्त करने के लिए एक लूप का उपयोग करें, जो कि रैग किए गए पैटर्न की वजह से वेक्टरकृत नहीं किया जा सकता है। टाइलिंग अनुकरण करने के लिए np.repeat का उपयोग करें और लूप से पहले इसे प्रत्येक समूह के लिए पहला तत्व दें और इस प्रकार आउटपुट सरणी का पहला कॉलम दें।

तो, मन में उन सभी सुधार के साथ, एक कार्यान्वयन इस प्रकार दिखाई देगा -

# 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)) 

कृपया ध्यान दें कि उत्पादन सरणी एक बड़ा (M, 3) आकार सरणी हो सकता है और नहीं सरणियों की सूची में विभाजित मूल कोड द्वारा उत्पादित के रूप में। यदि अभी भी इसकी आवश्यकता है, तो इसके लिए np.split का उपयोग कर सकते हैं।

इसके अलावा, त्वरित रनटाइम परीक्षणों से पता चलता है कि प्रस्तावित कोड में बहुत सुधार नहीं है। तो, शायद रनटाइम का बड़ा हिस्सा संयोजन प्राप्त करने में बिताया जाता है। इस प्रकार, यह networkx के साथ वैकल्पिक दृष्टिकोण लगता है जो विशेष रूप से इस तरह के कनेक्शन आधारित समस्याओं के लिए उपयुक्त है बेहतर फिट हो सकता है।