dilts के सामान्य निर्देश की तुलना में lil_matrix और dok_matrix इतनी धीमी क्यों हैं?

Question

मैं iteratively विरल मैट्रिक्स का निर्माण करना चाहते, और पाया है कि इस SciPy प्रलेखन के अनुसार के लिए दो उपयुक्त विकल्प हैं कि:

LiL matrix:

वर्ग scipy.sparse.lil_matrix (ARG1, आकार = कोई नहीं , dtype = कोई नहीं, प्रतिलिपि = झूठी) [स्रोत] पंक्ति आधारित लिंक्ड सूची विरल मैट्रिक्स

यह विरल मैट्रिक्स संवर्द्धित के निर्माण के लिए एक कुशल संरचना है।

DoK matrix:

वर्ग scipy.sparse.dok_matrix (ARG1, आकार = कोई नहीं, dtype = कोई नहीं, प्रतिलिपि = झूठी) [स्रोत] चाबियों का शब्दकोश आधारित विरल मैट्रिक्स।

यह स्पैर मैट्रिस वृद्धिशील बनाने के लिए एक कुशल संरचना है।

लेकिन जब मैं मान (जो बाद में आसानी से विरल मैट्रिक्स के लिए परिवर्तित किया जा सकता है) के शब्दकोश का एक शब्दकोश के निर्माण के लिए की तुलना बेंचमार्क चल रहा हूँ, बाद पता चला है के किसी भी उपयोग करने की तुलना के बारे में 10-20 गुना तेजी से होने के लिए विरल मैट्रिक्स मॉडल:

from scipy.sparse import dok_matrix, lil_matrix 
from timeit import timeit 
from collections import defaultdict 

def common_dict(rows, cols): 
    freqs = defaultdict(lambda: defaultdict(int)) 
    for row, col in zip(rows, cols): 
     freqs[row][col] += 1 

    return freqs 

def dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 

def lil(rows, cols): 
    freqs = lil_matrix((1000,1000)) 
    for row, col in zip(rows, cols): 
     freqs[row,col] += 1 

    return freqs 


def benchmark(): 
    cols = range(1000) 
    rows = range(1000) 

    res = timeit("common_dict({},{})".format(rows, cols), 
       "from __main__ import common_dict", 
       number=100) 

    print("common_dict: {}".format(res)) 

    res = timeit("dok({},{})".format(rows, cols), 
       "from __main__ import dok", 
       number=100) 

    print("dok: {}".format(res)) 

    res = timeit("lil({},{})".format(rows, cols), 
       "from __main__ import lil", 
       number=100) 

    print("lil: {}".format(res)) 

परिणाम:

benchmark() 

common_dict: 0.11778324202168733 
dok: 2.2927695910912007 
lil: 1.3541790939634666 

यह क्या है कि मैट्रिक्स मॉडल के लिए इस तरह के एक भूमि के ऊपर का कारण बनता है, और वहाँ यह गति अप करने के लिए किसी तरह है? क्या ऐसे मामलों का उपयोग किया जाता है जहां डॉक या लिल को डिक्ट्स के एक सामान्य निर्देश पर प्राथमिकता दी जाती है?

Answer 1

जब मैं बदलने अपने += करने के लिए सिर्फ = अपने 2 विरल सरणियों के लिए:

for row, col in zip(rows, cols): 
    #freqs[row,col] += 1 
    freqs[row,col] = 1 

उनके संबंधित बार आधे में कटौती कर रहे हैं। सबसे अधिक समय लेने वाला क्या अनुक्रमण है। += के साथ इसे __getitem__ और __setitem__ दोनों करना है।

जब दस्तावेज़ कहते हैं कि dok और lil पुनरावर्तक निर्माण के लिए बेहतर हैं तो उनका मतलब है कि अन्य प्रारूपों की तुलना में उनके अंतर्निहित डेटा संरचनाओं का विस्तार करना आसान है।

जब मैं अपने कोड के साथ एक csr मैट्रिक्स बनाने की कोशिश, मैं एक मिल:

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690: SparseEfficiencyWarning : Csr_matrix की स्पर्सिटी संरचना को बदलना महंगा है। lil_matrix अधिक कुशल है। स्पैसएफ़िशियंसवार्निंग)

