python - एक फेरबदल सूची की नकल बहुत धीमी क्यों है?




python-internals (3)

एक फेरबदल range(10**6) सूची की नकल करते हुए दस बार मुझे लगभग 0.18 सेकंड लगते हैं: (ये पांच रन हैं)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

दस बार अप्रमाणित सूची की प्रतिलिपि बनाने में मुझे लगभग 0.05 सेकंड का समय लगता है:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

यहाँ मेरा परीक्षण कोड है:

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

मैंने भी a[:] साथ नकल करने की कोशिश की, परिणाम समान थे (यानी, बड़ी गति अंतर)

बड़ी गति में अंतर क्यों? मैं प्रसिद्ध में गति के अंतर को जानता हूं और समझता हूं कि अनारक्षित सरणी की तुलना में सॉर्ट किए गए सरणी को संसाधित करना अधिक तेज़ क्यों है? उदाहरण, लेकिन यहाँ मेरे प्रसंस्करण का कोई निर्णय नहीं है। यह केवल आँख बंद करके सूची के संदर्भों को कॉपी कर रहा है, नहीं?

मैं विंडोज 10 पर पायथन 2.7.12 का उपयोग कर रहा हूं।

संपादित करें: पायथन 3.5.2 की कोशिश की, साथ ही अब परिणाम लगभग समान थे (लगभग 0.17 सेकंड तक लगातार फेरबदल किया, लगभग 0.05 सेकंड तक लगातार अप्रकाशित)। यहाँ उस के लिए कोड है:

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

जब आप सूची आइटम को फेरबदल करते हैं, तो उनके पास संदर्भ की बदतर स्थिति होती है, जिससे कैश प्रदर्शन खराब हो जाता है।

आप सोच सकते हैं कि सूची को कॉपी करना सिर्फ संदर्भों को कॉपी करता है, वस्तुओं को नहीं, इसलिए ढेर पर उनके स्थान मायने नहीं रखते। हालाँकि, प्रतिलिपि में अभी भी प्रत्येक वस्तु तक पहुँचने के लिए रिफंड को संशोधित करना शामिल है।


जैसा कि दूसरों द्वारा समझाया गया है, यह न केवल संदर्भों की नकल कर रहा है, बल्कि वस्तुओं के अंदर संदर्भ गणना को भी बढ़ाता है और इस प्रकार वस्तुएं पहुंच जाती हैं और कैश एक भूमिका निभाता है।

यहां मैं केवल और प्रयोग जोड़ना चाहता हूं। इतना नहीं के बारे में shuffled बनाम unshuffled (जहां एक तत्व तक पहुंचने से कैश की कमी हो सकती है लेकिन निम्नलिखित तत्वों को कैश में प्राप्त करें ताकि वे हिट हो जाएं)। लेकिन तत्वों को दोहराने के बारे में, जहां बाद में उसी तत्व की पहुंच कैश से टकरा सकती है क्योंकि तत्व अभी भी कैश में है।

एक सामान्य श्रेणी का परीक्षण:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

समान आकार की सूची लेकिन बार-बार दोहराए जाने वाले एक तत्व के साथ तेजी से होता है क्योंकि यह हर समय कैश को हिट करता है:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

और इससे कोई फर्क नहीं पड़ता कि यह किस संख्या में है:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

दिलचस्प है, यह तब और भी तेज हो जाता है जब मैं इसके बजाय एक ही दो या चार तत्वों को दोहराता हूं:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

मुझे लगता है कि कुछ एक ही काउंटर हर समय वृद्धि हुई पसंद नहीं करता है। शायद कुछ पाइपलाइन स्टाल क्योंकि प्रत्येक वृद्धि को पिछली वृद्धि के परिणाम के लिए इंतजार करना पड़ता है, लेकिन यह एक जंगली अनुमान है।

वैसे भी, दोहराया तत्वों की भी बड़ी संख्या के लिए यह कोशिश कर रहा है:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

आउटपुट (पहला कॉलम विभिन्न तत्वों की संख्या है, प्रत्येक के लिए मैं तीन बार परीक्षण करता हूं और फिर औसत लेता हूं):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

तो एक एकल (बार-बार) तत्व के बारे में 2.8 सेकंड से यह 2, 4, 8, 16 के लिए लगभग 2.2 सेकंड तक चला जाता है ... विभिन्न तत्व और सौ हजारों तक लगभग 2.2 सेकंड तक रहता है। मुझे लगता है कि यह मेरा L2 कैश (4 × 256 KB, मेरे पास i7-6700 ) का उपयोग करता है।

फिर कुछ चरणों में, समय 3.5 सेकंड तक चला जाता है। मुझे लगता है कि यह मेरे L2 कैश और मेरे L3 कैश (8 एमबी) के मिश्रण का उपयोग करता है, जब तक कि यह "समाप्त" भी नहीं हो जाता।

अंत में यह लगभग 3.5 सेकंड तक रहता है, मुझे लगता है क्योंकि मेरे कैश अब दोहराया तत्वों के साथ मदद नहीं करते हैं।


फेरबदल से पहले, जब ढेर में आवंटित किया जाता है, तो आसन्न सूचकांक ऑब्जेक्ट्स मेमोरी में आसन्न होते हैं, और एक्सेस किए जाने पर मेमोरी हिट दर अधिक होती है; फेरबदल के बाद, नई सूची के आसन्न सूचकांक की वस्तु स्मृति में नहीं है। बगल में, हिट दर बहुत खराब है।






python-internals