تنفيذ خلط ورق اللعب على صندوق الموسيقى السماوية

Question

كيف يمكن تنفيذ خلط ورق اللعب لـ "الصندوق الموسيقي السماوي"؟

بتعبير أدق، في كل مرة t، قم بإرجاع رقم عشوائي موحد بين 0..n(t)، بحيث لا يكون هناك تكرار في التسلسل بأكمله، مع زيادة n() بمرور الوقت.

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

قد يكون الحل المثالي ممكنًا على الأجهزة الموجودة - كيف يمكنني تشغيل قائمة تضم ستة ملايين أغنية في 8 ميجابايت من ذاكرة الوصول العشوائي الديناميكية (DRAM)؟وبالمثل، يؤدي ارتفاع عدد الأغاني إلى تفاقم توقيتات اختيار O(n).

-- بالنسبة لمولد الواقيات الأساسية لإنقاذ الحياة، نظرا لاستنفاد الواقيات الأساسية لإنقاذ الحياة جزئيا على 0..N₀, ، هل يمكن ترجمة ذلك إلى واقي أساسي لإنقاذ الحياة مختلف على 0..N₁ (حيث N1 > N0)، وهذا لا يكرر التسلسل المنهك.
-- يبدو أن التحقق من تشغيل أغنية معينة قد أصبح خارج نطاق السيطرة بسرعة، على الرغم من أن هذه قد تكون الطريقة الوحيدة؟هل هناك بنية بيانات فعالة لهذا؟

Answer 1

الطريقة التي أحب القيام بها بهذا النوع من الاختيار العشوائي غير المتكرر هي أن يكون لدي قائمة، وفي كل مرة أحدد عنصرًا بشكل عشوائي بين [0-N), ، أقوم بإزالته من تلك القائمة.في حالتك، عند إضافة عناصر جديدة إلى الكتالوج، ستتم إضافتها أيضًا إلى القائمة التي لم يتم تحديدها بعد.بمجرد وصولك إلى النهاية، ما عليك سوى إعادة تحميل جميع الأغاني مرة أخرى إلى القائمة.

يحرر:

إذا أخذت اقتراح v3 بعين الاعتبار، فيمكن القيام بذلك بشكل أساسي O(1) الوقت بعد O(N) خطوة التهيئة.ويضمن عدم تكرار الاختيار العشوائي.

هنا هو الخلاصة:

1. أضف العناصر الأولية إلى القائمة
2. اختر الفهرس i عشوائيا (من مجموعة من [0,N))
3. إزالة العنصر في الفهرس i
4. استبدل الفتحة عند i مع ال Nth العنصر (أو فارغًا إذا i == Nth) والتناقص N
5. بالنسبة للعناصر الجديدة، ما عليك سوى إلحاقها بنهاية القائمة وزيادة عددها N عند الضرورة
6. إذا تمكنت من تشغيل جميع الأغاني (أشك في أن لديك 6 ملايين أغنية)، فقم بإضافة جميع الأغاني مرة أخرى إلى القائمة، ثم قم بغسلها، ثم اشطفها، ثم كررها.

نظرًا لأنك تحاول التعامل مع مجموعات كبيرة نوعًا ما، فإنني أوصي باستخدام قاعدة بيانات.جدول بسيط يحتوي على حقلين أساسيين: id و "pointer" (أين "pointer"" هو ما يخبرك بالأغنية التي تريد تشغيلها والتي يمكن أن تكون عبارة عن GUID أو اسم ملف أو ما إلى ذلك، اعتمادًا على الطريقة التي تريد القيام بها).لديك فهرس على id ويجب أن تحصل على أداء لائق جدًا مع المثابرة بين عمليات تشغيل التطبيق.

تعديل لحد 8 ميجابايت:

أم، هذا يجعل الأمر أصعب قليلاً...في مساحة 8 ميجابايت، يمكنك تخزين ما يصل إلى 2 مليون إدخال كحد أقصى باستخدام مفاتيح 32 بت.

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

Answer 2

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

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

إذا كنت على استعداد للاسترخاء متطلبات 8MB ذاكرة الوصول العشوائي لمدة 6 مليون أغنية، أو للذهاب إلى القرص (على سبيل المثال، من خلال تعيين ذاكرة)، هل يمكن أن تولد سلسلة من 1..n في البداية، خلط ورق اللعب عليه مع فيشر ييتس، وكلما تمت إضافة أغنية جديدة، واختيار عنصر عشوائي من قسم إلى الآن، غير لعب، إدراج ID جديد هناك، وإلحاق ID الأصلي إلى نهاية القائمة.

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

Answer 3

وحين حل إريك هو على الأرجح أفضل لحالة استخدام محددة، والتحقق ما إذا كان أغنية تم بالفعل لعبت سريعة جدا (O إطفاء (1)) مع هيكل القائم على التجزئة، مثل set في بيثون أو hashset<int> في C ++.

Answer 4

هل يمكن ببساطة خلق تسلسل أرقام من 1 إلى n ومن ثم خلط ورق اللعب باستخدام المراوغة فيشر ييتس. وبهذه الطريقة يمكنك أن تضمن أن تسلسل لن تتكرر، بغض النظر عن ن.

Answer 5

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

 struct playlistNode{
  songLocator* song;
  playlistNode  *next;
};
struct playlistNode arr[N];

وتبقي أيضا على "رأس" ومؤشر "freelist '؛

وتعبئة في 2 ممرات:
    1. ملء آر مع جميع الأغاني في الكتالوج من أجل 0..N.
    2. تكرار عشوائيا من خلال جميع المؤشرات، وملء في مؤشر next؛

وحذف الأغاني لعبت هو O (1):

head=cur->next;
cur->song=NULL;
freelist->next = freelist;
cur->next=freelist;
freelist=cur;

والإدراج من الأغاني الجديدة O (1) أيضا: اختيار مؤشر مجموعة عشوائيا، وتصحيح عقدة جديدة

node = freelist;
freelist=freelist->next;
do {
i=rand(N);   
} while (!arr[i].song);  //make sure you didn't hit a played node
node->next = arr[i].next;
arr[i].next=node;