هذا Haskell الخاص بك هو (وليس) مضروب فقط وجيد ل

عندما يتعلق الأمر باللغات المفضلة ، عادة ما أقول أنه ، مع تساوي جميع الأشياء الأخرى ، فإنني أفضل استخدام C ++ لكسارات الأرقام و Haskell على كل شيء آخر. من المفيد التحقق دوريًا مما إذا كان هذا التقسيم له ما يبرره ، وفي الآونة الأخيرة فقط ، ظهر سؤال خاملاً وبسيط للغاية: كيف سيتصرف مجموع جميع مقسومات الرقم مع نمو هذا العدد بالذات ، على سبيل المثال ، بالنسبة لأول مليار من الأرقام. من السهل تخويف هذه المهمة (من العار أن نسميها طاحونة الأرقام الناتجة) ، لذلك تبدو خيارًا رائعًا لمثل هذا الفحص.

بالإضافة إلى ذلك ، ما زلت لا أملك القدرة على التنبؤ بدقة بأداء كود هاسكل ، لذلك من المفيد تجربة الأساليب السيئة عن علم لمعرفة كيف سيتدهور الأداء.

حسنًا ، بالإضافة إلى ذلك ، يمكنك بسهولة إظهار خوارزمية أكثر كفاءة من البحث الأمامي عن المقسومات لكل رقم من $$$1$ إلى $$$ن$ .

خوارزمية

لذلك ، لنبدأ مع الخوارزمية.

كيفية العثور على مجموع جميع المقسومات على عدد $$$ن$ ؟ يمكنك الذهاب من خلال كل شيء $$$k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ ولكل مثل هذا $$$k_1$ تحقق ما تبقى من الانقسام $$$ن$ في $$$k_1$ . إذا كان الباقي هو $$$0$ ، ثم أضف إلى البطارية $$$k_1 + k_2$ حيث $$$k_2 = \ frac {n} {k_1}$ إذا $$$k_1 \ neq k_2$ و فقط $$$k_1$ على خلاف ذلك.

يمكن تطبيق هذه الخوارزمية $$$ن$ مرات ، لكل رقم من $$$1$ إلى $$$ن$ ؟ يمكنك بالطبع. ماذا ستكون الصعوبة؟ من السهل أن نرى هذا النظام $$$O (n ^ \ frac {3} {2})$ تقسيمات - لكل رقم ، نقوم بعمل جذر التقسيمات تمامًا ، ولدينا أرقام $$$ن$ . هل يمكننا أن نفعل ما هو أفضل؟ اتضح أن نعم.

واحدة من المشاكل مع هذه الطريقة هي أننا نضيع الكثير من الجهد. الكثير من الانقسامات لا تقودنا إلى النجاح ، مما يعطي ما تبقى غير صفري. من الطبيعي أن نحاول أن نكون أكثر كسولًا وأن نتعامل مع المهمة من الجانب الآخر: دعنا فقط نولد جميع أنواع المرشحين للقواسم ونرى ما هي الأرقام التي يرضونها؟

لذا ، دعونا الآن نحتاج إلى ضربة واحدة لكل رقم من $$$1$ إلى $$$ن$ احسب مجموع المقسومات. للقيام بذلك ، انتقل من خلال كل شيء $$$k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ ، ولكل من هذا القبيل $$$k_1$ دعنا نذهب من خلال كل شيء $$$k_2 \ in \ {k_1 \ dots \ lfloor \ frac {n} {k} \ rfloor \}$ . لكل زوج $$$(k_1 ، k_2)$ إضافة إلى الخلية مع الفهرس $$$k_1 \ cdot k_2$ معنى $$$k_1 + k_2$ إذا $$$k_1 \ neq k_2$ و $$$k_1$ على خلاف ذلك.

هذه الخوارزمية تفعل بالضبط $$$n ^ \ frac {1} {2}$ تؤدي الأقسام ، وكل عملية ضرب (أرخص من القسمة) إلى النجاح: في كل تكرار نزيد شيئًا ما. هذا هو أكثر فعالية بكثير من النهج الجبهي.

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

التنفيذ الأول

وبالمناسبة ، هذا هو تقريبا شبه رمزية للتنفيذ الأولي في هاسكل:

module Divisors.Multi(divisorSums) where import Data.IntMap.Strict as IM divisorSums :: Int -> Int divisorSums n = IM.fromListWith (+) premap IM.! n where premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor $ sqrt $ fromIntegral n ] , k2 <- [ k1 .. n `quot` k1 ] ] 

Main الوحدة بسيطة ، وأنا لا أحضرها.

