melhor maneira de escolher um subconjunto aleatório de uma coleção?

StackOverflow https://stackoverflow.com/questions/136474

Pergunta

Eu tenho um conjunto de objetos em um vetor a partir do qual eu gostaria de selecionar um subconjunto aleatório (por exemplo 100 itens voltem; escolher 5 aleatoriamente). Na minha primeira (muito precipitada) passar Eu fiz uma solução extremamente simples e talvez excessivamente inteligente: 

Vector itemsVector = getItems();

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

Enquanto isto tem a vantagem de ser simples e simpático, 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())));
}

Todas as sugestões sobre as melhores formas de tirar um subconjunto aleatório de uma coleção?

Foi útil?

Solução

Jon Bentley discute isso em qualquer 'Pearls Programação' ou 'Mais Pearls programação'. Você precisa ter cuidado com o seu processo de seleção N de M, mas acho que o código funciona correctamente apresentados. Ao invés de embaralhar aleatoriamente todos os itens, você pode fazer o shuffle aleatório única baralhar as primeiras posições N - que é uma poupança útil quando N << M

.

Knuth também discute esses algoritmos -. Acredito que seria Vol 3 "classificação e pesquisa", mas meu jogo é embalado pendente um movimento da casa, então não posso verificar formalmente que

Outras dicas

@ 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 n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Está na página 127 da Programação Pérolas por Jon Bentley e é baseado fora de implementação de Knuth.

EDIT: Eu só vi uma outra modificação 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 "... precisamos embaralhar apenas o primeiro m elementos do array ..."

Se você está tentando selecionar k elementos distintos de uma lista de n, os métodos que você deu acima será O (n) ou O (kn), porque a remoção de um elemento de um vetor causará um arraycopy para mudar tudo os elementos para baixo.

Uma vez que você está pedindo a melhor maneira, isso depende do que você está autorizado a ver com a sua lista de entrada.

Se é aceitável para modificar a lista de entrada, como em seus exemplos, então você pode simplesmente trocar k elementos aleatórios para o início da lista e devolvê-los em O (k) momento como este: 

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 a lista deve acabar no mesmo estado em que começou, você pode acompanhar as posições que você trocados, e, em seguida, retornar a lista ao seu estado original depois de copiar o seu sub-lista selecionada. Isto é ainda uma solução de S (k).

Se, no entanto, você não pode modificar a lista de entrada em tudo e k é muito menos do que n (como 5 100), seria muito melhor para não remover elementos selecionados de cada vez, mas simplesmente selecionar cada elemento, e se você já teve uma duplicata, jogá-lo fora e volte a seleccionar. Isto lhe dará O (kn / (n-k)), que ainda está perto de O (k) quando n domina k. (Por exemplo, se K é menor do que n / 2, em seguida, reduz a O (k)).

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

Como outros já mencionado, se você estiver dependendo forte aleatoriedade onde cada sublista é possível (e imparcial), você definitivamente precisa de algo mais forte do que java.util.Random. Veja java.security.SecureRandom.

Eu escrevi uma aplicação eficaz do presente algumas semanas atrás. É em C #, mas a tradução para Java é trivial (essencialmente o mesmo código). O lado positivo é que também é completamente imparcial (que algumas das respostas existentes não são) - uma forma de teste que é aqui .

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

Seu segunda solução de usar aleatório para escolher elemento parece som, no entanto:

Quanto custa remover? Porque se que as necessidades de reescrever a matriz para um novo pedaço de memória, então você já fez O (5n) operações na segunda versão, em vez do O (n) que queria antes.

Você pode criar uma matriz de booleanos definido como false, e depois: 

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

Esta abordagem funciona se o seu subconjunto é menor do que seu tamanho total por uma margem significativa. Como esses tamanhos ficar perto um do outro (ou seja, 1/4 do tamanho ou algo assim), você terá mais colisões em que o gerador de números aleatórios. Nesse caso, eu faria uma lista de inteiros do tamanho de sua matriz maior, e então embaralhar essa lista de números inteiros, e retirar os primeiros elementos de que para obter o seu (não-colisão) indeces. Dessa forma, você tem o custo de O (n) na construção da matriz de inteiros, e outro O (n) na confusão, mas sem colisões de um interno ao verificador e menor que o O potencial (5n) que remove pode custar.

eu optar pessoal para sua implementação inicial: muito conciso. O teste de desempenho vai mostrar o quão bem ele pode ser expandido. Eu tenho implementado um bloco muito semelhante de código em um método decentemente abusado e dimensionado suficientemente. O código particular invocada matrizes contendo> 10.000 itens também. 

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

Este é uma questão muito semelhante no stackoverflow.

Para resumir as minhas respostas favoritas a partir dessa página (um Furst do usuário Kyle):

  • O (n) solução : Iterate através de sua lista, e copiar a um elemento (ou a eles de referência) com probabilidade (#needed / #remaining). Exemplo: se k = 5 e n ??= 100, depois de tomar o primeiro elemento com prov 5/100. Se você copiar esse, então você escolher o próximo com prov 4/99; mas se você não tomar o primeiro, prob é 5/99.
  • O (k log k) ou O (k 2 ) : construir uma lista ordenada de índices k (números em {0, 1, ..., n -1}) escolhendo aleatoriamente um número = 43, então você adiciona 1 a ela. Então, se sua segunda opção é 50, então você adiciona 1 a ela, e você tem {43, 51}. Se a sua próxima escolha é 51, você adiciona 2 a ele para obter {43, 51, 53}.

Aqui estão algumas 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

Eu estou dizendo que a complexidade de tempo é O (k 2 ) ou O (log k k) porque depende de quão rápido você pode pesquisar e inserir o recipiente para s. Se s é uma lista normal, uma dessas operações é linear, e você começa k ^ 2. No entanto, se você estiver disposto a construir s como uma árvore binária equilibrada, você pode sair tempo O (k log k).

duas soluções não creio que aparecem aqui - os corresponde é bastante longa, e contém alguns links, no entanto, eu não acho que todas as mensagens relacionadas ao problema de escolher um subst de K elemetns fora de um conjunto de N elementos. [Por "set", refiro-me ao termo matemático, isto é, todos os elementos aparecer uma vez, a ordem não é 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--;
}

Este é semelhante à resposta daniel deu, mas na verdade é muito diferente. É de O (k) tempo de execução.

Outra solução é usar um pouco de matemática: considerar os índices de matriz como Z_n e por isso, pode escolher aleatoriamente 2 números, X, que é co-primo a n, ou seja, chhose GCD (x, n) = 1, e o outro, um, o qual é "ponto de partida" -, em seguida, a série :. um% n, a + x% N, a + 2 * x% n, ... a + (k-1) * x% n é uma sequência de números distintos (enquanto k <= n)

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top