از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
به هم ریختن آرایه ها در جاوا اسکریپت یکی از بسیاری از ویژگی هایی که جاوا اسکریپت ارائه می دهد، امکان کار آسان با آرایه ها است. آرایه نوع خاصی از شی است که برای ذخیره چندین مقدار در یک متغیر استفاده می شود و در مورد جاوا اسکریپت نیازی نیست که این مقادیر یکسان باشند…
سرفصلهای مطلب
معرفی
یکی از بسیاری از ویژگی هایی که جاوا اسکریپت ارائه می دهد، امکان کار آسان با آرایه ها است. آرایه نوع خاصی از شی است که برای ذخیره چندین مقدار در یک متغیر استفاده می شود و در مورد جاوا اسکریپت نیازی نیست که این مقادیر از یک نوع باشند. گاهی اوقات، ممکن است نیاز داشته باشید که ترتیب عناصر در یک آرایه را به صورت تصادفی تنظیم کنید.
این مقاله شما را از طریق روش های مختلف به هم زدن آرایه ها در جاوا اسکریپت راهنمایی می کند.
آرایه ها در جاوا اسکریپت
قبل از اینکه به روش های مخلوط کردن بپردازیم، ابتدا بیایید بفهمیم که آرایه در جاوا اسکریپت چیست. آرایه یک ساختار داده ای است که می تواند چندین مقدار را در یک متغیر ذخیره کند. هر مقدار (که به عنوان عنصر نیز شناخته می شود) در یک آرایه دارای یک موقعیت عددی است که به عنوان شاخص آن شناخته می شود که از 0 شروع می شود.
در اینجا مثالی از یک آرایه ساده جاوا اسکریپت آورده شده است:
let fruits = ('Apple', 'Banana', 'Cherry', 'Date', 'Elderberry');
console.log(fruits(0)); // Output: 'Apple'
در این آرایه، ‘Apple’ در شاخص 0، ‘Banana’ در شاخص 1 قرار دارد و به همین ترتیب روی. با مراجعه به شماره فهرست می توانید به عناصر یک آرایه دسترسی داشته باشید.
توجه داشته باشید: در جاوا اسکریپت، آرایه ها پویا هستند، به این معنی که می توانند اندازه آنها را در زمان اجرا تغییر دهند، و می توانند حاوی عناصری از هر نوع باشند – اعداد، رشته ها، اشیاء یا حتی آرایه های دیگر.
آرایه‌ها در جاوا اسکریپت دارای مجموعه‌ای از روش‌های داخلی هستند که به شما امکان می‌دهند آرایه و عناصر آن را دستکاری کنید. برخی از این روش ها عبارتند از push() برای افزودن عناصر، pop() برای حذف عناصر، sort() برای مرتب کردن عناصر، و غیره روی.
با این حال، هیچ روش داخلی برای به هم زدن عناصر یک آرایه وجود ندارد. اینجاست که تکنیک‌هایی که در بخش‌های بعدی به آنها خواهیم پرداخت.
چرا یک آرایه را به هم بزنیم؟
به هم زدن یک آرایه عملیاتی است که به طور تصادفی عناصر یک آرایه را مرتب می کند. این به ویژه در سناریوهای مختلف مفید است.
به عنوان مثال، اگر در حال ساخت یک بازی با ورق هستید، باید دسته کارت‌های ذخیره شده در یک آرایه را قبل از شروع بازی به هم بزنید تا از عدالت اطمینان حاصل کنید. در یادگیری ماشینی، معمول است که داده‌های ورودی را قبل از تقسیم به مجموعه‌های آموزشی و آزمایشی به هم می‌زنیم تا اطمینان حاصل شود که مدل تحت تأثیر هیچ نظم موجود در داده‌ها قرار نمی‌گیرد.
از مخلوط کردن می‌توان برای تولید یک نمونه تصادفی از مجموعه داده‌های بزرگ‌تر یا ایجاد نمایشی جذاب‌تر از آیتم‌ها استفاده کرد. روی یک وب page. در جاوا اسکریپت، هیچ تابع داخلی برای به هم زدن یک آرایه وجود ندارد، اما چندین الگوریتم شناخته شده وجود دارد که می توانند به راحتی پیاده سازی شوند، که ما نگاهی به آنها خواهیم داشت.
شافل فیشر-یتس (کنوت).
Shuffle Fisher-Yates که با نام Knuth Shuffle نیز شناخته می شود، یک روش ساده و کارآمد برای به هم زدن یک آرایه است. با تکرار در میان آرایه از آخرین عنصر به اولین عنصر، تعویض هر عنصر با یک عنصر با شاخص تصادفی کمتر یا مساوی با شاخص فعلی آن، کار می کند.
در اینجا پیاده سازی جاوا اسکریپت Fisher-Yates Shuffle است:
function fisherYatesShuffle(array) {
let currentIndex = array.length;
while (currentIndex !== 0) {
// Pick a remaining element
let randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
// And swap it with the current element
let temporaryValue = array(currentIndex);
array(currentIndex) = array(randomIndex);
array(randomIndex) = temporaryValue;
}
return array;
}
let arr = (1, 2, 3, 4, 5);
console.log(fisherYatesShuffle(arr)); // ( 3, 1, 5, 4, 2 )
وقتی این کد را اجرا می کنید، اجرا می شود print نسخه به هم ریخته آرایه (1, 2, 3, 4, 5). هر بار که عملکرد را اجرا می کنید، خروجی متفاوت خواهد بود، همانطور که باید با یک الگوریتم زدن خوب باشد.
توجه داشته باشید: Fisher-Yates Shuffle یک الگوریتم در محل است، به این معنی که آرایه اصلی را بدون ایجاد آرایه جدید به هم می‌ریزد. این آن را به روشی بسیار کارآمد برای به هم زدن یک آرایه تبدیل می کند.
Fisher-Yates Shuffle دارای پیچیدگی زمانی O(n) است که آن را به روشی بسیار کارآمد برای به هم زدن آرایه های بزرگ تبدیل می کند. این به این دلیل است که فقط باید یک نفر از آرایه عبور کند، و هر عنصر را با عنصری که به طور تصادفی انتخاب شده است جایگزین کند که هنوز مخلوط نشده است.
دورستنفلد شافل
مخلوط دورستنفلد یک نسخه بهینه سازی شده کامپیوتری از مخلوط فیشر-یتس است که توسط ریچارد دورستنفلد در سال 1964 توسعه یافت. این الگوریتم به گونه ای طراحی شده است که کارآمدتر باشد و با انتخاب یک عنصر تصادفی برای هر عنصر آرایه اصلی کار می کند و سپس آن را از فهرست حذف می کند. قرعه کشی بعدی
بیایید ببینیم چگونه می توانیم این را در جاوا اسکریپت پیاده سازی کنیم:
function durstenfeldShuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
(array(i), array(j)) = (array(j), array(i));
}
return array;
}
let arr = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
console.log(durstenfeldShuffle(arr));
هنگامی که این اسکریپت را اجرا می کنید، خواهید دید که عناصر آرایه به طور تصادفی به هم ریخته شده اند. باز هم، هر اجرا احتمالاً نتیجه متفاوتی خواهد داشت.
توجه داشته باشید: مخلوط دورستنفلد کارآمدتر از مخلوط فیشر-یتس در نظر گرفته می شود زیرا از وارد کردن عناصر انتخاب شده در آرایه جدید جلوگیری می کند، که می تواند از نظر محاسباتی گران باشد.
تبدیل شوارتزیان
تبدیل شوارتزی که به نام راندال ال. شوارتز نامگذاری شده است، یک تکنیک مرتب‌سازی است که در برنامه‌نویسی کامپیوتری استفاده می‌شود. این دقیقاً یک الگوریتم مخلوط کردن نیست، اما می توان آن را برای این منظور تطبیق داد. ایده این است که آرایه را به گونه‌ای تبدیل کنیم که مرتب‌سازی کارآمدتر شود، سپس تبدیل را لغو کنیم.
در زمینه به هم زدن یک آرایه، می توانیم از تبدیل شوارتزی برای اختصاص یک عدد تصادفی به هر عنصر آرایه استفاده کنیم، آرایه را بر اساس مرتب کنیم. روی این اعداد، و سپس حذف اعداد، ترک یک آرایه به هم ریخته.
در اینجا پیاده سازی جاوا اسکریپت آمده است:
function schwartzianShuffle(array) {
return array
.map((a) => (Math.random(), a)) // Assign a random number to each element
.sort((a, b) => a(0) - b(0)) // Sort by the random numbers
.map((a) => a(1)); // Remove the random numbers
}
let arr = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
console.log(schwartzianShuffle(arr));
هنگامی که این اسکریپت را اجرا می کنید، خواهید دید که عناصر آرایه به طور تصادفی به هم ریخته شده اند. همانند الگوریتم های قبلی، هر اجرا احتمالاً نتیجه متفاوتی را به همراه خواهد داشت.
در حالی که تبدیل شوارتزی یک تکنیک هوشمندانه است، ممکن است کارآمدترین روش برای به هم زدن آرایه های بزرگ در جاوا اسکریپت نباشد. با این حال، نشان می دهد که چگونه می توانید از تکنیک های دیگر برای دستیابی به نتیجه دلخواه استفاده کنید.
مخلوط کردن آرایه های چند بعدی
وقتی صحبت از به هم زدن آرایه های چند بعدی می شود، process کمی پیچیده تر است یک آرایه چند بعدی اساساً فقط آرایه ای از آرایه ها است. اگر بخواهیم به سادگی یک الگوریتم shuffle را روی یک آرایه چند بعدی اعمال کنیم، در نهایت آرایه‌های فرعی را به هم می‌زنیم، اما نه تک تک عناصر درون آن آرایه‌های فرعی.
یکی از راه‌های به هم زدن درست یک آرایه چند بعدی، صاف کردن آرایه، به هم زدن آن و سپس بازسازی آرایه چند بعدی است. در اینجا روش انجام این کار آمده است:
function shuffleMultiDimensionalArray(array) {
// Flatten the array
let flattened = ().concat(...array);
// Shuffle the flattened array
for (let i = flattened.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
(flattened(i), flattened(j)) = (flattened(j), flattened(i));
}
// Rebuild the multidimensional array
let result = ();
while(flattened.length) result.push(flattened.splice(0, array(0).length));
return result;
}
let array = ((1, 2, 3), (4, 5, 6), (7, 8, 9));
console.log(shuffleMultiDimensionalArray(array));
این یک آرایه چند بعدی به هم ریخته را خروجی می دهد، مانند:
((3, 1, 2), (6, 5, 4), (8, 9, 7))
توجه داشته باشید: این تابع فرض می کند که تمام آرایه های فرعی در آرایه چند بعدی دارای طول یکسانی هستند. اگر طول آرایه های فرعی متفاوت باشد، این تابع به درستی کار نخواهد کرد.
با استفاده از Lodash
اگر استفاده می کنید لوداش، یک کتابخانه ابزار محبوب جاوا اسکریپت است که می توانید آرایه ها را با هم مخلوط کنید _.shuffle() تابع. این تابع الگوریتم shuffle Fisher-Yates را پیاده سازی می کند و با آرایه های تک بعدی و چند بعدی کار می کند.
در اینجا روش تغییر یک آرایه با استفاده از Lodash آورده شده است:
const _ = require('lodash');
let array = (1, 2, 3, 4, 5, 6, 7, 8, 9);
console.log(_.shuffle(array));
با این کار یک آرایه به هم ریخته مانند:
(3, 2, 9, 1, 6, 8, 7, 4, 5)
و در اینجا چگونه می توانید یک آرایه چند بعدی را به هم بزنید:
const _ = require('lodash');
let array = ((1, 2, 3), (4, 5, 6), (7, 8, 9));
console.log(_.shuffle(_.flatten(array)));
با این کار یک آرایه به هم ریخته مانند:
(3, 2, 1, 6, 5, 4, 9, 8, 7)
اینجا _.flatten() تابع برای صاف کردن آرایه چند بعدی قبل از به هم زدن آن استفاده می شود. با این حال، آرایه چند بعدی را پس از درهم ریختن بازسازی نمی کند. اگر نیاز به حفظ ساختار چند بعدی دارید، باید خودتان آن را بازسازی کنید.
ملاحظات عملکرد
وقتی صحبت از به هم ریختن آرایه ها در جاوا اسکریپت می شود، عملکرد می تواند عامل مهمی باشد که باید در نظر گرفته شود، به خصوص وقتی که با آرایه های بزرگ سروکار داریم.
شافل Fisher-Yates (Knuth) و نسخه بهینه شده آن، shuffle Durstenfeld، به دلیل پیچیدگی زمانی O(n) کارآمد خود شناخته شده اند. این به این معنی است که زمان لازم برای زدن آرایه به صورت خطی با اندازه آرایه رشد می کند که بسیار خوب است.
تبدیل شوارتزی، روی از سوی دیگر، به اندازه کافی کارآمد نیست. این روش شامل یک عملیات مرتب‌سازی است که پیچیدگی زمانی O(n log n) دارد. این باعث می‌شود که برای آرایه‌های بزرگ‌تر نسبت به Fisher-Yates و Durstenfeld کندتر باشد.
با این حال، هنگامی که با آرایه های کوچکتر سروکار داریم، تفاوت عملکرد بین این روش ها ناچیز است. سپس انتخاب روش بستگی دارد روی عوامل دیگری مانند خوانایی کد و سادگی.
توجه داشته باشید: همیشه تعادل بین عملکرد و خوانایی کد را در نظر بگیرید. یک روش کمی کندتر ممکن است ارزش آن را داشته باشد اگر درک و نگهداری کد شما را آسان‌تر کند.
استفاده از کتابخانه هایی مانند Lodash نیز می تواند پیامدهای عملکردی داشته باشد. در حالی که این کتابخانه‌ها بهینه شده‌اند و معمولاً عملکرد خوبی دارند، یک لایه انتزاعی اضافه می‌کنند که می‌تواند سرعت کار را در مقایسه با روش‌های بومی جاوا اسکریپت کاهش دهد.
در اینجا مقایسه ای از زمان صرف شده برای به هم زدن یک آرایه از 1 میلیون عدد با استفاده از روش های مختلف است:
let arr = Array.from({length: 1000000}, (_, i) => i + 1);
console.time('Fisher-Yates Shuffle');
fisherYatesShuffle(arr);
console.timeEnd('Fisher-Yates Shuffle');
console.time('Durstenfeld Shuffle');
durstenfeldShuffle(arr);
console.timeEnd('Durstenfeld Shuffle');
console.time('Schwartzian Transform');
schwartzianShuffle(arr);
console.timeEnd('Schwartzian Transform');
console.time('Lodash Shuffle');
_.shuffle(arr);
console.timeEnd('Lodash Shuffle');
$ node shuffle.js
Fisher-Yates Shuffle: 19.95ms
Durstenfeld Shuffle: 18.118ms
Schwartzian Transform: 898.175ms
Lodash Shuffle: 21.308ms
زمان دقیق بسته به آن متفاوت خواهد بود روی ماشین شما و حجم کاری فعلی، اما باید ببینید که شافل های فیشر-یتس و دورستنفلد به طور قابل توجهی سریعتر از تبدیل شوارتزیان و کمی سریعتر از شافل لوداش هستند.
با توجه به اینکه سریعتر از Lodash است، این ممکن است به دلیل استفاده از کتابخانه ای مانند Lodash باشد.
نتیجه
به هم ریختن آرایه ها در جاوا اسکریپت یک نیاز رایج است که می توان به روش های مختلفی به آن دست یافت. در حالی که شافل Fisher-Yates (Knuth) و Shuffle Durstenfeld کارآمد هستند و به طور گسترده مورد استفاده قرار می گیرند، روش های دیگری مانند تبدیل شوارتزی یا استفاده از کتابخانه هایی مانند Lodash ممکن است بسته به اینکه مناسب تر باشند. روی الزامات و محدودیت های خاص پروژه شما.
به یاد داشته باشید که هنگام انتخاب یک روش، به ویژه هنگامی که با آرایه های بزرگ سروکار دارید، مفاهیم عملکرد را در نظر بگیرید. با این حال، فراموش نکنید که خوانایی کد و سادگی نیز فاکتورهای مهمی هستند که باید در نظر گرفته شوند. بهترین راه حل معمولاً راه حل هایی است که بین کارایی، خوانایی و سادگی تعادل دارند.
(برچسب‌ها برای ترجمه)# جاوا اسکریپت
منتشر شده در 1402-12-31 06:08:08
