חידת מהירות בפייתון

11/05/2018

שלושת הפונקציות הבאות עושות בדיוק את אותו הדבר. נסו להבין מה הן עושות ומי המהירה ביותר:

def rot1(a, n, k):
    return [a[(i+k) %n] for i in range(n)]
def rot2(a, n, k):
    for _ in range(k):
        a = a[1:] + [a[0]]
    return a
def rot3(a, n, k):                                
    res = a[:]
    for _ in range(k):
        temp = res[0]
        del(res[0])
        res.append(temp)
    return res

שלושת הפונקציות "מגלגלות" אלמנטים במערך k פעמים כך שהמערך המוחזר כולל את אותם איברים כמו המערך המקורי אבל כל איבר נמצא k מקומות שמאלה. לדוגמא:

In [52]: rot1([1,2,3,4,5], 5, 4)
Out[52]: [5, 1, 2, 3, 4]

ואיזה מהמימושים הוא המהיר ביותר? התשובה מורכבת. לקחתי מערך של אלף איברים והפעלתי את שלושת הפונקציות עליו פעמיים - פעם אחת עם k קטן ופעם שניה עם k גדול:

In [38]: timeit rot1(arr, len(arr), 10)
134 µs ± 2.7 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [37]: timeit rot2(arr, len(arr), 10)
52.9 µs ± 972 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [36]: timeit rot3(arr, len(arr), 10)
5.79 µs ± 56 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [58]: timeit rot1(arr, len(arr), len(arr) * 5)
123 µs ± 577 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [59]: timeit rot2(arr, len(arr), len(arr) * 5)
23.9 ms ± 141 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [60]: timeit rot3(arr, len(arr), len(arr) * 5)
1.26 ms ± 33.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

ככל ש k גדול יותר מגודל המערך כך המימוש הראשון מהיר יותר. זה הגיוני כי זמן העבודה שלו תלוי בגודל המערך. מצד שני כש k קטן מאוד מימוש זה הוא הגרוע ביותר.

בהשוואה בין שני האחרים השלישי מנצח בגדול: יצירת מערך חדש בכל איטרציה (בפייתון) היא פעולה הרבה יותר איטית מאשר מחיקה והוספה למערך קיים.

ומה לגבי NumPy? אז כמו תמיד בעבודה עם מערכים אם אתם מוכנים להכניס את NumPy למערכת כמעט תמיד תקבלו שיפור ביצועים לעומת קוד שכתבנו לבד. הפונקציה שם נקראת roll ואלה התוצאות שלה:

In [62]: timeit np.roll(na, len(arr) * 5)
12.2 µs ± 190 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [63]: timeit np.roll(na, 10)
14 µs ± 76.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)