لماذا `(خريطة digitToInt) .المعرض هو بهذه السرعة ؟
https://stackoverflow.com/questions/4841078
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
تحويل غير سلبية Integer على قائمة من الأرقام يتم ذلك عادة مثل هذا:
import Data.Char
digits :: Integer -> [Int]
digits = (map digitToInt) . show
كنت أحاول أن أجد وسيلة أكثر مباشرة لأداء هذه المهمة ، دون إشراك سلسلة التحويل, ولكن أنا غير قادر على الخروج بشيء أسرع.
أشياء كنت أحاول حتى الآن:
خط الأساس:
digits :: Int -> [Int]
digits = (map digitToInt) . show
حصلت على هذا واحد من آخر السؤال على ستاكوفيرفلوو:
digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)
يحاول لفة بلدي:
digits3 :: Int -> [Int]
digits3 = reverse . revDigits3
revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
(0, digit) -> [digit]
(rest, digit) -> digit:(revDigits3 rest)
هذه كانت مستوحاة من showInt في Numeric:
digits4 n0 = go n0 [] where
go n cs
| n < 10 = n:cs
| otherwise = go q (r:cs)
where
(q,r) = n `quotRem` 10
الآن المؤشر.ملاحظة:أنا إجبار التقييم باستخدام filter.
λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)
هذا هو المرجع.الآن digits2:
λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)
هذا 3.46 مرات لفترة أطول.
λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)
digits3 هو 4.89 الوقت أبطأ.فقط من أجل المتعة ، حاولت فقط باستخدام revDigits3 وتجنب reverse.
λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)
الغريب أن هذا هو حتى أبطأ ، 5.24 مرات أبطأ.
و آخر واحد:
λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)
هذا هو 10.43 الوقت أبطأ.
كنت تحت انطباع بأن استخدام الحساب وسلبيات سوف يتفوق على أي شيء تنطوي على سلسلة التحويل.على ما يبدو هناك شيء لا أستطيع فهم.
فما الحيلة ؟ لماذا digits بهذه السرعة ؟
أنا باستخدام GHC 6.12.3.
المحلول
كما ترى لا أستطيع إضافة تعليقات حتى الآن, سوف تفعل القليل من العمل و تحليل كل منهم.سأضع تحليل في الأعلى ؛ ومع ذلك ، فإن البيانات ذات الصلة أدناه.(ملاحظة:كل هذا يتم في 6.12.3 وكذلك لا GHC 7 السحر بعد.)
تحليل:
النسخة 1: عرض جيد جدا بالنسبة رجات ، وخاصة أولئك قصيرة قدر علينا.مما يجعل السلاسل في الواقع يميل إلى أن يكون لائق في GHC;ومع ذلك القراءة سلاسل كتابة سلاسل كبيرة إلى ملفات (أو المعياري ، على الرغم من أنك لا تريد أن تفعل ذلك) حيث رمز يمكن على الاطلاق الزحف.وأظن أن الكثير من التفاصيل وراء السبب في هذا هو سريع جدا بسبب ذكي تحسينات في عرض رجات.
الإصدار 2: هذا واحد كان أبطأ من باقة عند تجميع.بعض المشاكل:عكس صارمة في الحجة.ما يعنيه هذا هو أنه لا فائدة من أن تكون قادرة على أداء العمليات الحسابية على الجزء الأول من القائمة بينما كنت الحوسبة القادمة العناصر ؛ لديك لحساب كل منهم ، الوجه لهم ، ثم لا الحسابية (وهي (`الدفاع` 10) ) على عناصر القائمة.في حين أن هذا قد تبدو صغيرة ، يمكن أن يؤدي إلى زيادة استخدام الذاكرة (ملاحظة 5GB من ذاكرة كومة الذاكرة المؤقتة المخصصة هنا كذلك) أبطأ الحسابية.(قصة قصيرة طويلة:لا تستخدم العكسي.)
الإصدار 3: تذكر كيف قلت لا تستخدم العكس ؟ اتضح إذا كنت تأخذ بها هذه واحدة قطرات 1.79 إجمالي وقت التنفيذ - بالكاد أبطأ من الأساس.المشكلة الوحيدة هنا هي أن تذهب أعمق في عدد ، كنت بناء العمود الفقري من القائمة في الاتجاه الخاطئ (أساسا أنت consing "في" قائمة مع العودية ، مقابل consing "على" قائمة).
الإصدار 4: هذا هو ذكي جدا في التنفيذ.يمكنك الاستفادة من عدة أشياء لطيفة:لأحد ، quotRem يجب استخدام خوارزميه إقليدس ، وهو لوغاريتمي في أكبر حجة.(ربما أسرع, ولكن أنا لا أعتقد أن هناك أي شيء أكثر من عامل ثابت أسرع من اقليدس.) وعلاوة على ذلك, يمكنك سلبيات على قائمة كما ناقش آخر الوقت بحيث لم يكن لديك لحل أي قائمة thunks كما تذهب - قائمة بالفعل تماما شيدت عندما كنت أعود إلى تحليل ذلك.كما يمكنك أن ترى أداء الفوائد من هذا.
هذا الرمز ربما كان أبطأ في GHCi لأن الكثير من التحسينات يؤديها مع -O3 العلم في GHC التعامل مع قوائم صنع أسرع, في حين GHCi لن تفعل أي من ذلك.
الدروس: سلبيات الطريقة الصحيحة على قائمة مراقبة المتوسطة التشدد التي يمكن أن تبطئ الحسابات, و القيام ببعض العمل في النظر في غرامة الحبيبات إحصاءات المدونة الخاصة بك الأداء.أيضا تجميع مع -O3 الأعلام:كلما كان لا كل هؤلاء الناس الذين وضعوا الكثير من الساعات في صنع GHC بسرعة فائقة على الكبير' جرو العيون عليك.
البيانات:
أنا فقط أخذت كل أربع وظائف ، عالقة في واحدة منها .الملف hs, ثم تغير كما الضروري أن تعكس وظيفة في الاستخدام.أيضا, لقد صدم الحد الخاص بك تصل إلى 5e6 ، لأنه في بعض الحالات التعليمات البرمجية المترجمة في أقل من نصف ثانية على 1e6, و هذا يمكن أن تبدأ يسبب تحبب مشاكل مع القياسات نحن نصنع.
خيارات برنامج التحويل البرمجي:استخدام ghc-جعل -O3 [filename].hs أن يكون قد اكتسب بعض التحسين.سنتخلص الإحصاءات إلى الخطأ المعياري باستخدام أرقام +RTS -sstderr.
الإغراق إلى sstderr يعطينا الناتج يشبه هذا في حالة digits1:
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
هناك ثلاثة الإحصاءات الأساسية هنا:
- إجمالي الذاكرة في استخدام:1MB فقط يعني هذا الإصدار هو جدا فعالة من حيث المساحة.
- مجموع الوقت:1.61 s لا يعني شيئا الآن ، ولكن سنرى كيف يبدو ضد تطبيقات أخرى.
- الإنتاجية:هذا هو فقط 100% ناقص القمامة جمع;بما أننا في 96.3% وهذا يعني أننا لا خلق الكثير من الأشياء التي تركها متناثرة في الذاكرة..
حسنا دعنا ننتقل إلى الإصدار 2.
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
حسنا, لذلك نحن نرى نمط مثيرة للاهتمام.
- نفس مقدار الذاكرة المستخدمة.هذا يعني أن هذا هو تطبيق جيد جدا, على الرغم من أنه قد يعني أننا بحاجة إلى الاختبار على العينة أعلى المدخلات لمعرفة ما اذا كنا نستطيع العثور على الفرق.
- يستغرق ضعف الوقت.سنعود إلى بعض التكهنات عن سبب هذا في وقت لاحق.
- انها في الواقع أكثر قليلا الإنتاجية ، ولكن بالنظر إلى أن GC ليست جزء كبير من البرنامج إما هذا لا يساعدنا أي شيء هام.
الإصدار 3:
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
حسنا, لذلك نحن نرى بعض أنماط غريبة.
- نحن ما زلنا في 1 ميغا بايت إجمالي الذاكرة في استخدام.لذا لم تصل أي شيء في الذاكرة غير الفعال ، وهو أمر جيد.
- لسنا في digits1, ولكن لدينا digits2 فاز بسهولة جدا.
- القليل جدا GC.(نضع في اعتبارنا أن أي شيء أكثر من 95% من إنتاجية جيدة جدا ، لذلك نحن لا نتعامل مع أي شيء أكثر أهمية من هنا.)
وأخيرا الإصدار 4:
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
الرئيس:!دعونا كسر عليه:
- نحن ما زلنا في 1MB المجموع.هذا هو بالتأكيد ميزة من هذه التطبيقات ، كما أنها تظل في 1MB على المدخلات من 5e5 و 5e7.دليل على الكسل ، إذا كنت سوف.
- نقطع حوالي 32% من الوقت الأصلي ، التي هي مؤثرة جدا.
- وأظن أن النسب هنا تعكس تحبب في sstderr الرصد بدلا من أي حساب على superluminal الجسيمات.
نصائح أخرى
الإجابة على السؤال "لماذا rem بدلا من وزارة الدفاع ؟" في التعليقات.عند التعامل مع القيم الإيجابية rem x y === mod x y لذلك فقط النظر في المذكرة الأداء:
> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)
فما هو الأداء ؟ إلا إذا كان لديك سبب وجيه لا (و كسولا لا سبب وجيه ولا لا يعرفون معيار) ثم استخدام أداة مرجعية ، كنت المعيار:
$ cat useRem.hs
import Criterion
import Criterion.Main
list :: [Integer]
list = [1..10000]
main = defaultMain
[ bench "mod" (nf (map (`mod` 7)) list)
, bench "rem" (nf (map (`rem` 7)) list)
]
تشغيل هذا يدل على rem هو ملموس أفضل من mod (جمعت مع -O2):
$ ./useRem
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950
benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950
