c# - shafayet - হাসানের রাফ খাতা




.NET এর সাথে অ্যারে র্যান্ডমাইজ করার সেরা উপায় (12)

.NET দিয়ে স্ট্রিংগুলির অ্যারে র্যান্ডম করার সেরা উপায় কী? আমার অ্যারেরটিতে প্রায় 500 স্ট্রিং রয়েছে এবং আমি একই স্ট্রিংগুলির সাথে একটি নতুন Array তৈরি করতে চাই তবে একটি এলোমেলোভাবে।

আপনার উত্তর একটি সি # উদাহরণ অন্তর্ভুক্ত করুন।


Jacco, আপনার সমাধান একটি কাস্টম IComparer হচ্ছে নিরাপদ নয়। সাজানোর রুটিন সঠিকভাবে কাজ করার জন্য বিভিন্ন প্রয়োজনীয়তা অনুসারে তুলনাকারী তুলনা প্রয়োজন। তাদের মধ্যে প্রথম সামঞ্জস্য হয়। যদি তুলনাকারী একই জিনিসের জোড়া বলা হয় তবে এটি অবশ্যই একই ফলাফলটি ফেরত দিতে হবে। (তুলনামূলক সংক্রামক হতে হবে)।

এই প্রয়োজনীয়তাগুলি পূরণ করতে ব্যর্থতা অনির্দিষ্ট লুপের সম্ভাবনা সহ শর্টিং রুটিনে কোনও সমস্যা সৃষ্টি করতে পারে।

প্রতিটি এন্ট্রির সাথে একটি র্যান্ডম সংখ্যাসূচক মান যুক্ত করার সমাধানগুলি এবং তারপরে সেই মান অনুসারে সাজানোর সমাধানগুলি সম্পর্কে, এই আউটপুটের মধ্যে একটি স্বতঃস্ফূর্ত পক্ষপাতের কারণ হয় কারণ কোনও সময় দুটি এন্ট্রি একই সংখ্যাসূচক মান নির্ধারণ করে, আউটপুটের র্যান্ডমনেসটি আপোস করা হবে। ("স্থিতিশীল" সাজানোর রুটিনে, যেটি প্রথম ইনপুটের মধ্যে প্রথম, আউটপুটের মধ্যে প্রথম হতে হবে। অ্যারে .ort স্থিতিশীল হতে পারে না, তবে কিক্সসোর্ট অ্যালগরিদম দ্বারা বিভাজিত বিভাজনের ভিত্তিতে একটি পক্ষপাত রয়েছে)।

আপনি প্রয়োজন কি এলোমেলোতা স্তর সম্পর্কে কিছু চিন্তা করতে হবে। যদি আপনি কোনও পকার সাইট চালাচ্ছেন যেখানে কোনও নির্ধারিত আক্রমণকারীর বিরুদ্ধে সুরক্ষার জন্য আপনার ক্রমবর্ধমান ক্র্রিপ্টোগ্রাফিক স্তরের প্রয়োজন হয় তবে আপনার কাছে এমন একটি ব্যক্তির কাছ থেকে খুব আলাদা প্রয়োজনীয়তা রয়েছে যা কেবল একটি গানের প্লেলিস্ট র্যান্ডমাইজ করতে চায়।

গানের তালিকা শাফিংয়ের জন্য, বীজযুক্ত PRNG ব্যবহার করে কোনও সমস্যা নেই (সিস্টেম সিস্টেম। র্যান্ডম)। একটি জুজু সাইটের জন্য, এটি এমনকি একটি বিকল্পও নয় এবং স্ট্যাকওভারফ্লোতে আপনার জন্য যে কেউ কাজ করছে তার চেয়ে আপনার সমস্যাটির বিষয়ে অনেক চিন্তা করা দরকার। (একটি ক্রিপ্টোগ্রাফিক RNG ব্যবহার করে শুধুমাত্র শুরু হয়, আপনাকে নিশ্চিত করতে হবে যে আপনার অ্যালগরিদম একটি পক্ষপাত পেশ করে না, আপনার কাছে এনট্রোপির পর্যাপ্ত উত্স রয়েছে এবং আপনি কোন অভ্যন্তরীণ রাষ্ট্রকে প্রকাশ করবেন না যা পরবর্তী এলোমেলোতার সাথে আপোস করবে)।


অ্যারেকে র্যান্ডমাইজ করা আপনার পক্ষে ঘন ঘন স্ট্রিংগুলির চারপাশে স্থানান্তরিত করার মতো গভীর। কেন এলোমেলোভাবে অ্যারে থেকে পড়া না? সবচেয়ে খারাপ ক্ষেত্রে আপনি একটি getNextString () সহ একটি রেপার ক্লাস তৈরি করতে পারেন। যদি আপনি সত্যিই একটি র্যান্ডম অ্যারে তৈরি করতে চান তাহলে আপনি ভালো কিছু করতে পারে