بالإضافة إلى ذلك ، نعرض هنا المبلغ فقط لأكثر من غيرها $$$ن$ لسهولة المقارنة مع التطبيقات الأخرى. على الرغم من أن هاسكل هي لغة كسولة ، إلا أنه في هذه الحالة سيتم حساب جميع المبالغ (على الرغم من أن التبرير الكامل لذلك خارج عن نطاق هذه المقالة) ، لذلك لا ينجح أننا لن نحسب أي شيء عن غير قصد.

ما مدى سرعة العمل؟ على i7 3930k ، في تيار واحد ، تم عمل 100000 عنصر في 0.4 ثانية. في هذه الحالة ، يتم إنفاق 0.15 ثانية على الحسابات و 0.25 ثانية على GC. ونشغل حوالي 8 ميغابايت من الذاكرة ، على الرغم من أن حجم int يبلغ 8 بايت ، من الأفضل أن يكون لدينا 800 كيلو بايت.

جيد (ليس حقا). كيف ستنمو هذه الأرقام مع زيادة ، أم ، الأرقام؟ بالنسبة إلى 1000 عنصر ، تعمل لمدة 7.5 ثانية تقريبًا ، وتنفق ثلاث ثوانٍ على الحوسبة و 4.5 ثانية تنفق على GC ، وتحتل أيضًا 80 ميجابايت (أكثر 10 مرات من اللازم). وحتى إذا كنا نتظاهر بأننا من مطوري برمجيات Java كبار للمرة الثانية ونبدأ في ضبط GC ، فلن نقوم بتغيير الصورة بشكل كبير. سيء للغاية يبدو أننا لن ننتظر أبدًا مليار رقم ، ولن ندخل في الذاكرة أيضًا: لا يوجد سوى 64 غيغابايت من ذاكرة الوصول العشوائي على جهازي ، وسوف يستغرق حوالي 80 إذا استمر هذا الاتجاه.

يبدو الوقت للقيام به

الخيار C ++

دعونا نحاول الحصول على فكرة عما يعنيه السعي إلى تحقيقه ، ولهذا سنكتب الرمز على الإيجابيات.

حسنًا ، نظرًا لأن لدينا بالفعل خوارزمية تم تصحيحها ، فكل شيء بسيط:

 #include <vector> #include <string> #include <cmath> #include <iostream> int main(int argc, char **argv) { if (argc != 2) { std::cerr << "Usage: " << argv[0] << " maxN" << std::endl; return 1; } int64_t n = std::stoi(argv[1]); std::vector<int64_t> arr; arr.resize(n + 1); for (int64_t k1 = 1; k1 <= static_cast<int64_t>(std::sqrt(n)); ++k1) { for (int64_t k2 = k1; k2 <= n / k1; ++k2) { auto val = k1 != k2 ? k1 + k2 : k1; arr[k1 * k2] += val; } } std::cout << arr.back() << std::endl; } 

-O3 -march=native ، -O3 -march=native 8 ، تتم معالجة مليون عنصر في 0.024 ثانية ، -O3 -march=native 8 ميجابايت من الذاكرة المخصصة. مليار - 155 ثانية ، 8 غيغابايت من الذاكرة ، كما هو متوقع. أوه. هاسكل ليست جيدة. هاسكل يحتاج إلى طرد. فقط الفصائل و prepororphisms على ذلك والكتابة! أم لا؟

الخيار الثاني

من الواضح أن تشغيل جميع البيانات التي تم إنشاؤها من خلال IntMap ، أي في الواقع خريطة عادية نسبيًا - IntMap ملطفة ، ليس القرار الأكثر حكمة (نعم ، هذا هو الخيار الرديء الواضح الذي تم ذكره في البداية). لماذا لا نستخدم صفيفًا مثل كود C ++؟

لنجرب:

 module Divisors.Multi(divisorSums) where import qualified Data.Array.IArray as A import qualified Data.Array.Unboxed as A divisorSums :: Int -> Int divisorSums n = arr A.! n where arr = A.accumArray (+) 0 (1, n) premap :: A.UArray Int Int premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor bound ] , k2 <- [ k1 .. n `quot` k1 ] ] bound = sqrt $ fromIntegral n :: Double 

هنا نستخدم على الفور الإصدار غير المربّع من المصفوفة ، نظرًا لأن Int بسيط للغاية ، ولا نحتاج إلى الكسل فيه. يختلف الإصدار المحاصر فقط في نوع arr ، لذلك لا نفقد المصطلح أيضًا. بالإضافة إلى ذلك ، يتم إجراء الربط من أجل المنفصل بشكل منفصل هنا ، ولكن ليس لأن المحول البرمجي غبي ولا يفعل LICM ، ولكن لأنه بعد ذلك يمكنك تحديد نوعه بشكل صريح وتجنب تحذير من المحول البرمجي حول التقصير في الوسيطة floor .

