بخش ۳: لیست در پایتون (List)

لیست یک ساختمان داده است که دنباله ای از مقادیر را در خود نگه می دارد. هر عنصر لیست با استفاده از اندیس آن قابل دسترسی است. به عنوان مثال به عنصر(i+1)-ام لیست a با [a[i دست می یابیم. ،معمولا در زبان برنامه نویسی پایتون لیست و آرایه معادل هم در نظر گرفته می شوند.  بجز تفاوت در نحوه پیاده سازی، تفاوت اصلی لیست با آرایه آن است که طول لیست می تواند تغییر کند. به عنوان مثال می توان عنصری را به انتهای یک لیست اضافه نمود یا عنصری را از آن حذف کرد.

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

نحوه کار با لیست در پایتون

تعریف لیست خالی[] = a
تعریف لیست خالی — روش دوم()a = list

پرسش ۱: یافتن دو عدد با مجموع ویژه

دنباله ای از اعداد صحیح یکتا و یک عدد ویژه (target) داده شده اند. برنامه ای بنویسید که  به عنوان خروجی، اندیس دو عنصر از این دنباله که حاصل جمعشان برابر با مقدار ویژه است را برگرداند. فرض کنید که برای هر ورودی دقیقا یک راه حل وجود دارد.

پاسخ

ابتدا سعی کنیم با آوردن مثالی ساده پرسش را بهتر درک کنیم. فرض کنیم دنباله زیر به عنوان ورودی داده شود

و مقدار ویژه که دنبالش هستیم 10 باشد آنگاه باید اندیس دو مقداری را بیابیم که مجموع آنها 10 می شود.در نگاه اول ممکن است بنظر برسد که دو پاسخ برای این ورودی وجود دارد بخاطر اینکه 5+5 و 8+2 هر دو برابر 10 می شوند. این موضوع را باید با مصاحبه کننده در میان بگذاریم. فرض ما این است که مصاحبه کننده تاکید می کند که اندیسهای خروجی باید متفاوت باشند. بنابراین پاسخ درست 8 و 2 و خروجی مورد نظر اندیسهای آندو یعنی 0 و 2 است.

معمولا اولین روشی که به دنبال آن هستیم روش جستجوی کامل است. در این پرسش جستجوی کامل یعنی عناصر دنباله را دو به دو با هم جمع کنیم و با مقدار ویژه مقایسه کنیم. هرگاه مقدار ویژه به عنوان حاصل مشاهده شد اندیس دو مقدار یافته شده را برگردانیم. روش جستجوی کامل n * (n-1)/2 زوج بوجود می آورد و نیاز به یک لیست به طول N دارد که مقادیر را در خود نگه دارد.

در این لحظه مصاحبه کننده ما را برای یافتن اولین راه حل عملی تحسین می کند. اما واضح است که این روش کند است و روی یک لیست مثلا یک میلیونی خیلی کند است. مصاحبه کننده ما را برای برنامه نویسی سیستم هایی می خواهد که داده های زیادی دارند و باید الگوریتم بهینه با سرعت مناسب بکار ببرند. بنابراین از ما میپرسد که چگونه می شود این را بهتر کرد؟

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

مصاحبه کننده به ما اجازه می دهد که راه حل را پیاده کنیم. ابتدا یک نام مناسب برای تابع و پارامترهای مناسب آن را در نظر می گیریم. سپس پارامتر ها و معنای آن را برای مصاحبه کننده توضیح می دهیم و نظر مصاحبه کننده را جویا می شویم (خط ۱). اولین پارامتر این تابع input می باشد که یک رشته حاوی دنباله ای از اعداد است.

سپس همزمان که بدنه تابع را می نویسیم خط به خط برنامه را برای مصاحبه کننده توضیح می دهیم. با توجه به نیاز به تکرار پیمایش روی مقادیر دنباله، بهترین راه، نگهداری مقادیر دنباله در یک لیست است. برای این کار رشته را به لیستی  از مقادیر صحیح تبدیل می کنیم (خط ۲). این کار توسط متد split انجام می شود که یک رشته را در محل های وقوع کاراکتر space(فاصله) می شکند. سپس تابع map هر یک از این مقادیر را تبدیل به یک عدد صحیح (int) می کند. سپس حاصل را به یک لیست تبدیل می کند و در متغیر nums قرار می دهد.

با بکارگیری دو متغیر به عنوان اندیس، می توانیم هر دو عنصر ممکن از لیست را با هم جمع و با مقدار ویژه مقایسه کنیم . ساده ترین روش  برای پیاده سازی استفاده از دو حلقه تو در توست (خطهای ۴ تا ۷). حلقه بیرونی (خط ۴)، عناصر لیست را به ترتیب از ابتدا تا انتها می پیماید. برای هر عنصر در حلقه بیرونی، حلقه درونی (خطوط ۵ تا ۷) تمام عناصر بعد از آن تا انتهای لیست را می پیماید. هر تکرار در حلقه  درونی یک زوج ممکن از عناصر لیست را ایجاد میکند. با محاسبه مجموع این زوج مشخص می شود که آیا مجموع آندو برابر مقدار ویژه می شود. تکه کد زیر این روش شده را پیاده می کند.

def twoSum(input, target):
	nums = list(map(int, input.split()))
	nums_len = len(nums)
	for i in range(nums_len):
		for j in range(i+1, nums_len):
			if nums[i] + nums[j]==target:
				return [i , j]

تحلیل سرعت برنامه: برنامه فوق از دو متغیر i و j استفاده می کند. متغیر i کندرو می باشد و در حلقه بیرونی هر بار یک واحد زیاد می شود. با این کار مقدار آن قدم به قدم از صفر تا num_len-1 تغییر می کند. متغیر j  تندرو می باشد. این متغیر در حلقه درونی استفاده می شود و مقدارش از i+1 تا num_len-1 قدم به قدم زیاد می شود. به ازای یک قدم پیشروی متغیر کندرو روی لیست، متغیر تندرو یکبار کامل تا انتهای آرایه را می رود. با اغماض می توان گفت که متغیر کندرو num_len قدم پیش می رود و به ازای هر قدمش متغیر تندرو num_len قدم پیش می رود. بنابراین تعداد مراحل پیدا کردن زوج عنصر مورد نظر این پرسش حداکثر num_len*num_len می باشد. از این رو، اگر طول لیست را بجای num_len با n نشان دهیم، می توانیم بگوییم که پیچیدگی محاسباتی این برنامه o(n2)می باشد.

پرسش ۲: خرید و فروش بهینه یک سهم

لیستی از ارزش هر سهم یک موسسه در یک بازه زمانی داده شده است. با فرض اینکه تنها می توانید یک سهم این موسسه را خرید و فروش کنید، برنامه ای بنویسید که بیشترین سود ممکن از این کار را برگرداند.

پاسخ

ابتدا نیاز داریم که پرسش را بهتر درک کنیم. با آوردن یک مثال باید مطمین شویم که منظور مصاحبه کننده را درست متوجه شده ایم. این بسیار مهم است که مساله درست را حل کنیم.

فرض کنیم که قیمت سهام یک شرکت فرضی در روزهای متوالی را داریم.

در این مثال اگر سهم را در روز اول بخریم و همان روز بفروشیم هیچ سودی نکرده ایم. اگر آن را در روز اول بخریم و در روز دوم بفروشیم در واقع دو واحد ضرر کرده ایم. اگر سهم را روز دوم بخریم و روز چهارم بفروشیم ۵ واحد سود کرده ایم. بیشترین سود با خرید در روز سوم و فروش در روز پنجم بدست می آید. در این صورت مقدار سود 8-18 یا به عبارتی 10 می باشد.

در یک برنامه اطلاعات نمودار فوق را می توانیم در لیست زیر قرار دهیم.

اولین راه حلی که به دنبال آن هستیم جستجوی کامل است. برای این کار باید هر یک از روزها را برای خرید و هریک از روزهای بعد آن را برای فروش امتحان کنیم. به عبارتی دیگر باید هر یک از روزها را برای فروش و همه روزهای قبل آن را برای خرید امتحان کنیم و سود حاصل را بدست آوریم. ما متوجه این موضوع هستیم که این دوتعبیر حل با جستجوی کامل با هم معادل می باشند. اما در ارایه روش سریعتر می فهمیم که تعبیر دوم کار را برای یافتن راه بهینه هموار می کند. با استفاده از روش جستجوی کامل بیشترین سود ممکن مشخص می شود. برای امتحان کردن روزهای خرید و فروش مختلف می توانیم از دو حلقه تو در تو استفاده کنیم که شمارنده حلقه بیرونی اندیس روز فروش و شمارنده حلقه درونی اندیس روز خرید در لیست را مشخص می کنند. در واقع در هر تکرار حلقه بیرونی، متغیر شمارنده حلقه درونی از صفر تا یک کمتر از شمارنده حلقه بیرونی افزایش می یابد. اگر تعداد روزهای کل که اطلاعات سهام را داریم n باشد آنگاه n*(n-1)/2 ترکیب ممکن برای خرید و فروش را باید محاسبه کنیم. بنابر این پیچیدگی محاسباتی این الگوریتم O(n2)می باشد. این الگوریتم یک قدم درست برای حل این مساله است. اما مصاحبه کننده از شما میخواهد که راه حل سریع تری بیابید.

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

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

سپس شروع به نوشتن برنامه می کنیم. تابعی با نام مناسب و یک پارامتر از نوع لیست تعریف می کنیم (خط 2). یک متغیر به نام pmin برای نگهداری کمترین قیمت سهام با مقدار اولیه بینهایت (بعبارت دقیقتر بزرگترین مقدار صحیح در پایتون) در نظر میگیریم (خط 4). یک متغیر دیگر به نام profit برای نگهداری بیشینه سود با مقدار اولیه صفر در نظر میگیریم (خط 5). سپس با استفاده از یک حلقه تکرار در هر تکرار میزان مینیمم کنونی را بروز می کنیم. برای این کار کمینه مقدار بین مقدار جدید و کمینه کنونی را محاسبه میکنیم (خط 8). آنگاه سود حاصل خرید یک سهم در روز i ام را با فرض خرید با قیمت کمینه در روزهای گذشته محاسبه می نماییم. این مقدار بیشینه سود در صورتی که سهم را در روز iام بفروشیم بدست می آید. بیشینه این مقدار را با بیشینه سود ممکن در روزهای گذشته محاسبه می کنیم و به عنوان میزان بیشینه سود در نظر میگیریم (خط 9). نهایتا میزان بیشینه سود ممکن را برمی گردانیم. تکه کد زیر پیاده سازی الگوریتم بهینه را نشان می دهد.

import sys 
def maxProfit(prices):
	pmin = sys.maxint
	profit = 0

	for i in range(len(prices)):    
		pmin = min(prices[i], pmin)
		profit = max(profit, prices[i]-pmin)
	
	return profit

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

پرسش ۳: پیداکردن عدد گمشده

تعداد n-1 عدد غیر تکراری با مقادیر 1 تا n داده شده اند. برنامه ای بنویسید که عددی از بازه 1 تا ‌n که در بین این n-1 عدد نیست (عدد گمشده) را بیابد.

پاسخ

کار را با یک مثال شروع میکنیم تا مطمین شویم که مساله را درست خوانده ایم. مثلا اگر 7  عدد غیر تکراری در بازه 1 تا 8 بصورت زیر داشته باشیم، عدد گمشده بین آنها 6 می باشد.

اولین تلاش برای یافتن پاسخ مساله استفاده از روش جستجوی کامل است. برای این کار با استفاده از یک حلقه تکرار هر بار به دنبال یکی از اعداد 1 تا n درون لیست اعداد می گردیم. مقداری که در لیست پیدا نشود جواب مورد نظر می باشد. برای این کار در بدترین حالت عدد گم شده n است که در این صورت در آخرین تکرار حلقه یافت می شود. از آنجا که در هر تکرار باید مقداره همه عناصر لیست را با یک مقدار مقایسه نماییم، تعداد کل مقایسه ها n*(n-1) می باشد. بنابر این پیچیدگی محاسباتی این روش O(n2) می باشد. این روش کند است و روی یک لیست طولانی بسیار زمان می برد. در ادامه برای یافتن راه حل بهتر پیشنهاد می کنیم که اگر لیست را مرتب کنیم سوراخ آن (عدد گمشده) خیلی راحت  پیدا می شود. در واقع اگر لیست را مرتب کنیم سپس هر عدد i باید در موقعیت i-1 در لیست قرار گرفته باشد (اندیس لیست از صفر شروع می شود). برای چک کردن این از یک حلقه تکرار که از 1 شروع می شود و تا n-1 می رود استفاده می کنیم. اگر عدد در موقعیت مورد نظر وجود نداشت جواب مساله را یافته ایم. تکه کد زیر این الگوریتم را پیاده می کند. یک اشتباه رایج این است که فراموش کنیم که محاسبات انجام شده در تابع sort (خط 2) را در محاسبه سرعت الگوریتم در نظر بگیریم و فکر کنیم چون این الگوریتم تنها دارای یک حلقه است که n-1 بار تکرار می شود، پیچیدگی محاسباتی کل برنامه O(n) است. اما در واقع بخاطر اینکه خود تابع sort دارای پیچیدگی محاسباتی O(n*log(n))می باشد، کل برنامه نیز با سرعت O(n*log(n))اجرا می شود.

def findMissing(nums, n):
	nums = sorted(nums)
	for i in range(1, n):
		if nums[i-1] != i:
			return i
	return n

راه حل با استفاده از مرتب سازی به اندازه ای که فکرش را میکردیم سریع نبود. در ادامه تفکر برای یافتن راه حل خطی (O(n)) راه ادامه می دهیم. برای پیدا کردن روش بهینه کافی است به این نکته توجه کنیم که یک فرمول برای محاسبه مجموع همه مقادیر از 1 تا n وجود دار. این فرمول  S=n * (n+1)2 می باشد. از آنجا که عدد گم شده در این حاصل جمع وجود ندارد، می توان آن را بر اساس تفاوت بین S و مجموع عناصر لیست پیدا کرد. تکه کد زیر پیاده سازی این روش را نشان می دهد.

def findMissing(nums, n):
	return n * (n+1) / 2 - sum(nums)

تابع sum (خط 2) مجموع عناصر لیست را محاسبه می کند. پیچیدگی محاسباتی این الگوریتم برابر با پیچیدگی تابع sum است که خطی است.





GiottoPress by Enrique Chavez