پاکیزه کد بزنیم: لیست ها را هم اندازه کن و راحت مقایسه کن

فهرست مطالب

برای نوشتن یک برنامه خوب نه تنها باید الگوریتم خوبی داشته باشیم بلکه از تکنیکهایی استفاده کنیم که پیاده سازی آن را خلاصه تر ، خوانا و قابل فهم تر می کنند. به عبارت دیگر باید کد تمیز بنویسیم. در این نوشته نمونه ای از چنین تکنیکی را ارایه می کنیم.

تکنیک: برای مقایسه مقادیر دو لیست (کدام از دیگری بزرگتر است) معمولا از یک حلقه استفاده می شود که عناصر متناظر لیست ها را تا انتهای لیست کوچکتر با هم مقایسه می کند و پس از اتمام حلقه از ساختار شرطی استفاده می شود تا نتیجه نهایی را بدست آورد. در این نوشته در حین حل یک مثال الگوریتمی روشی را ارایه می کنیم که خیلی راحت تر بتوانیم دو لیست را با هم مقایسه کنیم.

پرسش: برنامه ای بنویسید که دو رشته که نشان دهنده نسخه های یک نرم افزارند را در یافت نماید. اگر اولین رشته نسخه جدید تری باشد مقدار 1، چنانچه دومی جدیدتر باشد مقدار 1-، و در صورت مساوی بودن 0 را برگرداند.

پاسخ: کار را با چند مثال شروع می کنیم (فهم مساله). اگریک نسخه نرم افزاری "1.02" و نسخه دیگر آن "1.02.1" باشد آنگاه بخش آخر رشته دوم (یعنی "1.") نشان می دهد که ورژن "1.02.1" مربوط به ویرایش اول از نسخه "1.02" است و جدیدتر است. بنابر اگر "1.02" ورودی اول این برنامه و "1.02.1" ورودی دوم باشد این تابع باید مقدار 1- را برگرداند. اگر رشته اولی "1.2" باشد باز هم نتیجه 1- است زیرا صفر در بخش دوم (یعنی 02) در مقدار عددی ورژن تاثیری ندارد. اگر رشته دومی "1.02.0" باشد در واقع این دو ورژن یکی هستند.

با توجه به مثال های بالا واضح است که استفاده از عملگرهای مقایسه ای (یعنی ==, > , <) پاسخ صحیح را برای این سوال نمی دهد، زیرا مقایسه رشته ای حالتهای شامل 0 که در مثالها گفتیم را بدرستی مدیریت نمی کنند (یافتن ایراد راه حل).

بنابر این یک راه حل درست باید مقادیر عددی بخش های متناظر از دو رشته را با هم مقایسه نماید نه خود رشته ها را (ارایه راه حل بهتر).  به عنوان مثال، رشته "1.2" را می توانیم بصورت لیستی از مقادیر صحیح [2, 1] در نظر بگیریم و رشته "1.02.1" را بصورت یک لیست از مقادیر صحیح [1, 2, 1] در نظر داشته باشیم. با مقایسه لیست ها از چپ به راست اولین نقطه ای که دو لیست با هم متفاوت باشند مشخص می کند که کدام یک بزرگتر است. در صورتی که دو لیست تفاوتی نداشته باشند به این معنا است که دو نسخه نرم افزار با هم برابرند.

شروع به پیاده سازی الگوریتم می کنیم و همزمان بانوشتن برنامه باید چیزهایی که در ذهنمان می گذرد را برای مصاحبه کننده توضیح دهیم (فکرمان را داد بزنیم). مثلا <<یک تابع با پارامترهای مناسب تعریف می کنیم. این تابع نیاز به دو پارامتر برای گرفتن ورژنهای ورودی دارد (خط 1). سپس از تابع split استفاده می کنیم که بخشهای هر ورژن را بدهد (خط 2 و 3). البته اینجا می توانستیم قبل این کارها چک کنیم که آیا مقدار پارامتر version1 تهی (None) هست.>>