for i = 0 -> i= array.length * 5
   swap two strings in random places

* 5 ইচ্ছাকৃতভাবে হয়।


আপনি জটিল অ্যালগরিদম প্রয়োজন হয় না।

শুধু একটি সহজ লাইন:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

উল্লেখ্য, প্রথম স্থানে List ব্যবহার না করলে আমাদের Array প্রথমে List রূপান্তর করতে হবে।

এছাড়াও, মনে রাখবেন যে এটি খুব বড় অ্যারের জন্য কার্যকর নয়! অন্যথায় এটি পরিষ্কার এবং সহজ।


আপনি ম্যাট হাওয়েলস থেকে একটি এক্সটেনশন পদ্ধতিও তৈরি করতে পারেন। উদাহরণ।

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

তারপর আপনি শুধু এটি ব্যবহার করতে পারেন:

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

এই অ্যালগরিদম সহজ কিন্তু দক্ষ নয়, হে (এন 2 )। অ্যালগরিদম দ্বারা "অর্ডার" সমস্ত সাধারণত O (N লগ N) হয়। এটি সম্ভবত হাজার হাজার উপাদানগুলির নীচে একটি পার্থক্য তৈরি করে না তবে এটি বড় তালিকাগুলির জন্য হবে।

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

কারণ এটি O (N 2 ) সূক্ষ্ম: তালিকা। List.RemoveAt() একটি O (N) অপারেশন না হওয়া পর্যন্ত আপনি শেষ থেকে অপসারণ করতে পারেন।


এই কোড একটি অ্যারে সংখ্যা shuffles।

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

একই দৈর্ঘ্যের এলোমেলো ভাসা বা ইট এর একটি অ্যারে তৈরি করুন। যে অ্যারে সাজান, এবং আপনার লক্ষ্য অ্যারে অনুরূপ swaps না।

এই একটি সত্যিকারের স্বাধীন সাজানোর উত্পাদন।


এখানে OLINQ ব্যবহার করে একটি সহজ উপায়:

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

ঠিক আছে, এটি আমার পক্ষ থেকে স্পষ্টভাবে একটি দ্বিধা (ক্ষমাপ্রার্থী ...), তবে আমি প্রায়ই বেশ সাধারণ এবং ক্রিপ্টোগ্রাফিকভাবে দৃঢ় পদ্ধতি ব্যবহার করি।

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

শাফেল () কোনও অণুরূপে একটি এক্সটেনশান হয় তাই বলে, একটি তালিকাতে র্যান্ডম ক্রম থেকে 0 থেকে 1000 পর্যন্ত সংখ্যাগুলি সম্পন্ন করা যেতে পারে

Enumerable.Range(0,1000).Shuffle().ToList()

সাজানোর মানটি যখন আসে তখন এই পদ্ধতিটি কোনও চমক দেয় না, কারন সাজানোর মানটি ক্রমানুসারে উপাদানটির প্রতি একবারে একবার উত্পন্ন হয় এবং মনে হয়।


নিম্নলিখিত বাস্তবায়ন Fisher-Yates অ্যালগরিদম ব্যবহার করে। এটি O (n) সময় এবং শাফেলগুলিতে সঞ্চালিত হয়, তাই 'র্যান্ডম অনুসারে সাজান' প্রযুক্তির চেয়ে ভাল সম্পাদন করা হয়, যদিও এটি কোডের আরো লাইন। কিছু তুলনামূলক কর্মক্ষমতা পরিমাপের জন্য here দেখুন। আমি System.Random ব্যবহার করেছি, যা অ-ক্রিপ্টোগ্রাফিক উদ্দেশ্যের জন্য ভাল। *

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

ব্যবহার:

var array = new int[] {1, 2, 3, 4};
new Random().Shuffle(array);

* দীর্ঘতর অ্যারেগুলির জন্য, (অত্যন্ত বড়) ক্রমানুসারে সম্ভাব্য সম্ভাব্য সংখ্যাগুলি যথেষ্ট পরিমাণে এনট্রপি তৈরি করতে প্রতিটি সোয়াপের জন্য অনেক পুনরাবৃত্তি মাধ্যমে একটি ছদ্ম-র্যান্ডম সংখ্যা জেনারেটর (PRNG) চালানোর প্রয়োজন হবে। একটি 500-উপাদান অ্যারের জন্য শুধুমাত্র 500 খুব ছোট ভগ্নাংশ! একটি PRNG ব্যবহার করে permutations সম্ভব হবে। তবুও, ফিশার-ইয়েটস অ্যালগরিদমটি নিরপেক্ষ এবং অতএব শাফেলটি আপনার দ্বারা ব্যবহৃত RNG হিসাবে ভাল হবে।


private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();




random