الگوریتم TwoSum در جاوا اسکریپت — به زبان ساده
یکی از بزرگترین پیشنیازهای به دست آوردن یک شغل کدنویسی این است که در مصاحبه فنی قبول شوید که به طور معمول شامل حل الگوریتمها است. یکی از ابتداییترین الگوریتمهایی که در این زمینه استفاده میشود، الگوریتم TwoSum در جاوا اسکریپت است. صورت مسئله در تصویر زیر توضیح داده شده است.
بیان مسئله
فرض کنید، آرایهای از دو عدد صحیح دارید. اندیسهای دو عدد را چنان بازگشت دهید که مجموع آنها برابر با هدف مشخصی باشد. میتوانید فرض کنید که هر ورودی دقیقاً یک راهحل دارد و نمیتوانید از یک عنصر واحد، دو بار استفاده کنید.
روش ساده Brute Force
افراد مبتدی عموماً ابتدا راهحل ساده Brute Force را امتحان میکنند. این راهحلها گرچه کار میکنند اما زمان پردازشی یا حافظه زیادی را اشغال میکنند. این وضعیت شبیه آن است که از یک بازوکا برای کشتن یک پشه بهره بگیریم. با این که این روش جواب میدهد، اما به هیچ وجه عاقلانه نیست.
اما به هر حال باید از جایی آغاز کرد. زمانی که یک راهحل Brute Force پیدا کنید که کار میکند میتوانید آن را همواره بازسازی کرده و بهبود ببخشید، پس از روش بازوکا آغاز میکنیم.
اگر همه عناصر آرایه را با همدیگر مقایسه کنیم، میتوانیم ببینیم که آیا مجموع دو عنصر مفروض برابر با هدف مورد نظر است یا نه. سپس میتوانیم اندیس هر یک از این دو عنصر را یافته و آنها را در آرایهای قرار داده و آن آرایه را بازگشت دهیم.
به بیان دیگر میتوانیم این کار را به وسیله حلقه تودرتو انجام دهیم:
1const twoSum = function(nums, target) {
2 for (let i = 0; i < nums.length; i++){
3 for (let j = 0; j < nums.length; j++ ) {
4 if (nums[i] + nums[j] === target && i !== j){
5 return [i,j]
6 }
7 }
8 }
9}
در ادامه راهحل فوق را جزءبهجزء توضیح میدهیم.
اگر معنی دستور زیر را بدانید، میتوانید از مطالعه توضیحات چند پاراگراف بعدی بگذرید:
1let i = 0; i < nums.length; i++)
i اختصاری برای عبارت index است. با تعیین i به مقدار صفر بیان میکنیم که کار خود را از عنصر نخست آغاز میکنیم:
1(index = 0);
به کار خود ادامه میدهیم تا این که به انتهای آرایه برسیم، یعنی زمانی که i برابر با طول آرایه شود. تا آن زمان پس از هر تکرار i را یک واحد افزایش میدهیم.
در همین حال، این کار را بار دیگر انجام میدهیم، اما این بار به عناصر اندیس j نگاه میکنیم.
اگر عنصری در اندیس i و عنصری در اندیس j بیابیم که مجموعشان برابر با عدد مورد نظر باشد و اگر عددی که در اندیس i یافتهایم با عددی که در اندیس یافتهایم یکسان نباشد، میدانیم که دو عنصر جدا یافتهایم که الزامات ما را برآورده میسازند. سپس اندیسهای آنها یعنی i و j را در یک آرایه قرار میدهیم.
این راهحل بهکندی کار میکند:
این راهحل در مثال فوق شاید چندان کند به نظر نرسد، چون آرایه تنها چهار عنصر دارد. برای بررسی عنصر آیتم در برابر آیتمهای دیگر در آرایهای چهار عنصری تنها 16 یا $$2^{4}$$ مقایسه باید انجام دهیم.
اما اگر 4000 عنصر داشته باشیم، در این صورت $$2^{4000}$$ مقایسه خواهیم داشت. به بیان دیگر برای n عنصر در آرایه باید n^2 مقایسه انجام دهیم. به زبان ریاضیات و نماد O پیچیدگی این عملیات $$n^{2}$$ است که بسیار کُند محسوب میشود.
یک راهحل بهتر میتواند پیچیدگی O(n) داشته باشد، یعنی از روی هر آرایه تنها یک بار عبور کن.
بهتر، هوشمندانهتر و سریعتر
یکبار دیگر مسئله را تصور میکنیم. فرض کنید یک سبد پر از توپ دارید که هر کدام وزن متفاوتی دارند و میخواهید بدانید آیا دو توپ وجود دارد که وزن آنها در مجموع برابر با x باشد؟ در راهحل نخست ما همه ترکیبهای توپها را تا زمان پیدا کردن پاسخ صحیح بررسی کردیم.
در راهحل بعدی قصد داریم کار خود را از همان سبد توپ (سبد شماره 1) به همراه یک سبد خالی (سبد شماره 2) آغاز کنیم. برای هر توپ در سبد شماره 1 باید مراحل زیر را اجرا کنیم:
- توپ را وزن میکنیم (آن را توپ کنونی مینامیم).
- وزن توپ کنونی را از وزن هدف کم میکنیم تا وزن مورد نیاز را بیابیم. این همان مقداری است که توپ دیگر در راهحل باید داشته باشد. بنابراین اگر وزن توپ کنونی 2 گرم باشد و وزن هدف 10 گرم باشد، وزن مورد نیاز 8 گرم خواهد بود.
- در ادامه وِردی روی سبد شماره 2 میخوانیم و از آن میخواهیم که توپ به وزن 8 گرم را به بیرون پرتاب کند. البته در دفعه اول که این کار را انجام میدهیم، سبد شماره 2 خالی است، اما این موضوع اشکالی ایجاد نمیکند.
- اگر آن چه که به دنبالش هستیم را در سبد شماره 2 نیافتیم، وزن توپ کنونی را روی آن مینویسیم و آن را در سبد شماره 2 میاندازیم.
این کار را چندین بار انجام میدهیم تا این که نهایتاً...
- توپ کنونی وزنی برابر با 8 گرم داشته باشد.
- وزن مورد نظر را از وزن توپ کنونی کم میکنیم تا 2 گرم به دست آید.
- با مراجعه به سبد شماره 2 میتوانیم توپی که 2 گرم وزن داشت و وزنش را روی آن نوشته بودیم را پیدا کنیم.
- بدین ترتیب یک جفت توپ یافتهایم.
کدنویسی
1var twoSum = function(nums, target) {
2 const previousValues = {};
3 for (let i = 0; i < nums.length; i++) {
4 const currentNumber = nums[i];
5 const neededValue = target - currentNumber;
6 const index2 = previousValues[neededValue];
7 if (index2 != null){
8 return [index2, i];
9 } else {
10 previousValues[currentNumber] = i;
11 // hash[key] = value
12 }
13 }
14}
در ادامه کد فوق را توضیح میدهیم.
هش خالی previousValues همان سبد شماره 2 است که توپها را پس از بررسیشان در آن میاندازیم. currentNumber توپ کنونی است یعنی آن توپی که در اندیس i آرایه nums قرار دارد. neededValue وزن مورد نیاز ما است.
1const index2 = previousValues[neededValue];
index2 جایی است که توپ را با وزن مورد نظر در آرایه اصلی مییابیم (در صورت وجود توپ).
1if (index2 != null){
2 return [index2, i];
اگر index2 وجود داشته باشد، توپ تطبیق یافته با وزن مورد نیاز وجود دارد و از این رو مکان توپ تطبیق یافته و موقعیت توپ کنونی را بازگشت میدهیم.
1} else {
2 previousValues[currentNumber] = i;
3 // hash[key] = value
4}
اگر index2 وجود نوشته باشد، یک جفت کلید-مقدار به previousValues اضافه میکنیم که کلید currentNumber است و مقدار اندیس currentNumber در آرایه اصلی است.
نکته: از آنجا که previousValues یک هش است، زمانی که در آن به دنبال neededValue میگردیم لازم نیست حلقهای تعریف کنیم. کافی است ببینیم آیا مقدار معینی وجود دارد یا نه و این وضعیت زمانی اتفاق میافتد که کلید خاصی داشته باشیم که برابر با متغیر neededValue باشد. به دست آوردن مقادیر از هش بسیار سریعتر از تعریف حلقه تکرار روی آرایه است. پیچیدگی این عملیات O(n) است که در برابر O(n^2) بسیار کمتر است.
اینک مطمئنیم که این روش بسیار سریعتر است.
به این ترتیب به پایان این مقاله میرسیم. امیدواریم مطالعه این راهنما برای شما راهگشا بوده باشد. این نکته را نیز باید اشاره کنیم که یافتن راهحل مسائل همواره به آن سادگی و سرراستی که در مقالات میخوانیم نیست و نیازمند بررسی و آزمون و خطای موارد مختلف بوده است.
اگر این مطلب برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای JavaScript (جاوااسکریپت)
- مجموعه آموزشهای برنامهنویسی
- آموزش جاوا اسکریپت (JavaScript)
- ساخت وب اسکرپر (Web Scraper) با جاوا اسکریپت — راهنمای کاربردی
- آموزش جاوا اسکریپت — مجموعه مقالات جامع وبلاگ فرادرس
==