Foldl هو ذيل متكرر، فكيف يعمل Foldr بشكل أسرع من Foldl؟

Question

كنت أرغب في اختبار Foldl مقابل Foldr.مما رأيته، يجب عليك استخدام Foldl over Foldr عندما يكون ذلك ممكنًا بسبب تحسين التكرار الخلفي.

هذا يبدو منطقيا.ومع ذلك، بعد إجراء هذا الاختبار، أنا في حيرة من أمري:

Foldr (يستغرق 0.057 ثانية عند استخدام أمر الوقت):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

Foldl (يستغرق 0.089 ثانية عند استخدام أمر الوقت):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

من الواضح أن هذا المثال تافه، لكنني في حيرة من أمري بشأن سبب تفوق Foldr على Foldl.ألا ينبغي أن تكون هذه حالة واضحة حيث يفوز Foldl؟

Answer 1

مرحبًا بك في عالم التقييم الكسول.

عندما تفكر في الأمر من حيث التقييم الصارم ، تبدو FoldL "جيدة" و Foldr تبدو "سيئة" لأن Foldl هو عودية ذيل ، ولكن يجب على Foldr إنشاء برج في المكدس حتى يتمكن من معالجة العنصر الأخير أولاً.

ومع ذلك ، فإن التقييم كسول يحول الجداول. خذ ، على سبيل المثال ، تعريف وظيفة الخريطة:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

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

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

لقد أتضح أن map يمكن وصفها من حيث foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs

من الصعب معرفة ذلك من خلال النظر إليها ، لكن التقييم الكسول يبدأ لأن Foldr يمكن أن يعطيه f حجة الأولى على الفور:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

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

الآن ، التقييم كسول يعض. على سبيل المثال ، حاول تشغيل SUM [1..1000000]. أنه ينتج عنه فائض مكدس. لماذا يجب عليه؟ يجب أن يتم التقييم فقط من اليسار إلى اليمين ، أليس كذلك؟

دعونا نلقي نظرة على كيف يقيمها Haskell:

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

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

