Selecionando eficientemente um conjunto de elementos aleatórios de uma lista vinculada

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

Pergunta

Digamos que eu tenha uma lista vinculada de números de comprimento N. N é muito grande e não sei de antemão o valor exato de N.

Como posso escrever com mais eficiência uma função que retornará k completamente Números aleatórios da lista?

Foi útil?

Solução

Existe um algoritmo muito bom e eficiente para isso usando um método chamado amostragem de reservatório.

Deixe-me começar dando-lhe o seu história:

Knuth chama esse algoritmo de R na p.144 de sua edição de 1997 de Algoritmos Seminuméricos (volume 2 de The Art of Computer Programming), e fornece algum código para ele lá.Knuth atribui o algoritmo a Alan G.Homem da Água.Apesar de uma longa pesquisa, não consegui encontrar o documento original de Waterman, se existir, e pode ser por isso que você verá Knuth com mais frequência citado como a fonte desse algoritmo.

McLeod e Bellhouse, 1983 (1) fornece uma discussão mais completa do que Knuth, bem como a primeira prova publicada (que eu saiba) de que o algoritmo funciona.

Vitter 1985 (2) analisa o Algoritmo R e, em seguida, apresenta três algoritmos adicionais que fornecem a mesma saída, mas com uma diferença.Em vez de optar por incluir ou ignorar cada elemento recebido, seu algoritmo predetermina o número de elementos recebidos a serem ignorados.Em seus testes (que, reconhecidamente, estão desatualizados agora), isso diminuiu drasticamente o tempo de execução, evitando a geração de números aleatórios e comparações em cada número recebido.

Em pseudo-código o algoritmo é:

Let R be the result array of size s
Let I be an input queue

> Fill the reservoir array
for j in the range [1,s]:
  R[j]=I.pop()

elements_seen=s
while I is not empty:
  elements_seen+=1
  j=random(1,elements_seen)       > This is inclusive
  if j<=s:
    R[j]=I.pop()
  else:
    I.pop()

Observe que escrevi especificamente o código para evitar especificar o tamanho da entrada.Essa é uma das propriedades interessantes deste algoritmo:você pode executá-lo sem precisar saber o tamanho da entrada de antemão e ainda garante que cada elemento que você encontrar tem uma probabilidade igual de acabar em R (ou seja, não há preconceito).Além disso, R contém uma amostra justa e representativa dos elementos que o algoritmo considerou em todos os momentos.Isso significa que você pode usar isso como um algoritmo on-line.

Por que isso funciona?

McLeod e Bellhouse (1983) fornecem uma prova usando a matemática das combinações.É bonito, mas seria um pouco difícil reconstruí-lo aqui.Portanto, gerei uma prova alternativa que é mais fácil de explicar.

Prosseguimos através da prova por indução.

Digamos que queremos gerar um conjunto de s elementos e que já vimos n>s elementos.

Vamos supor que nosso atual s cada elemento já foi escolhido com probabilidade s/n.

Pela definição do algoritmo, escolhemos o elemento n+1 com probabilidade s/(n+1).

Cada elemento que já faz parte do nosso conjunto de resultados tem uma probabilidade 1/s de ser substituído.

A probabilidade de que um elemento do n-o conjunto de resultados visto é substituído no n+1-o conjunto de resultados visto é, portanto (1/s)*s/(n+1)=1/(n+1).Por outro lado, a probabilidade de um elemento não ser substituído é 1-1/(n+1)=n/(n+1).

Assim, o n+1-o conjunto de resultados visto contém um elemento se fizer parte do n-viu o conjunto de resultados e não foi substituído --- esta probabilidade é (s/n)*n/(n+1)=s/(n+1)---ou se o elemento foi escolhido---com probabilidade s/(n+1).

A definição do algoritmo nos diz que o primeiro s elementos são incluídos automaticamente como o primeiro n=s membros do conjunto de resultados.Portanto, o n-seen conjunto de resultados inclui cada elemento com s/n (=1) probabilidade nos dando o caso base necessário para a indução.

Referências

  1. McLeod, A.Ian e David R.Campanário."Um algoritmo conveniente para desenhar uma amostra aleatória simples". Jornal da Sociedade Estatística Real.Série C (Estatística Aplicada) 32.2 (1983):182-184.(Link)

  2. Vitter, Jeffrey S."Amostragem aleatória com um reservatório". Transações da ACM em software matemático (TOMS) 11.1 (1985):37-57.(Link)

Outras dicas

Isso é chamado de Amostragem de Reservatórios problema.A solução simples é atribuir um número aleatório a cada elemento da lista conforme você a vê e, em seguida, manter os k elementos superiores (ou inferiores) ordenados pelo número aleatório.

Eu sugeriria:Primeiro encontre seus k números aleatórios.Classifique-os.Em seguida, percorra a lista vinculada e seus números aleatórios uma vez.

Se de alguma forma você não sabe o comprimento da sua lista vinculada (como?), você pode pegar o primeiro k em uma matriz e, em seguida, para o nó r, gerar um número aleatório em [0, r) e, se for menor que k, substitua o enésimo item da matriz.(Não estou totalmente convencido de que isso não seja tendencioso ...)

Fora isso:"Se eu fosse você, não começaria daqui." Você tem certeza de que a lista vinculada é adequada para o seu problema?Não existe uma estrutura de dados melhor, como uma boa e velha lista de matrizes planas.

Se você não souber o tamanho da lista, terá que percorrê-la completamente para garantir escolhas aleatórias.O método que usei neste caso é o descrito por Tom Hawtin (54070).Ao percorrer a lista você mantém k elementos que formam sua seleção aleatória até aquele ponto.(Inicialmente você apenas adiciona o primeiro k elementos que você encontra.) Então, com probabilidade k/i, você substitui um elemento aleatório de sua seleção pelo io elemento da lista (ou seja,o elemento em que você está, naquele momento).

É fácil mostrar que isso resulta em uma seleção aleatória.Depois de ver m elementos (m > k), temos que cada um dos primeiros m os elementos da lista fazem parte de sua seleção aleatória com probabilidade k/m.Que isso inicialmente seja válido é trivial.Então para cada elemento m+1, você o coloca em sua seleção (substituindo um elemento aleatório) com probabilidade k/(m+1).Agora você precisa mostrar que todos os outros elementos também têm probabilidade k/(m+1) de ser selecionado.Temos que a probabilidade é k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (ou seja,probabilidade de esse elemento estar na lista vezes a probabilidade de ele ainda estar lá).Com o cálculo você pode mostrar diretamente que isso é igual a k/(m+1).

Bem, você precisa saber o que N é pelo menos em tempo de execução, mesmo que isso envolva fazer uma passagem extra pela lista para contá-los.O algoritmo mais simples para fazer isso é simplesmente escolher um número aleatório em N e remover esse item, repetido k vezes.Ou, se for permitido devolver números repetidos, não remova o item.

A menos que você tenha um N MUITO grande e requisitos de desempenho muito rigorosos, este algoritmo é executado com O(N*k) complexidade, o que deve ser aceitável.

Editar:Deixa pra lá, o método de Tom Hawtin é muito melhor.Selecione os números aleatórios primeiro e depois percorra a lista uma vez.A mesma complexidade teórica, eu acho, mas um tempo de execução esperado muito melhor.

Por que você não pode simplesmente fazer algo como

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

Tenho certeza de que você não quis dizer algo tão simples, então pode especificar mais?

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