और 30x धीमी गति।

तो गति दावे csr जैसे प्रारूपों के सापेक्ष हैं, शुद्ध पायथन या numpy संरचनाओं के सापेक्ष नहीं।

आप dok_matrix.__get_item__ और dok_matrix.__set_item__ के लिए पाइथन कोड को देखना चाहते हैं ताकि यह देखने के लिए कि freq[r,c] क्या होता है।

---

के निर्माण के लिए अपने dok होगा एक तेज़ तरीका:

freqs = dok_matrix((1000,1000)) 
d = dict() 
for row, col in zip(rows, cols): 
    d[(row, col)] = 1 
freqs.update(d) 

तथ्य यह है कि एक dok एक subclassed शब्दकोश है का लाभ लेने के। ध्यान दें कि dok मैट्रिक्स शब्दकोशों का एक शब्दकोश नहीं है। इसकी चाबियाँ (50,50) जैसी tuples हैं।

ही विरल सरणी के निर्माण का एक और तेज़ तरीका है:

freqs = sparse.coo_matrix((np.ones(1000,int),(rows,cols))) 

दूसरे शब्दों में, के बाद से आप पहले से ही, rows और cols सरणियों (या श्रेणियों) है इसी data सरणी की गणना, और फिर निर्माण स्पैस सरणी

लेकिन अगर आपको वृद्धिशील विकास चरणों के बीच अपने मैट्रिक्स पर स्पैस ऑपरेशंस करना होगा, तो dok या lil आपके सर्वोत्तम विकल्प हो सकते हैं।

---

विरल matricies इतनी बड़ी विरल मैट्रिक्स के साथ एक रेखीय समीकरण को सुलझाने के रूप में रेखीय बीजगणित समस्याओं, के लिए विकसित किए गए। मैंने उन्हें सीमित अंतर समस्याओं को हल करने के लिए कई वर्षों पहले MATLAB में उपयोग किया था। उस काम के लिए गणना अनुकूल csr प्रारूप अंतिम लक्ष्य है, और coo प्रारूप एक सुविधाजनक प्रारंभिक प्रारूप था।

अब scikit-learn और टेक्स्ट विश्लेषण समस्याओं से उत्पन्न होने वाले बहुत से एसपीआईसी प्रश्न उत्पन्न हुए हैं। इन्हें जैविक डेटाबेस फ़ाइलों में भी उपयोग किया जाता है। लेकिन अभी भी (data),(row,col) परिभाषा विधि सर्वोत्तम काम करती है।

तो स्पैस मैट्रिस का तेजी से वृद्धिशील सृजन के लिए कभी इरादा नहीं था। शब्दकोश और सूचियों जैसे पारंपरिक पायथन संरचनाएं इसके लिए बहुत बेहतर हैं।

---

यहाँ एक तेजी से dok यात्रा है कि अपने शब्दकोश तरीकों का लाभ लेता है। update एक सादा शब्दकोश के रूप में तेजी से काम करता प्रतीत होता है। get समकक्ष अनुक्रमण (freq[row,col]) के बारे में 3x तेज है। इंडेक्सिंग शायद get का उपयोग करती है, लेकिन इसमें बहुत अधिक ओवरहेड होना चाहिए।

def fast_dok(rows, cols): 
    freqs = dok_matrix((1000,1000)) 
    for row, col in zip(rows,cols): 
     i = freqs.get((row,col),0) 
     freqs.update({(row,col):i+1}) 
    return freqs 

get छोड़ा जा रहा है, और सिर्फ

  freqs.update({(row,col): 1) 

कर भी तेजी से है - तेजी से defaultdict उदाहरण के defaultdict से, और लगभग के रूप में तेजी से के रूप में सरल शब्दकोश प्रारंभ ({(r, c):1 for r,c in zip(rows, cols)})

Answer 2

रहे हैं विभिन्न कारणों से आपका परीक्षण उचित नहीं है। सबसे पहले, आप अपने टाइम लूप के हिस्से के रूप में स्पैर मैट्रिस बनाने के ऊपरी हिस्से को शामिल कर रहे हैं।

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