هي الصفوف أكثر كفاءة من قوائم الثعبان ؟
https://stackoverflow.com/questions/68630
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل هناك أي الفارق في الأداء بين المجموعات وقوائم عندما يتعلق الأمر مثيل واسترجاع العناصر ؟
المحلول
على dis وحدة يفكك البايت كود وظيفة و مفيد لمعرفة الفرق بين الصفوف و القوائم.
في هذه الحالة, يمكنك أن ترى أن الوصول إلى عنصر يولد متطابقة رمز ، ولكن هذا إسناد tuple هو أسرع بكثير من تعيين قائمة.
>>> def a():
... x=[1,2,3,4,5]
... y=x[2]
...
>>> def b():
... x=(1,2,3,4,5)
... y=x[2]
...
>>> import dis
>>> dis.dis(a)
2 0 LOAD_CONST 1 (1)
3 LOAD_CONST 2 (2)
6 LOAD_CONST 3 (3)
9 LOAD_CONST 4 (4)
12 LOAD_CONST 5 (5)
15 BUILD_LIST 5
18 STORE_FAST 0 (x)
3 21 LOAD_FAST 0 (x)
24 LOAD_CONST 2 (2)
27 BINARY_SUBSCR
28 STORE_FAST 1 (y)
31 LOAD_CONST 0 (None)
34 RETURN_VALUE
>>> dis.dis(b)
2 0 LOAD_CONST 6 ((1, 2, 3, 4, 5))
3 STORE_FAST 0 (x)
3 6 LOAD_FAST 0 (x)
9 LOAD_CONST 2 (2)
12 BINARY_SUBSCR
13 STORE_FAST 1 (y)
16 LOAD_CONST 0 (None)
19 RETURN_VALUE
نصائح أخرى
في عام ، قد تتوقع الصفوف أن تكون أسرع قليلا.ومع ذلك يجب أن اختبار بالتأكيد قضية محددة (إذا كان الفرق قد تؤثر على أداء البرنامج الخاص بك -- تذكر "سابق لأوانه الأمثل هو أصل كل الشرور").
بيثون يجعل هذا من السهل جدا: مرةلا هو صديقك.
$ python -m timeit "x=(1,2,3,4,5,6,7,8)"
10000000 loops, best of 3: 0.0388 usec per loop
$ python -m timeit "x=[1,2,3,4,5,6,7,8]"
1000000 loops, best of 3: 0.363 usec per loop
و...
$ python -m timeit -s "x=(1,2,3,4,5,6,7,8)" "y=x[3]"
10000000 loops, best of 3: 0.0938 usec per loop
$ python -m timeit -s "x=[1,2,3,4,5,6,7,8]" "y=x[3]"
10000000 loops, best of 3: 0.0649 usec per loop
حتى في هذه الحالة ، مثيل تقريبا أمر من حجم أسرع tuple ، ولكن الوصول إلى العنصر هو في الواقع إلى حد ما أسرع القائمة!حتى إذا كنت تقوم بإنشاء عدد قليل من الصفوف والوصول إليها العديد من الأوقات فإنه قد يكون في الواقع أسرع من استخدام قوائم بدلا من ذلك.
بالطبع إذا كنت تريد أن تغيير عنصر قائمة بالتأكيد سوف يكون أسرع منذ كنت بحاجة إلى إنشاء جديدة كاملة tuple إلى تغيير عنصر واحد من ذلك (منذ الصفوف غير قابلة للتغيير).
ملخص
الصفوف تميل إلى أداء أفضل من قوائم تقريبا في كل فئة:
1) يمكن أن تكون الصفوف ثابت مطوية.
2) المجموعات يمكن إعادة استخدامها بدلا من نسخها.
3) الصفوف المدمجة و لا فوق تخصيص.
4) الصفوف مباشرة المرجعية عناصرها.
المجموعات يمكن أن تكون ثابتة مطوية
الصفوف من الثوابت يمكن precomputed طريق بايثون ثقب الباب محسن أو AST-محسن.قوائم ، من ناحية أخرى ، الحصول على المبنية من الصفر:
>>> from dis import dis
>>> dis(compile("(10, 'abc')", '', 'eval'))
1 0 LOAD_CONST 2 ((10, 'abc'))
3 RETURN_VALUE
>>> dis(compile("[10, 'abc']", '', 'eval'))
1 0 LOAD_CONST 0 (10)
3 LOAD_CONST 1 ('abc')
6 BUILD_LIST 2
9 RETURN_VALUE
الصفوف لا تحتاج إلى نسخها
تشغيل tuple(some_tuple) يعود فورا نفسها.منذ الصفوف غير قابلة للتغيير ، ليس لديهم ليتم نسخها:
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
في المقابل ، list(some_list) يتطلب من جميع البيانات التي سيتم نسخها إلى قائمة جديدة:
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
الصفوف لا الإفراط في تخصيص
منذ tuple حجم ثابت ، فإنه يمكن تخزين متقاربة أكثر من القوائم التي تحتاج إلى أكثر من تخصص إلى جعل إلحاق() عمليات فعالة.
وهذا يعطي الصفوف لطيفة الفضاء ميزة:
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200
هنا هو التعليق من الكائنات/listobject.ج هذا يفسر ما يسرد يفعلون:
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
* Note: new_allocated won't overflow because the largest possible value
* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
الصفوف الرجوع مباشرة إلى عناصر
مراجع إلى الكائنات تدرج مباشرة في tuple الكائن.في المقابل, القوائم طبقة إضافية من المراوغة خارجية مجموعة من المؤشرات.
وهذا يعطي الصفوف الصغيرة ميزة السرعة المفهرسة المشاهدة والتفريغ:
$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop
$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop
هنا كيف tuple (10, 20) يتم تخزين:
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject *ob_item[2]; /* store a pointer to 10 and a pointer to 20 */
} PyTupleObject;
هنا كيف قائمة [10, 20] يتم تخزين:
PyObject arr[2]; /* store a pointer to 10 and a pointer to 20 */
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
Py_ssize_t allocated;
} PyListObject;
علما بأن المجموعة كائن يشتمل على اثنين من المؤشرات البيانات مباشرة في حين القائمة كائن طبقة إضافية من المراوغة خارجية مجموعة عقد اثنين من المؤشرات البيانات.
الصفوف ، كونها ثابتة ، هي أكثر كفاءة الذاكرة;قوائم الكفاءة ، overallocate الذاكرة من أجل السماح بإلحاق دون مستمر reallocs.لذلك, إذا كنت ترغب في تكرار خلال مستمر تسلسل القيم في التعليمات البرمجية الخاصة بك (على سبيل المثال for direction in 'up', 'right', 'down', 'left':), الصفوف المفضلة ، لأن مثل هذه الصفوف هي المحسوبة مسبقا في وقت الترجمة.
الوصول إلى سرعات يجب أن يكون نفس (كلاهما تخزين متجاورة المصفوفات في الذاكرة).
ولكن ، alist.append(item) يفضل كثيرا atuple+= (item,) عند التعامل مع البيانات قابلة للتغيير.تذكر الصفوف تهدف إلى تعامل السجلات دون أسماء الحقول.
عليك أن تنظر أيضا في array وحدة في المكتبة القياسية إذا كانت جميع العناصر في القائمة الخاصة بك أو المجموعة هي من نفس نوع C.وسوف يستغرق أقل من الذاكرة ويمكن أن يكون أسرع.
الصفوف ينبغي أن يكون قليلا أكثر كفاءة و بسبب ذلك, أسرع, من قوائم لأنها غير قابلة للتغيير.
هنا هو آخر الصغير المعيار ، من أجل ذلك..
In [11]: %timeit list(range(100))
749 ns ± 2.41 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [12]: %timeit tuple(range(100))
781 ns ± 3.34 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [1]: %timeit list(range(1_000))
13.5 µs ± 466 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [2]: %timeit tuple(range(1_000))
12.4 µs ± 182 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [7]: %timeit list(range(10_000))
182 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [8]: %timeit tuple(range(10_000))
188 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [3]: %timeit list(range(1_00_000))
2.76 ms ± 30.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [4]: %timeit tuple(range(1_00_000))
2.74 ms ± 31.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [10]: %timeit list(range(10_00_000))
28.1 ms ± 266 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [9]: %timeit tuple(range(10_00_000))
28.5 ms ± 447 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
دعونا متوسط هذه:
In [3]: l = np.array([749 * 10 ** -9, 13.5 * 10 ** -6, 182 * 10 ** -6, 2.76 * 10 ** -3, 28.1 * 10 ** -3])
In [2]: t = np.array([781 * 10 ** -9, 12.4 * 10 ** -6, 188 * 10 ** -6, 2.74 * 10 ** -3, 28.5 * 10 ** -3])
In [11]: np.average(l)
Out[11]: 0.0062112498000000006
In [12]: np.average(t)
Out[12]: 0.0062882362
In [17]: np.average(t) / np.average(l) * 100
Out[17]: 101.23946713590554
يمكنك تسميتها تقريبا حاسمة.
ولكن بالتأكيد الصفوف أخذت 101.239% الوقت ، أو 1.239% وقت إضافي للقيام بهذه المهمة مقارنة القوائم.
السبب الرئيسي Tuple أن تكون فعالة جدا في القراءة لأنه غير قابل للتغيير.
لماذا ثابتة الكائنات هي سهلة القراءة ؟
والسبب هو الصفوف يمكن تخزينها في ذاكرة التخزين المؤقت ، على عكس القوائم.البرنامج دائما قراءة من قوائم موقع الذاكرة كما أنها قابلة للتغيير (يمكن أن تتغير في أي وقت).
