أفضل طريقة لاختيار مجموعة فرعية عشوائية من مجموعة؟

Question

لدي مجموعة من الكائنات في Vector والتي أرغب في تحديد مجموعة فرعية عشوائية منها (على سبيل المثال.100 عنصر يعود؛اختر 5 عشوائيا).في تمريرتي الأولى (المتسرعة جدًا) قمت بحل بسيط للغاية وربما ذكي للغاية:

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

على الرغم من أن هذا يتمتع بميزة كونه لطيفًا وبسيطًا، إلا أنني أظن أنه لن يتم توسيع نطاقه بشكل جيد، على سبيل المثال.يجب أن تكون Collections.shuffle()‎ O(n) على الأقل.البديل الأقل ذكاءً هو

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

هل هناك أي اقتراحات حول طرق أفضل لاستخلاص مجموعة فرعية عشوائية من المجموعة؟

Answer 1

يناقش جون بنتلي هذا الأمر إما في "لآلئ البرمجة" أو "المزيد من لآلئ البرمجة".يجب أن تكون حذرًا في عملية اختيار N of M، ولكن أعتقد أن الكود الموضح يعمل بشكل صحيح.بدلاً من خلط جميع العناصر بشكل عشوائي، يمكنك إجراء الخلط العشوائي فقط من خلال تبديل المواضع N الأولى - وهو حفظ مفيد عندما يكون N << M.

يناقش Knuth أيضًا هذه الخوارزميات - أعتقد أن ذلك سيكون المجلد 3 "الفرز والبحث"، ولكن مجموعتي مكتظة في انتظار نقل المنزل لذا لا يمكنني التحقق من ذلك رسميًا.

Answer 2

@ جوناثان،

أعتقد أن هذا هو الحل الذي تتحدث عنه:

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

إنه موجود في الصفحة 127 من Programming Pearls بقلم جون بنتلي ويستند إلى تنفيذ Knuth.

يحرر:لقد رأيت للتو تعديلًا إضافيًا في الصفحة 129:

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

يعتمد هذا على فكرة أن "... نحتاج إلى خلط الأول فقط م عناصر المصفوفة..."

Answer 3

إذا كنت تحاول تحديد k عناصر مميزة من قائمة n، فإن الطرق التي ذكرتها أعلاه ستكون O(n) أو O(kn)، لأن إزالة عنصر من Vector سيؤدي إلى قيام نسخة مصفوفة بإزاحة جميع العناصر لأسفل .

نظرًا لأنك تسأل عن أفضل طريقة، فإن ذلك يعتمد على ما يُسمح لك بفعله بقائمة الإدخال الخاصة بك.

إذا كان من المقبول تعديل قائمة الإدخال، كما هو الحال في الأمثلة الخاصة بك، فيمكنك ببساطة تبديل عناصر عشوائية k إلى بداية القائمة وإعادتها في وقت O(k) مثل هذا:

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

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

ومع ذلك، إذا لم تتمكن من تعديل قائمة الإدخال على الإطلاق وكان k أقل بكثير من n (مثل 5 من 100)، فسيكون من الأفضل عدم إزالة العناصر المحددة في كل مرة، ولكن ببساطة حدد كل عنصر، وإذا حصلت على نسخة مكررة، ارمها وأعد تحديدها.سيعطيك هذا O(kn / (n-k)) الذي لا يزال قريبًا من O(k) عندما يهيمن n على k.(على سبيل المثال، إذا كانت k أقل من n / 2، فإنها تنخفض إلى O(k)).

إذا لم يهيمن n على k، ولا يمكنك تعديل القائمة، فيمكنك أيضًا نسخ قائمتك الأصلية، واستخدام الحل الأول، لأن O(n) سيكون بنفس جودة O(k).

كما لاحظ آخرون، إذا كنت تعتمد على العشوائية القوية حيث تكون كل قائمة فرعية ممكنة (وغير متحيزة)، فستحتاج بالتأكيد إلى شيء أقوى من ذلك. java.util.Random.يرى java.security.SecureRandom.

Answer 4

كتبت التنفيذ الفعال لهذا قبل بضعة أسابيع.إنها لغة C# لكن الترجمة إلى Java تافهة (نفس الكود في الأساس).الجانب الإيجابي هو أنه أيضًا غير متحيز تمامًا (وبعض الإجابات الموجودة ليست كذلك) - طريقة لاختبار ذلك هنا.

إنه يعتمد على تطبيق Durstenfeld لخلط فيشر ييتس.

Answer 5

الحل الثاني الخاص بك لاستخدام Random لاختيار العنصر يبدو سليمًا، ولكن:

