c# यादृच्छिक संख्या बहुत यादृच्छिक प्रतीत नहीं होती है




random base32 (3)

मैं यादृच्छिक बेस 32 संख्याएं उत्पन्न करने की कोशिश कर रहा हूं जो 6 वर्ण या उससे कम हैं। यह लगभग 1 अरब विभिन्न संयोजन देना चाहिए।

मैंने इन "यादृच्छिक" संख्याओं को उत्पन्न करने के लिए एक प्रोग्राम बनाया है। हालांकि, ऐसा प्रतीत होता है कि यह औसतन 40,000 पीढ़ियों पर डुप्लिकेट उत्पन्न करता है।

इन "यादृच्छिक" संख्याएं इतनी बार डुप्लिकेट क्यों होती हैं जब एक अरब से अधिक भिन्न संयोजन होते हैं?

मेरा कोड यहाँ है:

static void Main(string[] args)
{
    int seed = Environment.TickCount;
    Random r = new Random(seed);

    Dictionary<int, int> resultDictionary = new Dictionary<int, int>();
    for (int x = 1; x <= 1000; x++)
    {
        Dictionary<string, int> dictionary = new Dictionary<string, int>();
        try
        {
            while (true)
            {
                int rand = r.Next(0, 1073741823);
                CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                string encodedRand = encoding.Encode((ulong)rand, false);
                dictionary.Add(encodedRand, rand);
            }
        }
        catch (Exception)
        {
        }
        Console.WriteLine(string.Format("{0} - {1}", x, dictionary.Count));
        resultDictionary.Add(x, dictionary.Count);
        x++;
    }

    Console.WriteLine();
    Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
    Console.ReadLine();
}

यह en.wikipedia.org/wiki/Birthday_problem समान है। n लोगों के एक समूह को देखते हुए, संभावना क्या है कि दो समान जन्मदिन 1 साझा करते हैं? यह आपके विचार से ज्यादा है।

आपके मामले में, 0 और 1,073,741,823 एन बार के बीच यादृच्छिक रूप से कोई संख्या चुनने वाली बाधाएं आपको डुप्लिकेट देगी?

उपरोक्त लिंक से एक अनुमान 1-exp(-(n*n)/(2*d)) । यदि n=40,000 जो 52.5% संभावना के बराबर है जो डुप्लिकेट चुना जाता है, तो औसत पर 40,000 चुनने के बाद डुप्लीकेट देखना उचित लगता है।

1 यह मानते हुए कि जन्मदिन समान रूप से सार्वभौमिक रूप से वितरित किए जाते हैं, जो वास्तविकता में नहीं है लेकिन "पर्याप्त करीब" है और गणित को आसान बनाता है


फ्रेमवर्क में शामिल यादृच्छिक संख्या जेनरेटर यादृच्छिक संख्या वितरण की गारंटी के बिना छद्म-यादृच्छिक है। यदि आप वितरण पैटर्न के बारे में चिंतित हैं, तो इस आलेख पर विचार करें: http://www.codeproject.com/Articles/15102/NET-random-number-generators-and-distributions यादृच्छिक- संख्या- जनरेटर- और- वितरण

फिर भी, मेरे आंकड़े प्रोफेसर (एक नहीं) कहते थे, "एक छोटा झूठ है, एक बड़ा झूठ है, और सांख्यिकी है"।

