melhor maneira de escolher um subconjunto random de uma coleção?

Eu tenho um conjunto de objects em um vetor do qual eu gostaria de selecionar um subconjunto random (por exemplo, 100 itens voltando; escolha 5 aleatoriamente). Na minha primeira passagem (muito apressada) eu fiz uma solução extremamente simples e talvez excessivamente inteligente:

Vector itemsVector = getItems(); Collections.shuffle(itemsVector); itemsVector.setSize(5); 

Enquanto isso tem a vantagem de ser agradável e simples, eu suspeito que não vai escalar muito bem, ou seja, Collections.shuffle () deve ser O (n), pelo menos. Minha alternativa menos inteligente é

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

Alguma sugestão sobre melhores formas de extrair um subconjunto random de uma coleção?

    Jon Bentley discute isso em ‘Programming Pearls’ ou ‘More Programming Pearls’. Você precisa ter cuidado com o processo de seleção do N de M, mas acho que o código mostrado funciona corretamente. Em vez de embaralhar aleatoriamente todos os itens, você pode fazer o shuffle random apenas embaralhando as primeiras N posições – o que é uma economia útil quando N << M.

    Knuth também discute esses algoritmos – acredito que seria o Vol 3 “Classificando e Pesquisando”, mas meu conjunto está lotado enquanto se aguarda uma mudança de casa, então não posso verificar isso formalmente.

    @ Jonathan,

    Eu acredito que esta é a solução que você está falando:

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

    Está na página 127 de Programming Pearls, de Jon Bentley, e baseia-se na implementação de Knuth.

    EDIT: Acabei de ver uma modificação adicional na página 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"; } 

    Isto é baseado na idéia de que "... nós precisamos embaralhar apenas os primeiros m elementos da matriz ..."

    Se você está tentando selecionar k elementos distintos de uma lista de n, os methods que você deu acima serão O (n) ou O (kn), porque remover um elemento de um Vector fará com que uma arraycopy mude todos os elementos para baixo .

    Como você está pedindo a melhor maneira, depende do que você pode fazer com sua lista de input.

    Se for aceitável modificar a lista de input, como em seus exemplos, você pode simplesmente trocar elementos randoms para o início da lista e retorná-los no tempo O (k) como este:

     public static  List getRandomSubList(List 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 a lista tiver que terminar no mesmo estado em que começou, você poderá acompanhar as posições que você trocou e, em seguida, retornar a lista ao seu estado original depois de copiar a sub-lista selecionada. Esta ainda é uma solução O (k).

    Se, no entanto, você não puder modificar a lista de input e k for muito menor que n (como 5 de 100), seria muito melhor não remover os elementos selecionados de cada vez, mas simplesmente selecionar cada elemento, e se você conseguir uma duplicata, jogue-a fora e selecione novamente. Isto lhe dará O (kn / (nk)) que ainda está próximo de O (k) quando n domina k. (Por exemplo, se k é menor que n / 2, então reduz para O (k)).

    Se k não for dominado por n, e você não puder modificar a lista, você pode copiar sua lista original e usar sua primeira solução, porque O (n) será tão bom quanto O (k).

    Como outros notaram, se você estiver dependendo da aleatoriedade forte, onde cada sublist é possível (e imparcial), você definitivamente precisará de algo mais forte que java.util.Random . Veja java.security.SecureRandom .

    Eu escrevi uma implementação eficiente disso algumas semanas atrás. Está em C #, mas a tradução para Java é trivial (essencialmente o mesmo código). O lado positivo é que também é completamente imparcial (o que algumas das respostas existentes não são) – uma maneira de testar isso aqui .

    É baseado em uma implementação de Durstenfeld do shuffle de Fisher-Yates.

    Sua segunda solução de usar o Random para escolher o elemento parece boa, no entanto:

    • Dependendo de quão sensíveis são os seus dados, sugiro usar algum tipo de método de hashing para misturar a semente numérica aleatória. Para um bom estudo de caso, veja Como aprendemos a trapacear no Poker Online (mas esse link é 404 de 2015-12-18). URLs alternativos (encontrados por meio de uma pesquisa do Google no título do artigo entre aspas duplas) incluem:

      • Como aprendemos a trapacear no Poker Online – aparentemente o editor original.
      • Como aprendemos a trapacear no poker online
      • Como aprendemos a trapacear no poker online
    • Vector está sincronizado. Se possível, use ArrayList para melhorar o desempenho.

    Quanto custa remover o custo? Porque se isso precisa rewrite o array para um novo pedaço de memory, então você fez operações O (5n) na segunda versão, ao invés do O (n) que você queria antes.

    Você pode criar uma matriz de booleanos definida como false e, em seguida:

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

    Essa abordagem funciona se seu subconjunto for menor que seu tamanho total por uma margem significativa. À medida que esses tamanhos se aproximam um do outro (ou seja, 1/4 do tamanho ou algo assim), você teria mais colisões naquele gerador de números randoms. Nesse caso, eu faria uma lista de números inteiros do tamanho de sua matriz maior, e depois embaralhe essa lista de inteiros, e retire os primeiros elementos para obter suas partes (não-colidindo). Dessa forma, você tem o custo de O (n) na construção do array inteiro e outro O (n) no shuffle, mas nenhuma colisão de um verificador interno enquanto menor que o potencial O (5n) que remove pode custar.

    Eu pessoalmente optaria por sua implementação inicial: muito conciso. O teste de desempenho mostrará quão bem ele é dimensionado. Eu implementei um bloco de código muito semelhante em um método decentemente abusado e dimensionei o suficiente. O código específico contava com matrizes contendo> 10.000 itens também.

     Set s = new HashSet() // 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)); } 

    Esta é uma pergunta muito parecida no stackoverflow.

    Para resumir minhas respostas favoritas daquela página (a primeira do usuário Kyle):

    • O (n) solução : Iterar através de sua lista e copiar um elemento (ou referência a ele) com probabilidade (#needed / #remaining). Exemplo: se k = 5 e n ​​= 100, então você pega o primeiro elemento com prob 5/100. Se você copiar aquele, então você escolhe o próximo com prob 4/99; mas se você não pegou o primeiro, o prob é 5/99.
    • O (k log k) ou O (k 2 ) : Construa uma lista ordenada de k índices (números em {0, 1, …, n-1}) escolhendo aleatoriamente um número = 43, você adicionará 1 a ela. Portanto, se sua segunda opção for 50, você adicionará 1 a ela e terá {43, 51}. Se sua próxima escolha for 51, você adicionará 2 a ela para obter {43, 51, 53}.

    Aqui está algum 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, ni) # May be 0, must be < ni 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 

    Estou dizendo que a complexidade do tempo é O (k 2 ) ou O (k log k) porque depende da rapidez com que você pode pesquisar e inserir no seu contêiner por s. Se s é uma lista normal, uma dessas operações é linear e você obtém k ^ 2. No entanto, se você estiver disposto a construir s como uma tree binária balanceada, você poderá obter o tempo O (k log k).

    duas soluções eu não acho que aparecem aqui – o correspondente é bastante longo, e contém alguns links, no entanto, eu não acho que todos os posts se relacionam com o problema de escolher um subst de K elemetns de um conjunto de N elementos . [Por “set”, refiro-me ao termo matemático, ou seja, todos os elementos aparecem uma vez, a ordem não é importante].

    Sol 1:

     //Assume the set is given as an array: Object[] set ....; for(int i=0;i 

    Isso parece semelhante à resposta que Daniel deu, mas na verdade é muito diferente. É de O (k) tempo de execução.

    Outra solução é usar alguma matemática: considere os índices da matriz como Z_n e assim podemos escolher aleatoriamente 2 números, x que é co-primo de n, ou seja, chhose gcd (x, n) = 1 e outro, a, que é "ponto de partida" - então a série: a% n, a + x% n, a + 2 * x% n, ... a + (k-1) * x% n é uma seqüência de números distintos (contanto que k <= n).