كيفية خلط مصفوفة في Swift: تحسين الأداء والأداء

كيفية خلط مصفوفة في Swift بشكل صحيح: من المبتدئ إلى المحترف

هل تساءلت يومًا عن كيفية إنشاء قائمة تشغيل عشوائية في تطبيقك؟ أو ربما كنت بحاجة إلى خلط أسئلة في اختبار بحيث تظهر بترتيب جديد في كل مرة؟ إذا كنت تعمل مع Swift، فستواجه عاجلاً أم آجلاً مهمة: كيفية خلط مصفوفة (shuffle array). هذا السؤال على Stack Overflow حصد آلاف المشاهدات، وليس من دون سبب - فهناك مطبات خفية أكثر مما يبدو للوهلة الأولى.

في هذه المقالة، لن نعرض فقط كيفية استدعاء shuffle(). سننظر تحت الغطاء: سنحلل الخوارزميات، ونقارن الأداء، ونتعلم كيفية عمل خلط محسّن، ونفهم متى تكون الطريقة القياسية شرًا، ومتى تكون أفضل ما اخترعته البشرية. هيا بنا!

لماذا مجرد "random" فكرة سيئة؟

لنفترض أن لديك مصفوفة:

var cards = ["آس", "ملك", "ملكة", "جاك"]

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

func naiveShuffle(_ array: [String]) -> [String] {\n    var shuffled = [String]()\n    for element in array {\n        let randomIndex = Int.random(in: 0...shuffled.count)\n        shuffled.insert(element, at: randomIndex)\n    }\n    return shuffled\n}

في المصفوفات الصغيرة (4-10 عناصر)، يعمل هذا. ولكن بمجرد أن يتجاوز عدد العناصر المئة، ستشعر بالألم. لماذا؟ لأن insert(at:) له تعقيد O(n) - في كل مرة تقوم فيها بإدراج عنصر في البداية أو المنتصف، تنتقل جميع العناصر التالية. التعقيد النهائي: O(n²). لمصفوفة من 1000 عنصر، هذا يعني 500,000 عملية. لـ 10,000 - بالفعل 50 مليون. سيبدأ التطبيق في "التأخير"، سيغادر المستخدم، سينخفض التقييم. لا تفعل هذا.

الطريقة المضمنة shuffle(): صديقك الجديد الأفضل

بدءًا من Swift 4.2، لدينا الطريقة الأصلية shuffle() (للمصفوفات القابلة للتغيير) و shuffled() (تعيد مصفوفة جديدة). إليك كيفية عمل ذلك:

var numbers = [1, 2, 3, 4, 5]\nnumbers.shuffle()  // يغير المصفوفة الأصلية\nprint(numbers)     // على سبيل المثال: [3, 1, 5, 2, 4]\n\nlet shuffledNumbers = numbers.shuffled()  // مصفوفة جديدة\nprint(shuffledNumbers)                    // [4, 2, 1, 5, 3]

تحت الغطاء، تستخدم Apple خوارزمية فيشر-يتس (المعروفة أيضًا بخوارزمية كنوث). هذا هو المعيار الذهبي للخلط. كيف تعمل؟ نمر عبر المصفوفة من العنصر الأخير إلى الأول، لكل عنصر نختار فهرسًا عشوائيًا من 0 إلى الموضع الحالي ونتبادل العناصر. التعقيد: O(n). لمصفوفة من 10,000 عنصر - فقط 10,000 عملية. أسرع بـ 5000 مرة من النهج الساذج!

خوارزمية فيشر-يتس: شرح مبسط

لنقم بتنفيذها يدويًا لفهم السحر:

extension Array {\n    mutating func customShuffle() {\n        for i in stride(from: count - 1, through: 1, by: -1) {\n            let j = Int.random(in: 0...i)\n            swapAt(i, j)\n        }\n    }\n}\n\nvar deck = Array(1...10)\ndeck.customShuffle()\nprint(deck) // [6, 2, 9, 1, 8, 4, 7, 3, 10, 5]

ماذا يحدث هنا؟ لنفترض مصفوفة من 5 عناصر. نبدأ من الفهرس 4 (الأخير). نختار رقمًا عشوائيًا من 0 إلى 4، ونتبادل. ثم ننتقل إلى الفهرس 3، نختار من 0 إلى 3، ونتبادل. وهكذا حتى الفهرس 1. كل عنصر مضمون أن يكون في موضع عشوائي مرة واحدة بالضبط. لا انتقالات، لا إدراجات متكررة - رياضيات بحتة.

ملاحظة مهمة: في خوارزمية فيشر-يتس، لا يمكن اختيار فهرس عشوائي من 0 إلى count-1 في كل خطوة. لماذا؟ لأن بعض العناصر قد تبقى في أماكنها، بينما تتحرك أخرى عدة مرات، مما يخل بالتوزيع المتساوي. ثق في التنفيذ القياسي من Apple - إنه الأمثل.