[CPCS 204] الدرس الثالث: Sorted List Matching Problem

[deathpain]

-----------------------------------------------

بسم الله الرحمن الرحيم
السلام عليكم ورحمة الله وبركاته

" لا تؤدى الأعمال العظيمة بالقوة , بل بالمثابرة " .. صاموئيل جونسون

-----------------------------------------------

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

في السابق كانت الطريقة المعتادة لحل هذه المشكلة كالتالي:
* نختار أي اسم من القائمة الأولى ومن ثم نذهب للقائمة الثانية ونبحث عن الاسم المشابه ثم نطبعه عن ايجاده.
* وإذا كانت القائمة غير مرتبة والاسم غير موجود فعندها سيترتب على ذلك البحث في كلا القائمتين علماً بأن حجم كلاً من القائمتين يساوي n فبالتالي الوقت المستغرق لمثل هذه العلمية يساوي n^2.


الكود الذي يوضح الطريقة:

كود PHP:

public static void printMatches(String[] list1, String[] list2){
for (int i=0;i<list1.length();i++){
for (int j=0;j<list2.length();j++){
if(list1[i].equalsIgnoreCase(list2[j]) 
System.out.println(list1[i]);
break;
} // End of 2nd Loop 
} // End of 1st Loop 
} // End of Method 


لكن ماذا لو استخدمنا الـBinarySearch في إيجاد الأسماء المتشابهة علماً بأن المجموعة الثانية مرتبة ؟

الطريقة:
* نبحث عن الإسم في منتصف القائمة الثانية، اذا تطابق مع الاسم المطلوب نقوم بطباعته.
* اذا لم يتطابق فإننا نبحث في النصف السفلي أو النصف العلوي وبهذا نكون قسمنا مساحة البحث إلى النصف في القائمة الثانية.
( نفس الطريقة التي تم شرحها في الموضوع السابق )

الكود الذي يوضح الطريقة:

كود PHP:

public static void printMatches(String[] list1, String[] list2){
for (int i=0;i<list1.length();i++){
if (binSearch(list2,list[i])
System.out.println(list1[i]);
} // End of Loop 
} // End of Method

public static int binSearch(String[] names, String key) {
int low = 0;
int high = names.length();
while (low < high){
int mid = (low + high) / 2;
if (key.equalsIgnoreCase(names[mid]))
high = mid;
else if ( !key.equalsIgnoreCase(names[mid]))
low = mid + 1;
else 
return 1;
} // End of loop
return 0;
} / / End of method 


بما أن العناصر في القائمة الأولى غير مرتبة فالزمن اللازم حتى ينبغي الانتهاء منها هو n
وبما أن العناصر في القائمة الثانية مرتبة فالزمن التي تستغرقه سيكون log n للأنه يمكن استخدام الـBinarySearch عليها.
إذا الزمن النهائي للعملية إذا كانت لدينا قائمتين أحدها مرتب والآخرى لأ هو n * log n ..

السؤال هنا: هل يمكننا تسريع العملية لأفضل من ذلك ؟
نعم يمكننا، ولكن كيف ؟
في المثال الثاني افترضنا أن القائمة الثانية مرتبة والأولى غير مرتبة، ولم نفترض أن الاثنين مرتبة معاً.


لنفرض الآن ان لدينا قائمتين:


عندما ننظر إلى القائمتين فإننا ندرك مباشرة أن أول اسمين لا يتطابقان وهما Adams و Boston لأن Adams من فئة حرف A و Boston من B


وعندها ننزل في القائمة الأولى للحرف B ونجد الإسم Bell ولكنه أيضاً لا يتطابق مع Boston


نصل في القائمة الأولى للحرف D اسم Davis وعندها يجب علينا الانتقال في القائمة الثانية لنفس الحرف، ونجد الاسم Davis ايضاً !! لدينا تطابق الآن.


وبنفس الطريقة نكمل، حرفاً حرفاً ولا ننتقل للوراء !


الطريقة كتابة:
* نضع مؤشرين لكل قائمة مؤشر واحد، نبدأ من الحرف الأول هجائياً
* نطابق أول اسمين يكون المؤشرين عليهما
* إذا لم يكن هنالك أي تطابق، فإننا ننتقل للاسم التالي في القائمة التي تملك الحرف الأسبق هجائياً (مثل Bell يسبق Boston هجائياً) فإننا ننتقل في القائمة الأولى لـ Davis ويبقى مؤشر القائمة الثانية على Boston.
* إذا كان هناك تطابق فإننا نطبع الإسمين وونتقل بالمؤشرين إلى الاسمين التاليين ( مثل حالة Davis و Davis ) فإننا نطبع الاسم وننتقل في القائمة الأولى إلى Harding وفي القائمة الثانية إلى Francis.
* نجد أن Francis يسبق Harding هجائياً إذا ننتقل للاسم الذي يليه في القائمة الثانية، Gamble وأيضاً هذا لا يتطابق ويسبق Harding ثم ننتقل للاسم الذي يليه في القائمة الثانية، نصل لـ Harding وهنا يتطابق الاسمان فنقوم بطباعتهما.
* ننتقل للاسمين التاليين من كل قائمة، Jenkins من القائمة الأولى و Mason من القائمة الثانية، Jenkins أسبق هجائياً إذا ننتقل في القائمة الأولى ... الخ، وهكذا حتى ننتهي من القائمة في دورة واحدة فقط !.

إذا لنفرض أن كل قائمة تحتوي على عدد n من العناصر، ونحن نتحقق من كل عنصر مرة واحدة فقط.
الزمن الكلي للتأكد من كافة العناصر هو 2n !! أي أسرع من كلتا الحالتين الأولى ( n^2 ) و ( n * Log n ).

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


الخلاصة: عدد العناصر التي لدينا هو 100 عنصر في كل قائمة.
* الزمن الذي استغرقته الطريقة العادية في المطابقة هو n^2 أي 10 آلاف عملية مطابقة.
* الزمن الذي استغرقته الطريقة الثانية باستخدام BinarySearch هو ( n * Log n ) أي 600 عملية مطابقة تقريباً.
* الزمن الذي استغرقته الطريقة الثانية باستخدام مؤشرين هو 2n أي 200 عملية مطابقة فقط.

بانتظار ردودكم واكوادكم واقتراحاتكم، انتهينا الآن من الدروس التي تعتبر مقدمة بسيطة للمنهج، وبدءاً من الدرس القادم ستصبح الأمور أكثر تعقيداً.

تم بحمد الله

[n3omh]

ماشالله تبآرك الله , الله يعطيك العآفيه

ليآ رجعه باليل أمخمخ عليه *_^

[Tony7]

مشكووور يا سيدي جزاك الله خير