modo migliore per scegliere un sottoinsieme casuale da una collezione?

https://stackoverflow.com/questions/136474

02-07-2019
|

Domanda

Ho una serie di oggetti in un Vettore da cui vorrei selezionare un sottoinsieme casuale (ad es.100 articoli di ritorno;scegliere 5 in modo casuale).Nel mio primo (e molto frettolosa) pass ho fatto un estremamente semplice e, forse, eccessivamente soluzione intelligente:

Vector itemsVector = getItems();

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

Mentre questo ha il vantaggio di essere semplice e bello, ho il sospetto che non si sta andando a scala molto bene, cioèCollezioni.shuffle() deve essere O(n) almeno.Il mio meno intelligente alternativa

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())));
}

Eventuali suggerimenti su come migliorare estrarre un sottoinsieme casuale da una Collezione?

Soluzione

Jon Bentley ne discute in "Perle di programmazione" o "Perle di programmazione". Devi stare attento con il tuo processo di selezione N of M, ma penso che il codice mostrato funzioni correttamente. Invece di mescolare casualmente tutti gli oggetti, puoi fare lo shuffle casuale mescolando solo le prime N posizioni - il che è un utile salvataggio quando N & Lt; & Lt; M.

Knuth discute anche di questi algoritmi - credo che sarebbe Vol 3 " Ordinamento e ricerca " ;, ma il mio set è pieno in attesa di un trasloco, quindi non posso verificarlo formalmente.

Altri suggerimenti

@ Jonathan,

Credo che questa sia la soluzione di cui stai parlando:

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--;
         }
}

È a pagina 127 di Programming Pearls di Jon Bentley ed è basato sull'implementazione di Knuth.

EDIT: ho appena visto un'ulteriore modifica a pagina 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";
}

Questo si basa sull'idea che " ... abbiamo bisogno di mescolare solo i primi m elementi dell'array ... "

Se stai provando a selezionare k elementi distinti da un elenco di n, i metodi che hai dato sopra saranno O (n) o O (kn), perché la rimozione di un elemento da un vettore farà spostare tutti gli arraycopy gli elementi in basso.

Dato che stai chiedendo il modo migliore, dipende da cosa ti è permesso fare con la tua lista di input.

Se è accettabile modificare l'elenco di input, come nei tuoi esempi, puoi semplicemente scambiare k elementi casuali all'inizio dell'elenco e restituirli in O (k) time in questo modo:

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);
}

Se l'elenco deve finire nello stesso stato in cui è iniziato, puoi tenere traccia delle posizioni che hai scambiato, quindi riportare l'elenco allo stato originale dopo aver copiato l'elenco secondario selezionato. Questa è ancora una soluzione O (k).

Se, tuttavia, non è possibile modificare affatto l'elenco di input e k è molto inferiore a n (come 5 da 100), sarebbe molto meglio non rimuovere gli elementi selezionati ogni volta, ma semplicemente selezionare ogni elemento e se hai mai ricevuto un duplicato, buttalo fuori e riseleziona. Questo ti darà O (kn / (n-k)) che è ancora vicino a O (k) quando n domina k. (Ad esempio, se k è inferiore a n / 2, allora si riduce a O (k)).

Se k non è dominato da n e non è possibile modificare l'elenco, è possibile anche copiare l'elenco originale e utilizzare la prima soluzione, poiché O (n) sarà uguale a O (k).

Come altri hanno notato, se dipendi da una forte casualità in cui ogni sottoelenco è possibile (e imparziale), avrai sicuramente bisogno di qualcosa di più forte di java.util.Random. Vedi java.security.SecureRandom.

Ho scritto a un'implementazione efficiente di questo un modo per testare qui .

Si basa su un'implementazione di Durstenfeld dello shuffle Fisher-Yates.

La tua seconda soluzione di utilizzo di Casuale per selezionare l'elemento sembra comunque valida:

A seconda di quanto siano sensibili i tuoi dati, ti suggerisco di utilizzare una sorta di metodo di hashing per rimescolare il seme di numeri casuali. Per un buon caso di studio, vedi Come abbiamo imparato a imbrogliare nel poker online ( ma questo link è 404 dal 18-12-2015). Gli URL alternativi (trovati tramite una ricerca di Google sul titolo dell'articolo tra virgolette doppie) includono:
- Come abbiamo imparato a imbrogliare nel poker online & # 8212; apparentemente l'editore originale.
- Come abbiamo imparato a imbrogliare nel poker online
- Come abbiamo imparato a imbrogliare nel poker online
  nbsp &;
Il vettore è sincronizzato. Se possibile, utilizzare invece ArrayList per migliorare le prestazioni.

Quanto costa rimuovere? Perché se questo ha bisogno di riscrivere l'array in un nuovo pezzo di memoria, allora hai fatto operazioni O (5n) nella seconda versione, piuttosto che O (n) che volevi prima.

È possibile creare una matrice di valori booleani impostati su false, quindi:

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;
}

Questo approccio funziona se il tuo sottoinsieme è più piccolo della dimensione totale di un margine significativo. Man mano che queste dimensioni si avvicinano l'una all'altra (cioè 1/4 della dimensione o qualcosa del genere), si otterrebbero più collisioni su quel generatore di numeri casuali. In tal caso, farei un elenco di numeri interi delle dimensioni del tuo array più grande, quindi mescolerei quell'elenco di numeri interi e ne toglierei i primi elementi per ottenere i tuoi (non-collidi) indici. In questo modo, hai il costo di O (n) nella costruzione dell'array intero e di un'altra O (n) nello shuffle, ma nessuna collisione da un controllore interno interno e inferiore alla potenziale O (5n) che rimuove può costare.

Personalmente opterei per la tua implementazione iniziale: molto concisa. I test delle prestazioni mostreranno quanto bene si ridimensiona. Ho implementato un blocco di codice molto simile in un metodo decentemente abusato ed è sufficientemente scalato. Il codice particolare si basava su array contenenti & Gt; 10.000 elementi.

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));
}

Questo è una domanda molto simile su stackoverflow.

Per riassumere il mio preferito risposte da questa pagina (furst uno dall'utente Kyle):

O(n) soluzione:Scorrere l'elenco e la copia di un elemento (o richiamo) con probabilità (#necessaria #rimanenti).Esempio:se k = 5 e n = 100, poi si prende il primo elemento con prob 5/100.Se si copia uno, poi si sceglie il prossimo con prob 4/99;ma se non hai il primo, il prob è 5/99.
O(k log k) o o(k²):Creare un elenco ordinato di k indici (i numeri in {0, 1, ..., n-1}) scegliendo in modo casuale un numero < n, quindi in modo casuale la scelta di un numero < n-1, etc.A ogni passo, è necessario recallibrate vostra scelta per evitare le collisioni e mantenere la probabilità anche.Ad esempio, se k=5 e n=100, e la vostra prima scelta è di 43, la vostra prossima scelta è compreso nell'intervallo [0, 98], e se è >=43, quindi aggiungere 1 ad esso.Quindi, se la vostra seconda scelta è 50, quindi aggiungere 1, e si ha {43, 51}.Se la vostra scelta è di 51, si aggiunge 2 per ottenere {43, 51, 53}.

Ecco alcune pseudopython -

# 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

Sto dicendo che la complessità è O(k²) o O(k log k) perché dipende da quanto velocemente si può cercare e inserire nel contenitore per s.Se s è una lista normale, una di queste operazioni è lineare, e si ottiene k^2.Tuttavia, se siete disposti a costruire s come un albero binario bilanciato, si può uscire O(k log k) tempo.

due soluzioni non credo che appaiano qui - la corrispondenza è piuttosto lunga e contiene alcuni collegamenti, tuttavia, non penso che tutti i post si riferiscano al problema di scegliere un sottostanza di K elemetns da un set di N elementi. [Per & Quot; set & Quot ;, mi riferisco al termine matematico, ovvero tutti gli elementi appaiono una volta, l'ordine non è importante].

Sol 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--;
}

Sembra simile alla risposta di Daniel, ma in realtà è molto diverso. È del tempo di esecuzione O (k).

Un'altra soluzione è usare un po 'di matematica: consideriamo gli indici di array come Z_n e quindi possiamo scegliere casualmente 2 numeri, x che è co-primo ad n, cioè chhose gcd (x, n) = 1, e un altro, a, che è " punto iniziale < !> quot; - quindi la serie: a% n, a + x% n, a + 2 * x% n, ... a + (k-1) * x% n è una sequenza di numeri distinti (purché k <. = n)

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow