چگونه به صورت کارآمد یک آرایه را به صورت تصادفی در C# مرتب کنیم؟!

در این مقاله، روش‌‌های مختلف تصادفی کردن آرایه را با هم بررسی کردیم.

در ابتدا یک متد ایجاد کرده‌ایم که در ورودی یک عدد صحیح به عنوان طول آرایه دریافت می‌کند. و در بدنه ی متد یک آرایه از اعداد صحیح با ترتیب صعودی می‌سازد.

public static class ArrayFunctions
{
      public static int[] GetOrderedArray(int numberOfElements)
     { 
            var array = new int[numberOfElements];
             for (int i = 0; i < numberOfElements; i++)
             { 
                     array[i] = i;
             } 
              return array;
      }
}

رندم کردن آرایه با استفاده از LINQ

ابزار LINQ یکی از قدرتمندترین امکاناتی است که در اختیار ما در C# قرار دارد. این ابزار به ما روش‌های مختلفی برای کنترل داده‌ها را فراهم می‌کند.

معمولاً از آن برای پرس و جو یا فیلتر کردن مجموعه داده ها استفاده می کنیم، اما می توانیم از آن برای تصادفی سازی نیز استفاده کنیم. برای مرتب کردن داده‌ها در LINQ از متد OrderBy استفاده می‌کنیم. این متد داده‌ها را بر اساس کلید ورودی مرتب می‌کند.

رندم کردن به وسیله GUID

ما یک متد جدید RandomizeWithOrderByAndGuid ایجاد کرده‌ایم. این متد به طور مستقیم آرایه ورودی را با استفاده از Guid.NewGuid() مرتب می کند. در این شیوه Guid.NewGuid() هر بار یک GUID جدید و منحصر به فرد تولید می‌کند و باعث می‌شود که اعضای ارایه به صورت تصادفی چیده شوند.

public static int[] RandomizeWithOrderByAndGuid(int[] array) =>
‍           array.OrderBy(x => Guid.NewGuid()).ToArray();

رندم کردن آرایه با یک کلاس رندم

یک متد جدید دیگر به اسم RandomizeWithOrderByAndRandom ایجاد کردیم. در اینجا از متدNext از Random.Shared برای مرتب کردن آرایه استفاده کردیم. این متد هر بار بک عدد تصادفی تولید می‌کند و باعث می‌شود که آرایه به صورت تصادفی مرتب شود.

public static int[] RandomizeWithOrderByAndRandom(int[] array) =>
       array.OrderBy(x => Random.Shared.Next()).ToArray();.

رندم کردن ارایه درC# با استفاده از الگوریتم Fisher-Yates

public static int[] RandomizeWithFisherYates(int[] array)
{
         int count = array.Length;
         while (count > 1)
         { 
                  int i = Random.Shared.Next(count--);
                 (array[i], array[count])= (array[count], array[i]);
         }
          return array;
}

ما متد RandomizeWithFisherYates ایجاد می کنیم که یک آرایه صحیح را به عنوان ورودی می گیرد.

در داخل متد، متغیر count را با طول آرایه ورودی مقداردهی اولیه می کنیم. در هر تکرار حلقه while، یک عدد تصادفی تولید می شود و عنصر مربوط به ایندکس عدد تولید شده تصادفی در آرایه با عنصر اشاره شده توسط متغیرcount با استفاده ازTuple جابجا می شود. این کار تا زمانی ادامه پیدا می کند که count برابر 1 شود. در نهایت، آرایه تغییر یافته را برمی گردانیم.

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

نسخه دوم الگوریتم Fisher-Yates :

public static int[] RandomizeWithFisherYatesCopiedArray(int[] array)
{
          int count = array.Length;
          var arrayCopy = new int[count];
          Array.Copy(array, arrayCopy, count);
          while (count > 1)
          {
                   int i = Random.Shared.Next(count--);
                   (arrayCopy[i], arrayCopy[count]) = (arrayCopy[count], arrayCopy[i]);
           }
            return arrayCopy;
}

این روش تقریباً شبیه به متد اصلی RandomizeWithFisherYates است با این استثنا که از روش Array.Copy برای کپی آرایه ورودی استفاده می کنیم. در بخش دیگری از متد، با متغیرarrayCopy کار می کنیم و پس از پایان کار آن را برمی گردانیم.

تست رندم کردن آرایه

بعد از داشتن روش های مختلف تصادفی سازی سعی می‌کنیم که روش ها را تست کنیم.

public class ArrayFunctionsTests
{
        private readonly int[] _array;
        private const int ARRAY_SIZE = 1000;
        public ArrayFunctionsTests()
         {
                 _array = ArrayFunctions.GetOrderedArray(ARRAY_SIZE);
         }
}

در داخل متد تست، از متدRandomizeWithOrderByAndGuid کلاسArrayFunctions برای تصادفی سازی متغیر_array استفاده می کنیم.

نتیجه را در متغیر randomizedArray ذخیره می کنیم. سپس با استفاده از کتابخانه FluentAssertions، ادعا می کنیم که متغیر randomizedArray نباید خالی باشد، نباید به صورت صعودی و نیز به صورت نزولی مرتب شود.

به این روش، اطمینان حاصل می کنیم که متدRandomizeWithOrderByAndGuid() با موفقیت یک ترتیب متفاوت از آرایه اصلی تولید می کند.

[Fact]
public void WhenRandomizeWithOrderByAndGuidIsInvoked_ThenArrayIsRandomized()
{
            // Act
            var randomizedArray = ArrayFunctions.RandomizeWithOrderByAndGuid(_array);
            // Assert
            randomizedArray.Should()
                       .NotBeNullOrEmpty()
                       .And.NotBeInAscendingOrder()
                      .And.NotBeInDescendingOrder();
}

برای تست سه روش دیگری که در این مقاله ایجاد کرده ایم، می توانیم با استفاده از همین روش عمل کنیم .

ملاحظات عملکردی هنگام تصادفی سازی یک آرایه در C#

برای تشخیص اینکه کدام روش پرفورمنس بهتری دارد از BenchmarkDotNet برای اندازه گیری عملکرد و تخصیص حافظه استفاده کنیم:

بنچمارکی که ما استفاده می کنیم، زمان اجرای میانگین، خطا، انحراف استاندارد و تخصیص حافظه را برای هر روش اندازه گیری می کند.

روش RandomizeWithFisherYates تا حد زیادی بهترین عملکرد را دارد و با زمان اجرای حدود 1،400 میکروثانیه، در رتبه اول قرار دارد و تقریباً هیچ تخصیص حافظه ای ندارد.

نسخه اصلاح شده الگوریتم Fisher-Yates ، RandomizeWithFisherYatesCopiedArray) در رتبه دوم قرار دارد و با 1،500 میکروثانیه، عملکرد بسیار خوبی دارد. به دلیل کپی کردن آرایه ورودی، تخصیص حافظه بیشتری نسبت به نسخه اصلی دارد.

سپس، روش RandomizeWithOrderByAndRandom با زمان اجرای حدود 17،000 میکروثانیه و تخصیص حافظه قابل توجه بالاتر نسبت به دو روش قبل - در رتبه سوم قرار دارد.

و در نهایت، RandomizeWithOrderByAndGuid با زمان اجرای حدود 26،000 میکروثانیه. در میان چهار روش، در رتبه آخر قرار دارد و همچنین بالاترین تخصیص حافظه را دارد.

مقاله اصلی را میتوانید در اینجا ببینید.