السبت، 19 نوفمبر، 2011

قليلٌ من المرح مع الأكواد و الخوارزمات ^_^

أريد في هذه المرة أن نمرح قليلاً مع الأكواد ^_^

حيث سأضرب مثالاً بسيطاً لكيفية اختلاف الخوارزمات algorithms التي تؤدي نفس الوظيفة، و كيف يمكن أن يكون أحدها أفضل من الآخر من حيث السرعة و الكفاءة، و كيفية المقارنة السريعة بين أداء كل الخوارزمات !

المعضلة:
فلنتخيل أن معنا مجموعةً من الأعداد تبدأ بالعدد (min) و تنتهي بالعدد (max)، حيث يزيد كل عددٍ عن سابقه بقيمة (step)، و أن لدينا ملف نصي مساره (path) هو (test_fname)، هذا الملف مخزنٌ فيه مجموعةٌ كبيرة من الأعداد، و هي مرتبةٌ بحيث أن كل عددٍ في سطرٍ بمفرده كما يلي:
و نحن نريد أن نأخذ كل عددٍ من مجموعة الأعداد المحصورة بين (min) و (max) و نعرف كم عدداً في الملف أكبر منه أو يساويه، و كم عدداً أصغر منه.

الحل: 
و قد وجدتُ حينما أردتُ كتابة الدالة function التي تقوم بهذه العملية أن هناك خوارزمين يصلحان لهذا:
  • الأول:
    هو أن نأخذ في كل مرة عدداً من مجموعة الأعداد (فلنطلق عليه "المرجع")، و نقوم بقراءة الملف و نعد الأعداد التي داخله و التي قيمتها أكبر من قيمة "المرجع"، و كذلك الأرقام التي قيمتها أصغر من قيمة "المرجع"، و هكذا حتي تنتهي مجموعة الأعداد.
  • الثاني:
    هو أن نقرأ في كل مرة عدداً واحداً من الأرقام المخزنة في الملف ليكون هو "المرجع" هذه المرة، و نقوم بمقارنته بكل مجموعة الأعداد المحصورة بين (min) و (max)، و هكذا حتي تنتهي الأعداد في الملف.

التطبيق:
و بناء implementation هذه الدوال كما يلي:
مع ملاحظة أن البناء سيكون بلغة الـ++C ( للأسف الشديد)؛ حيث أنني كنت أعمل بها حينما قابلني هذا الموقف في العمل، و لا قدرة لي حالياً علي كتابة الشفرة بلغة أسهل مثل الـjava أو الـ#C، فاعذروني علي هذا.
بناء الخوارزم الأول:
بناء الخوارزم الثاني:
و أكتفي الآن بملاحظةٍ بسيطةٍ هي: أن الدالة الأولي ربما تكلف وقتاً أكبر؛ نظراً لأنها ستجعلنا نقرأ الملف أكثر من مرة، لأننا سنقرأ كل أعداده عند مقارنتها بكل عددٍ من أعداد مجموعة الأعداد المرجعية، بينما يتم قراءة الملف في الدالة الثانية مرةً واحدةً فقط.
و نظراً لأن القراءة من الملف قد تكلف وقتاً أكبر من القراءة لأعدادٍ مخزنة في الذاكرة و يشير إليها مؤشر pointer: فإن هذا يعني استهلاكَ وقتٍ أكبر، و حتي و إن كان الفارقُ ضئيلاً جداً فإن هذا سيشكل فارقاً كبيراً حينما نكتب الكثير و الكثير من الدوال في المشاريع الضخمة، و من ثم يبدوا تراكم الفروقات الصغيرة واضحاً بقوة.
و لكن الأمر الوحيد الذي يمكن أن يجعل مقارنتا هذه خاطئةً تماماً هو أن تكون مكتبة الـ++C تقوم بقراءة الملف من الذاكرة في المرات التي تلي قراءته للمرة الأولي، أي أنها تحمل الملف في الذاكرة ثم تقوم بعدها في كل مرة بالتعامل مع نسخة الذاكرة، و ليس النسخة الموجودة علي القرص الصلب. و ساعتها ستكون الدالة الأولي أفضل في الأداء، كما أنها كما هو ملاحظ أقل من حيث عدد الأسطر.
إذاً فيجب أن نجرب كلا البنائين و نقيس الوقت الذي استغرقه كلا منهما منذ بداية استدعاء الدالة حتي إنهائها لعملها.
    أكتفي بهذا نظراً للانشغال الجديد، و لكن فيما بعد إن شاء الله عز و جل ربما أقوم بشرح هاتين الدالتين و توضيح الفروق بينهما جيداً.

ليست هناك تعليقات:

إرسال تعليق