بيثون: ما مدى سرعة ذلك؟

Question

فترة أعصادي Mersenne المستخدمة في الوحدة النمطية random هو (قيل لي) 2 ** 19937 - 1. كرقم ثنائي ، أي عام 19937 '1 على التوالي (إذا لم أكن مخطئا). بيثون يحولها إلى عشرية جميلة بسرعة:

$ python -m timeit '2**19937'
10000000 loops, best of 3: 0.0271 usec per loop

$ python -m timeit -s 'result = 0' 'result += 2**19937'
100000 loops, best of 3: 2.09 usec per loop

أعتقد أن الإصدار الثاني هو الذي يتطلب التحويل؟

وهذا ليس فقط ثنائي. هذا سريع أيضا. (بدلاً من إظهار الأرقام ، أعرض طول العشري الذي تم تحويله إلى سلسلة):

>>> import math
>>> N = 1000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
10787
>>> N = 5000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
64921

توقيت:

python -m timeit -s 'import math' -s 'N=1000' 's = str((int(N*math.e))**(int(N*math.pi)))'
10 loops, best of 3: 51.2 msec per loop

والسؤال هو: كيف يتم هذا بالفعل؟

هل أنا فقط ساذج أن أعجب؟ أجد مشهد قشرة الثعبان التي تولد عددًا من 5000 مكان أو نحو ذلك في لحظة مذهلة حقًا.

يحرر:

توقيت إضافي اقترحه dalke و truppo

$ python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 230 usec per loop
$ python -m timeit 'x=2' 'int(x**19937)'
1000 loops, best of 3: 232 usec per loop
$ python -m timeit 'x=2' 'str(x**19937)'
100 loops, best of 3: 16.6 msec per loop

$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937'
1000 loops, best of 3: 237 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'int(result)'
1000 loops, best of 3: 238 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'str(result)'
100 loops, best of 3: 16.6 msec per loop

لذلك يبدو لي مثل result = 0; result += 2**19937 ربما يفرض التحويل.

Answer 1

بيثون يحولها إلى عشرية جميلة مرتق.

لا أعرف بيثون ، لكن لا ، لا يحتاج إلى القيام بذلك. 2^19937 لا تحتاج إلى حسابات ، إنه مجرد تحول ثنائي ("<<") مع 19937 ، لذلك فهو سريع للغاية. فقط إذا قمت بطباعة ذلك في العشرية ، يكون التحويل الفعلي ضروريًا وهذا أبطأ بكثير.

تحرير: يمكن أن يكون الأساسي هو نفسه التحول (= نقل النقطة) إذا كانت قاعدة الأرقام مطابقة لقاعدة الأسعار.

10^-1 = 0.1 10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1 (N Zeroes)

ترى هذا الأسعار من 10 مع الأسس N ببساطة تحول الرقم. تستخدم أجهزة الكمبيوتر الآن في الغالب القاعدة الداخلية 2 (بت) ، لذا فإن حساب 2^19937 هو وضع بعض الشيء في الموضع 19937 (عد مواقع بت من الصفر).
كمعلومات إضافية: يتم تنفيذ التحويل إلى العشري عادةً بواسطة خوارزمية قهر وإقامة تقسم الرقم على التوالي على قوى Ten. كما ترى ، فإن التحويل الفعلي أبطأ بعامل نصف مليون.

المثال الثاني أكثر إثارة للاهتمام: نظرًا لأنك تقوم بحساب M^n مع الأعداد الصحيحة الكبيرة M ، فإن أسرع طريقة هي مضاعفةها على التوالي وتخزين النتائج المؤقتة.

مثال: 10^345

أ = 10^2
ب = أأ = 10^4
ج = بب = 10^16
D = C*C = 10^256

النتيجة = دججججججججبب*10

(يمكن تحسينها: انظر Knuth ، الخوارزميات الناتجة)

لذلك تحتاج فقط إلى مضاعفات طويلة ويمكن حسابها بشكل فعال.

تحرير: يعتمد التنفيذ الدقيق للضرب: إلى جانب مضاعفة مضاعفة المدرسة العادية ، يتم استخدام تكاثر Karatsuba و Tom-Cooke و Schoenhagen-Strasse (FFT).

Answer 2

أكره أن تمطر على موكبك ، ولكن السبب في ذلك هو أن وحدة الرياضيات لم يتم تنفيذها بالفعل في بيثون.

يدعم Python تحميل المكتبات المشتركة التي تصدر واجهات برمجة تطبيقات Python ، ولكن يتم تنفيذها بلغات أخرى. Math.so ، والتي توفر الوحدة التي تحصل عليها import math, ، يحدث ليكون واحد من هؤلاء (وكذلك هو _random.so).

Answer 3

عند تجميع رمز البايت ، تعبيرات مستمرة مثل 2**19937 سيتم تحسينه إلى ثابت واحد:

>>> def foo(): return 2**10
... 
>>> import dis
>>> dis.dis(foo)
  1           0 LOAD_CONST               3 (1024)
              3 RETURN_VALUE        
>>> 

النظر بدلا من ذلك:

[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop

Answer 4

لا أعرف شيئًا عن أي شيء عن كيفية هذا في الحقيقة تم تنفيذه في Python ، ولكن بالنظر إلى أن هذا هو الضرب البدائي واللوغاريتمات بشكل أساسي ، لست مندهشًا بشكل رهيب أنه سريع بشكل معقول حتى على أعداد كبيرة جدًا.

هناك مكتبات رياضيات دقة تعسفية مثل GMP تنفذ مجموعة واسعة من العمليات بطريقة فعالة للغاية ، تم تحسينها في التجميع ، لهذا الغرض فقط.