می توانیم از مصاحبه کننده بپرسیم که آیا لازم هست که این شرط را بررسی کنیم. این سوال ما نشان می دهد که ما حالتهای ورودی در یک برنامه واقعی را می شناسیم و مطلعیم که ممکن است ورودی شکل مورد نظر ما را نداشته باشد. بررسی این حالت خیلی ساده است و پیشنهاد می کنیم که آن را اضافه کنیم. در اینجا برای اینکه برنامه کوتاه و قابل فهم باشد این شرط را نیاورده ایم.

<<پس از آنکه بخشهای ورژن را در آوردیم باید آنها را به عدد صحیح تبدیل کنیم. برای این کار از تابع map  استفاده می کنیم که در واقع تک تک مقادیر لیست (بخش های نسخه) را به عدد صحیح تبدیل می کند (خط 2). این کار را برای رشته دوم هم انجام می دهیم (خط 3).>>

حالا باید دو لیست را با هم مقایسه کنیم. برای این کار می توانیم یک حلقه تکرار بنویسیم که سراغ تک تک عناصر لیست می رود تا جایی که (۱) یکی از مقادیر متناظر مقایسه شده از دیگری بزرگتر باشد که در این صورت نتیجه را می دانیم، یا (۲) یا به انتهای لیست کوچکتر برسیم. حالت دوم به این معناست که همه مقادیر دو لیست تا اینجای کار با هم مساوی می باشند. شاید بنظر برسی که پس از خروج از حلقه باید اندازه لیست ها را با هم مقایسه کنیم تا لیست بزرگتر را به عنوان نسخه بزرگتر اعلام کنیم اما در مورد این مساله خاص باید این را در نظر بگیریم که لیست طولانی تر الزاما بزرگتر نیست. به این دلیل که ممکن است باقی مانده عناصر لیست بزرگتر همگی صفر باشند. مثلا لیست های مرتبط با رشته های "1.2" و "1.2.0" عبارتند از [2, 1] و [0, 2, 1]. با وجود اینکه تا عنصر اندیس 1 این دو لیست با هم برابرند و لیست دوم طولانی تر است، به این دلیل که مقادیر از اندیس 1 به بعد در لیست دوم صفر است، تفاوتی را در نسخه نرم افزار ایجاد نمی کند. بنابر این این دو لیست با هم برابرند.

برای اینکه این مشکل را حل کنیم می توانیم چک کنیم که آیا همه عناصر باقیمانده صفر می باشند. این کار برنامه ما را اندکی کثیف و ناخوانا می کند.

برای اینکه از بررسی شرطهای اضافی خلاص شویم، از یک تکنیک خوب استفاده می کنیم: در این تکنیک دو لیست را ابتدا هم اندازه می کنیم و سپس آنها را مقایسه می کنیم. بنابراین در خط 5 ابتدا تفاوت طول در لیست را محاسبه می کنیم. سپس با استفاده از امکانات زبان پایتون به راحتی تعداد صفر مناسب به انتها رشته ها اضافه می کنیم (خطوط 6 و 7). در انتها دو لیست را مستقیما با عملگرهای مقایسه ای مقایسه می کنیم (خطوط 9 و 11) و نیازی به نوشتن حلقه تکرار برای مقایسه نخواهیم داشت. نهایتا در خط نتیجه را برمی گردانیم.

تحلیل سرعت برنامه: یک اشتباه رایج آن است که تصور کنیم این برنامه دارای پیچیدگی محاسباتی (O(1 است به این خاطر که هیچ حلقه یا فراخوانی بازگشتی ای وجود ندارد. اما باید هزینه توابع موجود و از پیش تعریف شده در زبان برنامه نویسی را نیز جزو هزینه برنامه خود محاسبه کنیم. برنامه بالا از split، map و مقایسه لیست ها استفاده می کند که دارای پیچیدگی محاسباتی (O(nاست که در آن n مجموع طول دو رشته است.  بنابر این پیچیدگی محاسباتی این الگوریتم (O(n می باشد.