لحسن الحظ ، هناك وظيفة خاصة في Data.list تسمى foldl' التي تعمل بدقة. foldl' (+) 0 [1..1000000] لن تكدس الفائض. (ملاحظة: حاولت استبدال foldl مع foldl' في الاختبار الخاص بك ، لكنه جعلها في الواقع تعمل أبطأ.)

Answer 2

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

الفرق في كيفية foldl و foldr تطبيق وظيفة التخفيض. أنظر إلى foldr الحالة ، يمكننا توسيعها كـ

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

تتم معالجة هذه القائمة بواسطة sum, الذي يستهلكها على النحو التالي:

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

لقد تركت تفاصيل القائمة المتسلسل ، ولكن هذه هي الطريقة التي يستمر بها التخفيض. الجزء المهم هو أن كل شيء تتم معالجته من أجل تقليل عبور القائمة. ال foldr يعبر القائمة مرة واحدة فقط ، لا تتطلب التسلسلات عبور قائمة مستمرة ، و sum أخيرًا يستهلك القائمة في تمريرة واحدة. من الأهمية بمكان ، رئيس القائمة متاح من foldr على الفور ل sum, ، لذا sum يمكن أن تبدأ العمل على الفور ويمكن أن تكون القيم GC'D عند توليدها. مع أطر عمل الانصهار مثل vector, ، حتى القوائم الوسيطة من المحتمل أن تنصهر.

قارن هذا مع foldl وظيفة:

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

لاحظ الآن أن رئيس القائمة غير متوفر حتى foldl انتهى. هذا يعني أنه يجب بناء القائمة بأكملها في الذاكرة من قبل sum يمكن أن تبدأ في العمل. هذا أقل كفاءة بشكل عام. تشغيل النسختين مع +RTS -s يظهر أداء جمع القمامة البائس من إصدار Foldl.

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

أستخدم القاعدة التالية لتحديد أفضل خيار fold

• للطيات التي هي اختزال, ، استعمال foldl' (على سبيل المثال ، سيكون هذا هو اجتياز/أخيرة)
• خلاف ذلك استخدام foldr.
• لا تستخدم foldl.

في معظم الحالات foldr هو أفضل وظيفة طية لأن اتجاه اجتياز هو الأمثل للتقييم البطيئة للقوائم. إنه أيضًا الشخص الوحيد القادر على معالجة القوائم اللانهائية. صرامة إضافية foldl' يمكن أن يجعل الأمر أسرع في بعض الحالات ، ولكن هذا يعتمد على كيفية استخدام هذا الهيكل ومدى كسوله.

Answer 3

لا أعتقد أن أي شخص قد قال بالفعل الإجابة الحقيقية على هذا السؤال حتى الآن، إلا إذا فاتني شيء ما (والذي قد يكون صحيحًا ومرحبًا به مع التصويتات السلبية).

أعتقد أن الاختلاف الأكبر في هذه الحالة هو ذلك foldr يبني القائمة مثل هذا:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

بينما foldl يبني القائمة مثل هذا:

((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]

الفرق دقيق، لكن لاحظ ذلك في foldr إصدار ++ يحتوي دائمًا على عنصر قائمة واحد فقط كوسيطة يسرى.مع ال foldl الإصدار، هناك ما يصل إلى 999999 عنصرًا فيه ++الوسيطة اليسرى (في المتوسط ​​حوالي 500000)، ولكن عنصر واحد فقط في الوسيطة اليمنى.

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

لهذا السبب foldl الإصدار أبطأ بكثير.الأمر لا علاقة له بالكسل في رأيي.

Answer 4

المشكلة هي أن تحسين عودة الذيل هو تحسين الذاكرة ، وليس تحسين وقت التنفيذ!

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

لذلك ، فإن Foldl في الواقع "جيد" و lovr هو "سيء".

على سبيل المثال ، بالنظر إلى تعريفات Foldr و Foldl:

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)

هذه هي الطريقة التي يتم بها تقييم تعبير "Foldl (+) 0 [1،2،3]:

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

لاحظ أن Foldl لا يتذكر القيم 0 ، 1 ، 2 ... ، ولكن تمرير التعبير بأكمله (((0+1) +2) +3) كوسيطة بتكس Foldl ، حيث تصل إلى حالة الأساس وإرجاع القيمة التي تم تمريرها لأن المعلمة الثانية (z) لم يتم تقييمها بعد.

من ناحية أخرى ، هكذا يعمل طية:

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

الفرق المهم هنا هو أنه عندما يقوم FoldL بتقييم التعبير بأكمله في المكالمة الأخيرة ، وتجنب الحاجة إلى العودة للوصول إلى القيم المذكورة ، Foldr No. foldr تذكر عدد صحيح واحد لكل مكالمة ويقوم بإضافة في كل مكالمة.

من المهم أن تضع في اعتبارك أن Foldr و FoldL ليسا دائمًا ما يعادلان. على سبيل المثال ، حاول حساب هذه التعبيرات في العناق:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

Foldr و Foldl متكافئان فقط في ظل ظروف معينة موصوفة هنا

(اسف على سوء لغتي الانجليزية)

Answer 5

ل ، [0.. 100000] يجب توسيع القائمة على الفور بحيث يمكن أن تبدأ FoldR بالعنصر الأخير. ثم أثناء طي الأشياء معًا ، فإن النتائج الوسيطة هي

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

نظرًا لأنه لا يُسمح لأي شخص بتغيير قيمة القائمة هذه (Haskell هي لغة وظيفية خالصة) ، فإن المترجم حر في إعادة استخدام القيمة. القيم المتوسطة ، مثل [99999, 100000] يمكن أن تكون ببساطة مؤشرات في الموسعة [0.. 100000] قائمة بدلا من قوائم منفصلة.

ل B ، انظر إلى القيم المتوسطة:

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

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

نظرًا لأنك تقوم فقط بإنشاء نسخة من القائمة ، فإن تشغيل أسرع لأنه يبدأ بتوسيع القائمة الكاملة ثم يستمر في نقل مؤشر من الجزء الخلفي من القائمة إلى الأمام.

Answer 6

لا هذا ولا ذاك foldl ولا foldr هو الذيل محسّن. إنه فقط foldl'.

ولكن في حالتك باستخدام ++ مع foldl' ليست فكرة جيدة لأن التقييم المتتالي ++ سوف يسبب اجتياز تراكم النمو مرارا وتكرارا.

Answer 7

حسنًا ، اسمحوا لي أن أعيد كتابة وظائفك بطريقة يجب أن يكون هذا الاختلاف واضحًا -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

ترى أن B أكثر تعقيدًا من A. إذا كنت تريد أن تكون دقيقًا a يحتاج إلى خطوة تخفيض واحدة حتى يتم حساب القيمة ، ولكن b يحتاج اثنين. هذا يجعل الفارق الزمني الذي تقيسه ، في المثال الثاني يجب أن يتم تنفيذ التخفيضات.

// تحرير: لكن تعقيد الوقت هو نفسه ، لذلك لن أزعجني ذلك كثيرًا.