• اعتمادًا على مدى حساسية بياناتك، أقترح استخدام نوع ما من طرق التجزئة لخلط بذرة الأرقام العشوائية.للحصول على دراسة حالة جيدة، راجع كيف تعلمنا الغش في البوكر على الإنترنت (لكن هذا الرابط هو 404 اعتبارًا من 18/12/2015).تتضمن عناوين URL البديلة (التي يمكن العثور عليها عبر بحث Google على عنوان المقالة بين علامتي اقتباس مزدوجتين):

  • كيف تعلمنا الغش في البوكر على الإنترنت - على ما يبدو الناشر الأصلي.
  • كيف تعلمنا الغش في البوكر على الإنترنت
  • كيف تعلمنا الغش في البوكر على الإنترنت
     

• تتم مزامنة المتجهات.إذا أمكن، استخدم ArrayList بدلاً من ذلك لتحسين الأداء.

Answer 6

كم تكلفة الإزالة؟لأنه إذا كان ذلك يتطلب إعادة كتابة المصفوفة إلى جزء جديد من الذاكرة، فقد قمت بإجراء عمليات O(5n) في الإصدار الثاني، بدلاً من O(n) التي أردتها من قبل.

يمكنك إنشاء مصفوفة من القيم المنطقية مضبوطة على القيمة false، ثم:

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

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

Answer 7

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

Answer 8

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

Answer 9

هذا هو سؤال مشابه جدًا حول Stackoverflow.

لتلخيص إجاباتي المفضلة من تلك الصفحة (أولاً من المستخدم كايل):

• يا (ن) الحل:كرر خلال قائمتك، وانسخ عنصرًا (أو مرجعًا إليه) مع الاحتمال (#needed / #remaining).مثال:إذا كان k = 5 وn = 100، فستأخذ العنصر الأول باستخدام السؤال 5/100.إذا قمت بنسخ ذلك، فاختر التالي مع السؤال 4/99؛ولكن إذا لم تأخذ الأولى، فالاحتمال هو 5/99.
• يا (ك سجل ك) أو يا (ك²):أنشئ قائمة مرتبة من مؤشرات k (الأرقام في {0، 1، ...، n-1}) عن طريق اختيار رقم < n عشوائيًا، ثم اختيار رقم < n-1 بشكل عشوائي، وما إلى ذلك.في كل خطوة، تحتاج إلى إعادة ضبط اختيارك لتجنب الاصطدامات والحفاظ على تكافؤ الاحتمالات.على سبيل المثال، إذا كان k=5 وn=100، وكان اختيارك الأول هو 43، فسيكون اختيارك التالي في النطاق [0، 98]، وإذا كان >=43، فقم بإضافة 1 إليه.لذا، إذا كان اختيارك الثاني هو 50، فأنت تضيف إليه 1، ويصبح لديك {43، 51}.إذا كان خيارك التالي هو 51، فقم بالإضافة 2 إليها لتحصل على {43، 51، 53}.

وهنا بعض الزائفة -

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s 

أنا أقول أن التعقيد الزمني هو O(k²) أو O(k log k) لأن ذلك يعتمد على مدى سرعة البحث والإدراج في الحاوية الخاصة بك لـ s.إذا كانت s قائمة عادية، فإن إحدى هذه العمليات تكون خطية، وستحصل على k^2.ومع ذلك، إذا كنت على استعداد لبناء s كشجرة ثنائية متوازنة، فيمكنك الحصول على وقت O(k log k).

Answer 10

لا أعتقد أن هناك حلين يظهران هنا - المطابق طويل جدًا، ويحتوي على بعض الروابط، ومع ذلك، لا أعتقد أن جميع المنشورات تتعلق بمشكلة اختيار فرع من عناصر K من مجموعة عناصر N .[بكلمة "مجموعة"، أشير إلى المصطلح الرياضي، أي.تظهر جميع العناصر مرة واحدة، والترتيب ليس مهمًا].

اليوم المريخي 1:

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

يبدو هذا مشابهًا للإجابة التي قدمها دانيال، لكنه في الواقع مختلف تمامًا.إنه وقت التشغيل O(k).

الحل الآخر هو استخدام بعض الرياضيات:اعتبر فهارس المصفوفة Z_n وبالتالي يمكننا اختيار رقمين بشكل عشوائي، x وهو أولي مشارك لـ n، أي.chhose gcd(x,n)=1، وآخر، a، وهو "نقطة البداية" - ثم السلسلة:a % n,a+x % n, a+2*x % n,...a+(k-1)*x%n عبارة عن سلسلة من الأرقام المميزة (طالما k<=n).