0.045 ثانية لمليون عنصر (أسوأ مرتين فقط من الإيجابيات!). 8 ميغابايت من الذاكرة ، ميلي ثانية واحدة في GC (!). في أحجام أكبر ، يستمر الاتجاه - حوالي مرتين أبطأ من C ++ ، ونفس مقدار الذاكرة. نتيجة رائعة! ولكن هل يمكننا أن نفعل ما هو أفضل؟

اتضح أن نعم. accumArray بالتحقق من المؤشرات ، والتي لا نحتاج إلى القيام بها في هذه الحالة - المؤشرات صحيحة في الإنشاء. دعونا نحاول استبدال المكالمة إلى accumArray بـ unsafeAccumArray :

 module Divisors.Multi(divisorSums) where import qualified Data.Array.Base as A import qualified Data.Array.IArray as A import qualified Data.Array.Unboxed as A divisorSums :: Int -> Int divisorSums n = arr A.! (n - 1) where arr = A.unsafeAccumArray (+) 0 (0, n - 1) premap :: A.UArray Int Int premap = [ (k1 * k2 - 1, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor bound ] , k2 <- [ k1 .. n `quot` k1 ] ] bound = sqrt $ fromIntegral n :: Double 

كما ترون ، فإن التغييرات ضئيلة ، باستثناء الحاجة إلى فهرستها من نقطة الصفر (والتي ، في رأيي ، خطأ في مكتبة API ، ولكن هذا سؤال آخر). ما هو الأداء؟

مليون عنصر - 0.021 ثانية (نجاح باهر ، ضمن هامش الخطأ ، ولكن أسرع من الايجابيات!). بطبيعة الحال ، نفس 8 ميغابايت من الذاكرة ، نفس 0 مللي ثانية في GC.

مليار عنصر - 152 ثانية (يبدو أنه أسرع حقًا من الإيجابيات!). أقل بقليل من 8 غيغا بايت. 0 مللي ثانية في GC. الرمز لا يزال اصطلاحي. أعتقد أننا يمكن أن نقول أن هذا نصر.

في الختام

أولاً ، لقد فوجئت بأن استبدال accumArray بإصدار unsafe سيعطي هذه الزيادة. سيكون أكثر عقلانية توقع 10-20 بالمائة (بعد كل شيء ، في الإيجابيات ، استبدال operator[] بـ at() لا يعطي انخفاضًا كبيرًا في الأداء) ، ولكن ليس بمقدار النصف!

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

ثالثًا ، بالطبع ، هناك مزيد من التحسينات ممكنة ، وعلى جميع المستويات. أنا متأكد ، على سبيل المثال ، من أنه يمكنك الضغط أكثر قليلاً من الكود على الإيجابيات. ومع ذلك ، في رأيي ، في كل هذه المعايير ، فإن التوازن بين الجهد المبذول (ومقدار الكود) والعادم الناتج مهم. خلاف ذلك ، كل شيء في النهاية يتلاقى مع تحدي LLVM JIT أو شيء من هذا القبيل. بالإضافة إلى ذلك ، هناك بالتأكيد خوارزميات أكثر فاعلية لحل هذه المشكلة ، ولكن نتيجة التفكير القصير المقدم هنا ستنجح أيضًا في مغامرة الأحد الصغيرة هذه.

رابعًا ، المفضل لدي: يجب تطوير أنظمة الكتابة. ليست هناك حاجة unsafe هنا ، كمبرمج يمكنني إثبات أن k_1 * k_2 <= n لجميع k_1, k_2 صادفته في الحلقة. في عالم مثالي من اللغات المكتوبة بشكل يعتمد عليه ، أقوم بإنشاء هذا الدليل بشكل ثابت ونقله إلى الوظيفة المقابلة ، مما يزيل الحاجة إلى عمليات الفحص في وقت التشغيل. ولكن ، للأسف ، في هاسكل لا توجد zavtipov كاملة ، وفي اللغات التي توجد بها zavtipy (والتي أعرفها) ، لا توجد array ونظائرها.

خامسًا ، لا أعرف لغات البرمجة الأخرى بدرجة كافية للتأهل للحصول على علامات قريبة في هذه اللغات ، لكن أحد أصدقائي كتب نظيرًا في بيثون. بالضبط ما يقرب من مائة مرة أبطأ ، وأسوأ من الذاكرة. والخوارزمية نفسها بسيطة للغاية ، لذلك إذا كتب شخص ما على دراية تماثلية في Go أو Rust أو Julia أو D أو Java أو Malbolge في التعليقات ، أو إذا كان هناك مشاركة أخرى ، على سبيل المثال ، مع C ++ - شفرة على أجهزتهم - فمن المحتمل أن تكون رائعة .

ملاحظة: آسف لرأس clickbait قليلا. لم أستطع التوصل إلى أي شيء أفضل.