सबसे पहले पूर्ण कोड, इसलिए लोगों को परीक्षण करने के लिए कक्षा कार्यान्वयन की तलाश में इंटरनेट को खराब करने की आवश्यकता नहीं है:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = RandomProvider.GetThreadRandom();

            Dictionary<int, int> resultDictionary = new Dictionary<int, int>();
            for (int x = 1; x <= 1000; x++)
            {
                Dictionary<string, int> dictionary = new Dictionary<string, int>();
                try
                {
                    while (true)
                    {
                        int rand = r.Next(0, 1073741823);
                        CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                        string encodedRand = encoding.Encode((ulong)rand, false);
                        dictionary.Add(encodedRand, rand);
                    }
                }
                catch (Exception)
                {
                }
                Console.WriteLine("{0} - {1}", x, dictionary.Count);
                resultDictionary.Add(x, dictionary.Count);
                x++;
            }

            Console.WriteLine();
            Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
            Console.WriteLine("Minimum Number Before Duplicate: " + resultDictionary.Min(x => x.Value));
            Console.WriteLine("Maximum Number Before Duplicate: " + resultDictionary.Max(x => x.Value));
            Console.WriteLine(" Median Number Before Duplicate: " + resultDictionary.Select(x=>x.Value).Median());
            Console.ReadLine();
        }


    }

    public static class Extensions
    {
        public static double Median<T>(this IEnumerable<T> list)
        {
            List<double> orderedList = list.Select(s=>Convert.ToDouble(s))
                .OrderBy(numbers => numbers)
                .ToList();

            int listSize = orderedList.Count;
            double result;

            if (listSize % 2 == 0) // even
            {
                int midIndex = listSize / 2;
                result = ((orderedList.ElementAt(midIndex - 1) +
                           orderedList.ElementAt(midIndex)) / 2);
            }
            else // odd
            {
                double element = (double)listSize / 2;
                element = Math.Round(element, MidpointRounding.AwayFromZero);

                result = orderedList.ElementAt((int)(element - 1));
            }

            return result;
        } 
    }


    public static class RandomProvider
    {
        private static int seed = Environment.TickCount;

        private static ThreadLocal<Random> randomWrapper = new ThreadLocal<Random>(() =>
            new Random(Interlocked.Increment(ref seed))
            );

        public static Random GetThreadRandom()
        {
            return randomWrapper.Value;
        }
    }

    public class CrockfordBase32Encoding
    {
        const int Base = 32;
        const int CheckDigitBase = 37;

        static readonly IDictionary<int, char> valueEncodings;
        static readonly IDictionary<int, char> checkDigitEncodings;
        static readonly IDictionary<char, int> valueDecodings;
        static readonly IDictionary<char, int> checkDigitDecodings;
        static CrockfordBase32Encoding()
        {
            var symbols = new SymbolDefinitions();
            valueEncodings = symbols.ValueEncodings;
            checkDigitEncodings = symbols.CheckDigitEncodings;
            valueDecodings = symbols.ValueDecodings;
            checkDigitDecodings = symbols.CheckDigitDecodings;
        }

        public string Encode(ulong input, bool includeCheckDigit)
        {
            var chunks = SplitInto5BitChunks(input);
            var characters = chunks.Select(chunk => valueEncodings[chunk]);

            if (includeCheckDigit)
            {
                var checkValue = (int)(input % CheckDigitBase);
                characters = characters.Concat(new[] { checkDigitEncodings[checkValue] });
            }

            return new string(characters.ToArray());
        }

        internal static IEnumerable<byte> SplitInto5BitChunks(ulong input)
        {
            const int bitsPerChunk = 5;
            const int shift = (sizeof(ulong) * 8) - bitsPerChunk;
            var chunks = new List<byte>();
            do
            {
                var lastChunk = input << shift >> shift;
                chunks.Insert(0, (byte)lastChunk);
                input = input >> bitsPerChunk;
            } while (input > 0);
            return chunks;
        }

        public ulong? Decode(string encodedString, bool treatLastCharacterAsCheckDigit)
        {
            if (encodedString == null)
                throw new ArgumentNullException("encodedString");

            if (encodedString.Length == 0)
                return null;

            IEnumerable<char> charactersInReverse = encodedString.Reverse().ToArray();

            int? expectedCheckValue = null;
            if (treatLastCharacterAsCheckDigit)
            {
                var checkDigit = charactersInReverse.First();
                if (!checkDigitDecodings.ContainsKey(checkDigit)) return null;
                expectedCheckValue = checkDigitDecodings[checkDigit];

                charactersInReverse = charactersInReverse.Skip(1);
            }

            ulong number = 0;
            ulong currentBase = 1;
            foreach (var character in charactersInReverse)
            {
                if (!valueDecodings.ContainsKey(character)) return null;

                var value = valueDecodings[character];
                number += (ulong)value * currentBase;

                currentBase *= Base;
            }

            if (expectedCheckValue.HasValue &&
                (int)(number % CheckDigitBase) != expectedCheckValue)
                return null;

            return number;
        }
    }

    internal class SymbolDefinitions : List<SymbolDefinition>
    {
        readonly List<SymbolDefinition> extraCheckDigits = new List<SymbolDefinition>();

        public SymbolDefinitions()
        {
            AddRange(new[]
            {
                new SymbolDefinition { Value = 0, EncodeSymbol = '0', DecodeSymbols = new[] { '0', 'O', 'o' } },
                new SymbolDefinition { Value = 1, EncodeSymbol = '1', DecodeSymbols = new[] { '1', 'I', 'i', 'L', 'l' } },
                new SymbolDefinition { Value = 2, EncodeSymbol = '2', DecodeSymbols = new[] { '2' } },
                new SymbolDefinition { Value = 3, EncodeSymbol = '3', DecodeSymbols = new[] { '3' } },
                new SymbolDefinition { Value = 4, EncodeSymbol = '4', DecodeSymbols = new[] { '4' } },
                new SymbolDefinition { Value = 5, EncodeSymbol = '5', DecodeSymbols = new[] { '5' } },
                new SymbolDefinition { Value = 6, EncodeSymbol = '6', DecodeSymbols = new[] { '6' } },
                new SymbolDefinition { Value = 7, EncodeSymbol = '7', DecodeSymbols = new[] { '7' } },
                new SymbolDefinition { Value = 8, EncodeSymbol = '8', DecodeSymbols = new[] { '8' } },
                new SymbolDefinition { Value = 9, EncodeSymbol = '9', DecodeSymbols = new[] { '9' } },
                new SymbolDefinition { Value = 10, EncodeSymbol = 'A', DecodeSymbols = new[] { 'A', 'a' } },
                new SymbolDefinition { Value = 11, EncodeSymbol = 'B', DecodeSymbols = new[] { 'B', 'b' } },
                new SymbolDefinition { Value = 12, EncodeSymbol = 'C', DecodeSymbols = new[] { 'C', 'c' } },
                new SymbolDefinition { Value = 13, EncodeSymbol = 'D', DecodeSymbols = new[] { 'D', 'd' } },
                new SymbolDefinition { Value = 14, EncodeSymbol = 'E', DecodeSymbols = new[] { 'E', 'e' } },
                new SymbolDefinition { Value = 15, EncodeSymbol = 'F', DecodeSymbols = new[] { 'F', 'f' } },
                new SymbolDefinition { Value = 16, EncodeSymbol = 'G', DecodeSymbols = new[] { 'G', 'g' } },
                new SymbolDefinition { Value = 17, EncodeSymbol = 'H', DecodeSymbols = new[] { 'H', 'h' } },
                new SymbolDefinition { Value = 18, EncodeSymbol = 'J', DecodeSymbols = new[] { 'J', 'j' } },
                new SymbolDefinition { Value = 19, EncodeSymbol = 'K', DecodeSymbols = new[] { 'K', 'k' } },
                new SymbolDefinition { Value = 20, EncodeSymbol = 'M', DecodeSymbols = new[] { 'M', 'm' } },
                new SymbolDefinition { Value = 21, EncodeSymbol = 'N', DecodeSymbols = new[] { 'N', 'n' } },
                new SymbolDefinition { Value = 22, EncodeSymbol = 'P', DecodeSymbols = new[] { 'P', 'p' } },
                new SymbolDefinition { Value = 23, EncodeSymbol = 'Q', DecodeSymbols = new[] { 'Q', 'q' } },
                new SymbolDefinition { Value = 24, EncodeSymbol = 'R', DecodeSymbols = new[] { 'R', 'r' } },
                new SymbolDefinition { Value = 25, EncodeSymbol = 'S', DecodeSymbols = new[] { 'S', 's' } },
                new SymbolDefinition { Value = 26, EncodeSymbol = 'T', DecodeSymbols = new[] { 'T', 't' } },
                new SymbolDefinition { Value = 27, EncodeSymbol = 'V', DecodeSymbols = new[] { 'V', 'v' } },
                new SymbolDefinition { Value = 28, EncodeSymbol = 'W', DecodeSymbols = new[] { 'W', 'w' } },
                new SymbolDefinition { Value = 29, EncodeSymbol = 'X', DecodeSymbols = new[] { 'X', 'x' } },
                new SymbolDefinition { Value = 30, EncodeSymbol = 'Y', DecodeSymbols = new[] { 'Y', 'y' } },
                new SymbolDefinition { Value = 31, EncodeSymbol = 'Z', DecodeSymbols = new[] { 'Z', 'z' } },
            });

            extraCheckDigits.AddRange(new[]
            {
                new SymbolDefinition { Value = 32, EncodeSymbol = '*', DecodeSymbols = new[] { '*' } },
                new SymbolDefinition { Value = 33, EncodeSymbol = '~', DecodeSymbols = new[] { '~' } },
                new SymbolDefinition { Value = 34, EncodeSymbol = '$', DecodeSymbols = new[] { '$' } },
                new SymbolDefinition { Value = 35, EncodeSymbol = '=', DecodeSymbols = new[] { '=' } },
                new SymbolDefinition { Value = 36, EncodeSymbol = 'U', DecodeSymbols = new[] { 'U', 'u' } },
            });
        }

        public IDictionary<int, char> ValueEncodings
        {
            get
            {
                return this.ToDictionary(s => s.Value, s => s.EncodeSymbol);
            }
        }

        public IDictionary<int, char> CheckDigitEncodings
        {
            get
            {
                return this
                    .Union(extraCheckDigits)
                    .ToDictionary(s => s.Value, s => s.EncodeSymbol);
            }
        }

        public IDictionary<char, int> ValueDecodings
        {
            get
            {
                return this
                    .SelectMany(s => s.DecodeSymbols.Select(d => new { s.Value, DecodeSymbol = d }))
                    .ToDictionary(s => s.DecodeSymbol, s => s.Value);
            }
        }

        public IDictionary<char, int> CheckDigitDecodings
        {
            get
            {
                return this
                    .Union(extraCheckDigits)
                    .SelectMany(s => s.DecodeSymbols.Select(d => new { s.Value, DecodeSymbol = d }))
                    .ToDictionary(s => s.DecodeSymbol, s => s.Value);
            }
        }
    }

    internal class SymbolDefinition
    {
        public int Value { get; set; }
        public IEnumerable<char> DecodeSymbols { get; set; }
        public char EncodeSymbol { get; set; }
    }
}

