خلط ورق اللعب باستخدام icomparer

Question

بادئ ذي بدء، أعرف عن خلط ورق اللعب فيشر. ولكن دعونا نقول للحجج التي أريد أن أسمح للمستخدم باختيار الفرز من قائمة منسدلة. ستشمل هذه القائمة خيار "عشوائي". بناء على نتيجة اختيارهم، أريد فقط استبدال مثيل Icomparer الخاص بي. ما الذي يشبه Icomparer؟

تشكل Google عددا كبيرا من النتائج المعيبة التي تأخذها جميعها هذا النموذج:

public class NaiveRandomizer<T> : IComparer<T>
{
    private static Random rand = new Random();

    public int Compare(T x, T y)
    {
        return (x.Equals(y))?0:rand.Next(-1, 2);
    }
}

ومع ذلك، فإن هذا التنفيذ منحازي وسوف يرمي استثناءا في بعض الظروف. يمكن إظهار التحيز مع التعليمات البرمجية التالية:

void Test()
{
    Console.WriteLine("NaiveRandomizer Test:");
    var data = new List<int>() {1,2,3};
    var sortCounts = new Dictionary<string, int>(6);
    var randomly = new NaiveRandomizer<int>();

    for (int i=0;i<10000;i++)
    {   //always start with same list, in _the same order_.
        var dataCopy = new List<int>(data); 
        dataCopy.Sort(randomly);

        var key = WriteList(dataCopy);
        if (sortCounts.ContainsKey(key))
            sortCounts[key]++;
        else
            sortCounts.Add(key, 1);
    }

    foreach (KeyValuePair<string, int> item in sortCounts)
        Console.WriteLine(item.Key + "\t" + item.Value);
}

string WriteList<T>(List<T> list)
{
   string delim = "";
   string result = "";
   foreach(T item in list)
   {
       result += delim + item.ToString();
       delim = ", ";
   }
   return result;
}

فكيف يمكنك تنفيذ عشوائي IComparer<T> التي حل هذه القضايا؟ يسمح له بطلب كل مكالمة .Sort() لاستخدام مثيل Icomparer منفصل، لأنني لا أرى أي طريقة أخرى للقيام بذلك: العناصر يجب يمكن مقارنتها باستخدام بعضها البعض، قيمة عشوائية حقا، ولكن هذه القيمة يجب أن تكون متسقة أيضا لعنصر ضمن عملية فرز معينة.

لدي بداية هنا, ، ولكن تم نشره في العجلة، هو الى ابعد حد بطيئة، ولا حتى إرجاع جميع الأنواع الممكنة (يبين الاختبار أنه يفعل على الأقل إلغاء التحيز، إذا كنت لا تحسب الخيارات المفقودة). لا أتوقع أداء O (N) مثل Fisher-Yates، لكنني أريد شيئا معقولا (سجل N N للحصول على صغير ISH N)، وأتوقع أنه لإظهار كل أنواع ممكنة. لسوء الحظ، هذا الرابط هو الإجابة الحالية المقبولة لسؤالها، لذلك آمل أن أكون قادرا على استبدالها بشيء أفضل قليلا.

إذا لم يكن هناك شيء آخر، فأنا أريد أن يكون هذا مغناطيسا لجميع هذه الاستعلامات Google التي تبحث عن حل مثبت - أنهم سينتهي بهم الأمر هنا بدلا من مكان آخر يخبرونهم باستخدام الإصدار غير الصحيح.

Answer 1

اقتراح واحد حصلت في أماكن أخرى هو إنشاء واجهة IARRanger منفصلة تصف عملية واحدة ل يرتب مجموعة. يمكن أن يعمل هذا حيث لا يستطيع Icomparer / icomomarable لأنه يعمل على مجموعة كاملة، بدلا من العناصر الفردية. قد تبدو مثل هذا:

public interface IArranger<T>
{
    IEnumerable<T> Arrange(IEnumerable<T> items);
}

ثم يمكنني تنفيذ Shuffle من واجهة IARRanger باستخدام خوارزمية مناسبة للشركة فيشر، ولديها أيضا تطبيقات تفتتح كل إضافي IEnumerable.Sort()/IComparable/IComparer الأصناف التي أهتم بها. قد تبدو مثل هذا:

public class ComparerArranger<T> : IArranger<T>
{
    private IComparer<T> comparer;

    public ComparableArranger(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i, comparer);
    }
}

أو

//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T> 
{
    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i);
    }
}

أو

public class ShuffleArranger<T> : IArranger<T>
{
    //naive implementation for demonstration
    // if I ever develop this more completely I would try to
    // avoid needing to call .ToArray() in here
    // and use a better prng
    private Random r = new Random();

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
        var values = items.ToArray();

        //valid Fisher-Yates shuffle on the values array
        for (int i = values.Length; i > 1; i--)
        {
            int j = r.Next(i);
            T tmp = values[j];
            values[j] = values[i - 1];
            values[i - 1] = tmp;
        }
        foreach (var item in values) yield return item;
    }
}

للحصول على خطوة أخيرة، أضيف الدعم لهذا إلى أي ienumerable عبر طريقة تمديد. ثم لا تزال تحصل على تبديل خوارزمية وقت التشغيل البسيط، لديك تطبيق أفضل لخوارزمية خلط ورق اللعب، والرمز لاستخدامه يبدو طبيعيا:

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
    return arranger.Arrange(items);
}

Answer 2

لقد فوجئت إلى حد ما هذا الموضوع كم عدد الإجابات الخاطئة التي تم نشرها. فقط من أجل الآخرين الذين يأتون إلى حل مشابه للواحد الذي أرسله البروتوكول الاختياري، الكود التالي تبدو صيح:

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

ومع ذلك، سيقوم القانون بإلقاء استثناء في بعض الأحيان، ولكن ليس دائما. هذا ما يجعلها ممتعة لتصحيح الأخطاء :) إذا قمت بتشغيلها أوقاتا كافية، أو تنفيذ إجراء الفرز في حلقة 50 أو نحو ذلك، ستحصل على خطأ يفيد:

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The IComparer: ''.

بمعنى آخر، هذا النوع السريع مقارنة ببعض العدد x لنفسها وحصلت على نتيجة غير صفرية. سيكون الحل الواضح للقانون يكتب:

Array.Sort<int>(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

ولكن حتى هذا لا يعمل، لأن هناك مناسبات حيث يقارن .NET .NET أرقام ضد بعضها البعض مما يؤدي إلى نتائج غير متناسقة، مثل A> B، B> C، و C> A (عفوا!). بغض النظر عما إذا كنت تستخدم GUID أو Gethashcode أو أي مدخلات أخرى تم إنشاؤها عشوائيا، فإن الحل مثل الواحد الموضح أعلاه لا يزال خطأ.

---

مع القول، فإن فيشر ييتس هو الطريقة القياسية لمصفوفات خلط، لذلك ليس هناك سبب حقيقي لاستخدام Icomparer في المقام الأول. فيشر ييتس هو O (N) في حين أن أي تطبيق يستخدم Icomparer يستخدم QuickStort خلف الكواليس التي لديها تعقيد وقت O (N Log N). ليس هناك سبب وجيه لعدم استخدام الخوارزمية المعروفة والكفاءة والفعالة لحل هذا النوع من المشكلة.

ومع ذلك، إذا أصرت حقا على استخدام Icomparer وراند، فقم بتطبيق بياناتك العشوائية قبل أنت فرز. يتطلب هذا عرضا للبيانات على كائن آخر حتى لا تفقد بياناتك العشوائية:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair<T, U>
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

أو احصل على Linqy مع نفسك السيئ:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;

Answer 3

icomparer تتطلب عودة صفر في مرحلة ما (للحصول على مثيلات متساوية من ر)، يجعلها رياضيا من المستحيل إنشاء Icomparer Generic من شأنه أن يحاكي خلط ضاحك في صياد فيشر. سيكون هناك دائما تحيز. خلط ورق اللعب الحقيقي، لن ترغب أبدا في إجباره على إعادة أي قيمة معينة.

Answer 4

كيف 'نوبة الفرز بناء على حقل مخفي، والتي تم تعيينها مسبقا قيمة عشوائية؟

Answer 5

لمتابعة فكرة جيمس كوران: دع التحفيز لا يحافظ على القيم "الفرز" كقائمة؛ إذا حدثت قيمة جديدة، أدخلها في القائمة بموضع عشوائي؛ قارن بواسطة فهرس القائمة. التحسين من خلال الحفاظ على القائمة كشجرة متوازنة أو شيء من هذا. سيحافظ كل مثيل من مثل هذا المثليين على ترتيب فرز ثابت وعشوائي حتى يكون لديك اختيار السماح للفرز العشوائي بنفس طلب عشوائي أو واحد مختلف في كل مرة. سوف يسمح تعديل بسيط حتى عناصر متساوية ليتم "فرزها" في مواقف طلبية مختلفة، إذا كنت تفضل قراءة "عشوائي" بهذه الطريقة.

Answer 6

مسعى مثير للاهتمام. على الأرجح سوء استخدام / إساءة استخدام Icomparer.

أنت تحاول إجراء فرز مرجز عشوائي باستخدام آلية لم يتم بناؤها لهذا الغرض.

لماذا لا تنفذ روتين الفرز الخاص بك والمقارنة الخاصة بك؟ لدي شعور بأنه لن يكون كافيا.

Answer 7

لا تفعل ذلك.

جميع الخوارزميات المقترحة حتى الآن تقدم نوعا من التحيز في الإخراج (بعض أكبر من غيرها).

تقترح Rincess و Luke تخزين رقم عشوائي جنبا إلى جنب مع البيانات. ومع ذلك، فهناك احتمال أن يكون لدى أي رقمين من هذه الأرقام العشوائية نفس القيمة مثل آخر، فإن ترتيب الفرز بين هذين عنصرين سيكون متحيزا محتملا

ستكون أسوأ حالة لهذا الغرض إذا كان روتين الفرز "مستقرا" (هو أن الكائنات التي تعتبر متساوية دائما إخراج دائما بنفس الترتيب الذي كانت مدخلات فيه). لا يحدث Array.Sort مستقر (يستخدم QuickSort Internally) ولكن لا يزال هناك تحيز يحدث كلما كان عنصرين لهما نفس القيمة التي تعتمد على المكان الذي تعتمد فيه في الإدخال (وتحديدا حيث هم نسبي إلى QuickSort's pivot).

كما يزيد حجم المفاتيح لهذا العدد العشوائي، تنخفض احتمال الاصطدام (مع مصدر عشوائي جيد)، ولكن ضع في اعتبارك أنه نظرا لأن عدد القيم التي تقوم بها الفرز، فإن مفارقة عيد الميلاد يملي ذلك على الأقل زوج واحد بينهم يصطدمون بسرعة كبيرة.

للحصول على مفتاح عدد صحيح، هناك 2 ^ 32 قيم فريدة للمفتاح وحتى على افتراض أن هناك توزيعا تماما حتى لقيم عشوائية، مع 75000 صف، هناك احتمال 50٪ سيكون هناك تصادم. ويكيبيديا.

يتواهى تجزئة التشفير التي اقترحتها على أنه يحتمل أن يكون لديها أجزاء كبيرة بما يكفي (160) بتسهيل الاصطدام ضئيل، لكن الخوارزمية الخاصة بك تتحلل كل هذه العشوائية مرة أخرى إلى كثيرة واحدة قبل القيام بالمقارنة التي تنفيها فعليا هذا مفاتيح أكبر.

أفضل نهجك هو ربط قيمة "شريان" متميز مع كل عنصر من عناصر البيانات الخاصة بك خلط ورق اللعب هذه القيم باستخدام خوارزمية مثبتة، ثم اطلب النتائج حسب هذه القيمة.

إذا كنت تستخدم Array.Sort، فهناك عبارة عن عبارة عن مجموعة من "مفاتيح" ومجموعة من "القيم". يتم فرز صفيف المفاتيح بشكل طبيعي، ولكن كلما تم نقل قيمة في صفيف المفاتيح، يتم نقل الإدخال المقابل في صفيف القيم أيضا.

شيء مثل:

Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
 keys[i] = i;
}

Shuffle(keys);

Array.Sort(keys, data);