تكرار الحروف بالتوازي

التعليمات

احسب تكرار الحروف في النصوص باستخدام الحوسبة المتوازية.

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

المهام غير المتزامنة

المهام هي التجريد الأساسي لكتابة الكود غير المتزامن في Lean. وهي خفيفة، وقد تُنفَّذ بالتوازي على خيط آخر، أو بالتزامن على الخيط نفسه.

قد تكون المهام نقية أو غير نقية. تُنشأ المهام النقية باستخدام Task.spawn، الذي يقبل حسابًا نقيًا. أما المهام غير النقية فتُنشأ من حسابات IO باستخدام، على سبيل المثال، IO.asTask، الذي يرفع IO α إلى Task α داخل موناد IO.

في هذا التمرين، الدالة calculateFrequencies مونادية، إذ تُرجع IO (Std.TreeMap Char Nat). وهذا يتيح استخدام المهام غير النقية عبر IO.asTask، ويجعل من الممكن أيضًا إنشاء مهام نقية لحسابات وسيطة قبل إرجاع القيمة النهائية.

منع سباقات البيانات

بما أن Lean لغة دالية، فإن معظم القيم فيها دائمة، أي غير قابلة للتغيير. العمليات التي تبدو وكأنها تعدّل قيمة ما تُنتج في الواقع قيمة جديدة تتضمن التغييرات المطلوبة. وهذا يعني أنه يمكن غالبًا مشاركة الذاكرة بأمان بين المهام دون إحداث سباقات بيانات.

لاحظ مع ذلك أن ليست كل هياكل البيانات مناسبة بالقدر نفسه للاستخدام الدائم. فعلى سبيل المثال، يتطلب تحديث عنصر واحد في Array عادةً نسخ المصفوفة بأكملها. وينطبق الأمر نفسه على Std.HashSet وStd.HashMap.

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

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

قياس سرعة التنفيذ

يُقاس زمن تنفيذ كل اختبار بالنانوثانية باستخدام IO.monoNanosNow ويُعرض إلى جانب النتائج. يمكنك تجربة أساليب مختلفة ومعرفة أثرها على أداء زمن التشغيل.