मैंने कुछ अतिरिक्त आउटपुट लाइनों को जोड़ा है:

Average Number Before Duplicate: 41043.954
Minimum Number Before Duplicate: 2498
Maximum Number Before Duplicate: 127683
 Median Number Before Duplicate: 37860

यह दिलचस्प नहीं है, जबकि औसत लगभग 40k है, न्यूनतम और अधिकतम, परिमाण के दो आदेश अलग-अलग देखें।

यादृच्छिकता समान वितरण की गारंटी नहीं देती है। एक पासा के लगातार दो फेंक में, दोनों फेंकने पर नंबर 4 प्राप्त करना अभी भी यादृच्छिक है। एक जीवनकाल में लॉटरी बड़ा पुरस्कार दो बार या उससे अधिक जीतना पहले किया गया है।

यदि आपको प्रति थ्रेड में अधिक अनूठा वितरण की आवश्यकता है, तो मैंने जॉन स्कीट की सबसे उत्कृष्ट पुस्तक (हाँ, मैं एक प्रशंसक हूं) से रैंडमप्रोवाइडर का नमूना शामिल किया है।

अद्यतन करें

समांतर निष्पादन के लिए एक छोटी सी पुनर्लेखन, क्योंकि सिलिकॉन आधारित जीवन रूपों को यातना देना मजेदार है:

    static void Main(string[] args)
    {

        ConcurrentDictionary<int, int> resultDictionary = new ConcurrentDictionary<int, int>();
        Parallel.For(0, 1000, x =>
        {
            var r = RandomProvider.GetThreadRandom();
            ConcurrentDictionary<string, int> dictionary = new ConcurrentDictionary<string, int>();
                while (true)
                {
                    int rand = r.Next(0, 1073741823);
                    CrockfordBase32Encoding encoding = new CrockfordBase32Encoding();
                    string encodedRand = encoding.Encode((ulong) rand, false);
                    if (!dictionary.TryAdd(encodedRand, rand)) break;
                }
            Console.WriteLine("{0} - {1}", x, dictionary.Count);
            resultDictionary.TryAdd(x, dictionary.Count);
        });

        Console.WriteLine();
        Console.WriteLine("Average Number Before Duplicate: " + resultDictionary.Average(x => x.Value));
        Console.WriteLine("Minimum Number Before Duplicate: " + resultDictionary.Min(x => x.Value));
        Console.WriteLine("Maximum Number Before Duplicate: " + resultDictionary.Max(x => x.Value));
        Console.WriteLine(" Median Number Before Duplicate: " + resultDictionary.Select(x=>x.Value).Median());
        Console.ReadLine();
    }

