python - चलन - क्यों collections.counter बहुत धीमा है?




वोडाफोन नेट स्पीड (2)

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

अब यह पहले से ही कारण है कि str.count() कॉल करने से चार गुना किसी और चीज़ से तेज़ है यद्यपि यह स्ट्रिंग को चार बार पुनरावृति करता है, ये लूप मूल कोड में चलते हैं। str.count सी में कार्यान्वित किया गया है, इसलिए यह बहुत कम उपरि है, जिससे यह बहुत तेज हो। यह हरा करना वास्तव में मुश्किल है, विशेष रूप से जब कार्य सरल है (केवल साधारण चरित्र समानता के लिए)।

आपकी दूसरी विधि, एक सरणी में गिनती एकत्र करने का वास्तव में निम्नलिखित का एक कम प्रदर्शन संस्करण है:

def method4 (seq):
    a, c, g, t = 0, 0, 0, 0
    for i in seq:
        if i == 'A':
            a += 1
        elif i == 'C':
            c += 1
        elif i == 'G':
            g += 1
        else:
            t += 1
    return [a, c, g, t]

यहां, सभी चार मान अलग-अलग चर हैं, इसलिए उन्हें अपडेट करना बहुत तेज है सूची वस्तुओं को उत्परिवर्तित करने से यह वास्तव में थोड़ा तेज है

समग्र प्रदर्शन "समस्या" यहां है कि यह पायथन के भीतर स्ट्रिंग को दोहराता है। इसलिए यह एक स्ट्रिंग इरेटरेटर बनाता है और फिर प्रत्येक चरित्र को एक वास्तविक स्ट्रिंग ऑब्जेक्ट के रूप में अलग-अलग रूप से उत्पन्न करता है। यह बहुत अधिक उपरि है और मुख्य कारण है कि प्रत्येक समाधान जो पायथन में स्ट्रिंग को फिर से काम करता है, धीमा हो जाएगा।

वही समस्या collection.Counter साथ है। यह पायथन में कार्यान्वित किया गया है, हालांकि यह बहुत ही कुशल और लचीला है, यह एक ही मुद्दे से ग्रस्त है, यह गति के मामले में मूल के पास कभी नहीं है।

मैं किसी दिए गए अनुक्रम में न्यूक्लियोटाइड की गिनती की रोसलिंड की बुनियादी समस्या को हल करने की कोशिश कर रहा हूं, और परिणामों को एक सूची में लौटा रहा हूं। (बायोइनफॉरमैटिक्स से परिचित नहीं होने वाले उन लोगों के लिए यह सिर्फ 4 अलग-अलग वर्णों ('ए', 'सी', 'जी', 'टी') की आबादी की संख्या की गणना कर रहा है)

मुझे कलेक्शंस क्वॉंटर की सबसे तेज़ विधि होने की उम्मीद है (सबसे पहले क्योंकि वे उच्च प्रदर्शन का दावा करते हैं, और दूसरा क्योंकि मैंने इस विशिष्ट समस्या के लिए इसका उपयोग करने वाले बहुत से लोगों को देखा था)।

लेकिन मुझे आश्चर्य है कि यह विधि धीमी है !!

मैंने तीन अलग-अलग तरीकों की तुलना की, समय का उपयोग करते हुए और दो प्रकार के प्रयोग timeit :

  • एक लंबी अनुक्रम कई बार चल रहा है
  • एक छोटी सी अनुक्रम कई बार चल रहा है

यहां मेरा कोड है:

import timeit
from collections import Counter

# Method1: using count
def method1(seq):
    return [seq.count('A'), seq.count('C'), seq.count('G'), seq.count('T')]

# method 2: using a loop
def method2(seq):
    r = [0, 0, 0, 0]
    for i in seq:
        if i == 'A':
            r[0] += 1
        elif i == 'C':
            r[1] += 1
        elif i == 'G':
            r[2] += 1
        else:
            r[3] += 1
    return r

# method 3: using Collections.counter
def method3(seq):
    counter = Counter(seq)
    return [counter['A'], counter['C'], counter['G'], counter['T']]


if __name__ == '__main__':

    # Long dummy sequence
    long_seq = 'ACAGCATGCA' * 10000000
    # Short dummy sequence
    short_seq = 'ACAGCATGCA' * 1000

    # Test 1: Running a long sequence once
    print timeit.timeit("method1(long_seq)", setup='from __main__ import method1, long_seq', number=1)
    print timeit.timeit("method2(long_seq)", setup='from __main__ import method2, long_seq', number=1)
    print timeit.timeit("method3(long_seq)", setup='from __main__ import method3, long_seq', number=1)

    # Test2: Running a short sequence lots of times
    print timeit.timeit("method1(short_seq)", setup='from __main__ import method1, short_seq', number=10000)
    print timeit.timeit("method2(short_seq)", setup='from __main__ import method2, short_seq', number=10000)
    print timeit.timeit("method3(short_seq)", setup='from __main__ import method3, short_seq', number=10000)

परिणाम:

Test1: 
Method1: 0.224009990692
Method2: 13.7929501534
Method3: 18.9483819008

Test2:
Method1: 0.224207878113
Method2: 13.8520510197
Method3: 18.9861831665

विधि 1 दोनों तरीकों के लिए विधि 2 और 3 की तुलना में तेजी है !!

तो मेरे पास सवाल का एक सेट है:

-मैं कुछ गलत कर रहा हूं या यह अन्य दो तरीकों से वास्तव में धीमी है? क्या कोई एक ही कोड चला सकता है और परिणाम साझा कर सकता है?

-यदि मेरे परिणाम सही हैं, (और शायद यह एक और सवाल होना चाहिए) क्या विधि 1 की तुलना में इस समस्या को हल करने के लिए एक तेज़ तरीका है?

-यदि गिनती तेज है, तो संग्रह के साथ क्या सौदा है ??


यह इसलिए नहीं है क्योंकि collections.Counter दुर्घटना धीमी है, यह वास्तव में बहुत तेज है, लेकिन यह एक सामान्य उद्देश्य उपकरण है, वर्णों की गिनती सिर्फ कई अनुप्रयोगों में से एक है।

दूसरी ओर str.count पर स्ट्रिंग्स में वर्णों की गणना की जाती है और इसका भारी रूप से अनुकूलित किया जाता है क्योंकि यह एक और केवल कार्य है।

इसका मतलब यह है कि str.count अंतर्निहित सी- str.count सरणी पर काम कर सकता है, जबकि यह पुनरावृत्त के दौरान नया (या ऊपर की तलाश में) लम्बाई-1-अजगर-स्ट्रिंग बनाने से बच सकता है (जो कि और Counter क्या है)।

बस इस कथन को कुछ और संदर्भ जोड़ने के लिए

एक स्ट्रिंग सी सरणी के रूप में संग्रहीत है जिसे अजगर ऑब्जेक्ट के रूप में लपेटा गया है। str.count जानता है कि स्ट्रिंग एक संकीर्ण सरणी है और इस प्रकार उस चरित्र को परिवर्तित करती है जिसे आप सी- "वर्ण" के साथ str.count चाहते हैं, फिर मूल सी कोड में सरणी से दोहराता है और समानता के लिए जांच करता है और आखिर में लपेटता है और इसकी संख्या वापस करता है अवसरों पाया

दूसरी ओर और Counter अजगर-चलना-प्रोटोकॉल का उपयोग करें आपकी स्ट्रिंग के प्रत्येक अक्षर को अजगर-वस्तु के रूप में लपेट दिया जाएगा और फिर इसे (हैश और) अजगर के भीतर उनकी तुलना करेंगे।

इसलिए मंदी का कारण है:

  • प्रत्येक चरित्र को एक पायथन ऑब्जेक्ट में बदला जाना चाहिए (यह प्रदर्शन हानि का प्रमुख कारण है)
  • लूप पायथन में किया जाता है (अजगर 3.x में Counter लागू नहीं क्योंकि इसे सी में पुनः लिखा गया था)
  • प्रत्येक तुलना को पायथन में किया जाना चाहिए (केवल सी वर्णों की संख्या की तुलना करने के बजाय संख्याओं के आधार पर)
  • काउंटर को मूल्यों को हश करने की आवश्यकता है और आपके लूप को आपकी सूची को अनुक्रमित करने की आवश्यकता है।

ध्यान दें मंदी का कारण प्रश्न के समान है क्यों अजगर की सरणी धीमी है? ।

मैंने कौन सा बिंदु collections.Counter पर पता लगाने के लिए कुछ अतिरिक्त मानक str.countstr.count को str.count पर str.count किया str.count । इस अंतराल के लिए मैंने यादृच्छिक स्ट्रिंग्स को अलग-अलग वर्णों के साथ बनाया और प्रदर्शन को साजिश रची।

from collections import Counter
import random
import string

characters = string.printable  # 100 different printable characters

results_counter = []
results_count = []
nchars = []

for i in range(1, 110, 10):
    chars = characters[:i]
    string = ''.join(random.choice(chars) for _ in range(10000))
    res1 = %timeit -o Counter(string)
    res2 = %timeit -o {char: string.count(char) for char in chars}
    nchars.append(len(chars))
    results_counter.append(res1)
    results_count.append(res2)

और परिणाम matplotlib का उपयोग प्लॉट किया गया था:

import matplotlib.pyplot as plt

plt.figure()

plt.plot(nchars, [i.best * 1000 for i in results_counter], label="Counter",   c='black')
plt.plot(nchars, [i.best * 1000 for i in results_count],   label="str.count", c='red')
plt.xlabel('number of different characters')
plt.ylabel('time to count the chars in a string of length 10000 [ms]')
plt.legend()

पायथन 3.5 के लिए परिणाम

पायथन 3.6 के परिणाम बहुत समान हैं इसलिए मैंने उन्हें स्पष्ट रूप से सूचीबद्ध नहीं किया।

इसलिए यदि आप 80 अलग-अलग वर्णों को गिनना चाहते हैं तो Counter तेजी से / तुलनीय हो जाता है क्योंकि यह स्ट्रिंग को एक बार str.count करता है और कई बार str.count तरह नहीं। यह स्ट्रिंग की लंबाई का कमजोर रूप से निर्भर होगा (लेकिन परीक्षण ने केवल बहुत कम अंतर दिखाया +/- 2%)।

पायथन 2.7 के लिए परिणाम

पायथन -2.7 collections.Counter में। काउंटर अजगर (सी के बजाय) और बहुत धीमा का उपयोग करके कार्यान्वित किया गया था। str.count और Counter लिए ब्रेक-पॉइंट पॉइंट एक्सट्रपलेशन द्वारा केवल अनुमान लगाया जा सकता है क्योंकि 100 अलग-अलग वर्णों के साथ str.count अभी भी 6 गुना तेज है।





bioinformatics