और परिणाम:

Average Number Before Duplicate: 41826.375
Minimum Number Before Duplicate: 1655
Maximum Number Before Duplicate: 134671
 Median Number Before Duplicate: 39119

अद्यतन 2

तो कोडप्रोजेक्ट आलेख के लेखक ने अपना काम एक NuGet पैकेज के रूप में प्रकाशित किया है:

Install-Package Troschuetz.Random

मैंने विभिन्न जेनरेटर का परीक्षण करने के लिए एक ही नमूना कोड का उपयोग किया है:

StandardGenerator

Average Number Before Duplicate: 40434.148
Minimum Number Before Duplicate: 978
Maximum Number Before Duplicate: 136248
 Median Number Before Duplicate: 38845

ALFGenerator

Average Number Before Duplicate: 40395.845
Minimum Number Before Duplicate: 828
Maximum Number Before Duplicate: 125705
 Median Number Before Duplicate: 38042

MT19937Generator

Average Number Before Duplicate: 40478.174
Minimum Number Before Duplicate: 2723
Maximum Number Before Duplicate: 121367
 Median Number Before Duplicate: 38279

XorShift128Generator

Average Number Before Duplicate: 41463.732
Minimum Number Before Duplicate: 878
Maximum Number Before Duplicate: 111206
 Median Number Before Duplicate: 39013.5

इसलिए यह अब आपके पास है। इसके लिए क्या लायक है इसका आनंद लें ..


इसे en.wikipedia.org/wiki/Birthday_problem रूप में जाना जाता है और यह केवल मूल संभावना-सिद्धांत है।

संभावना है कि एन के माध्यम से श्रेणी 1 में यादृच्छिक संख्या डुप्लिकेट नहीं देती है:


कम से कम एक डुप्लिकेट प्राप्त करने के मौके की गणना करने के लिए 1 से मान घटाएं।

आपके मामले में यह मूल्यांकन करता है

P(40000, 1073741823) = 1 - p(40000, 1073741823)

गणना करने के लिए वोल्फ्राम अल्फा का उपयोग करके परिणाम है

0.5252888122305790

जिसका अर्थ है कि यह 50% से थोड़ा अधिक मौका है, आपको डुप्लिकेट मिलेगा। जैसे ही आप अधिक संख्याएं उत्पन्न करते हैं, आपको अधिक से अधिक डुप्लिकेट मिलेंगे।

एन के कुछ और मूल्यांकन यहां दिए गए हैं:

   N      Result
 40000    0.5253
100000    0.9905
200000    0.9999




base32