Eu tenho um mapa de itens com alguma distribuição de probabilidade:

Map<SingleObjectiveItem, Double> itemsDistribution;

Dado um certom Eu tenho que gerar umSet dom elementos amostrados da distribuição acima.

A partir de agora eu estava usando a maneira ingênua de fazê-lo:

while(mySet.size < m)
   mySet.add(getNextSample(itemsDistribution));

ogetNextSample(...) O método busca um objeto na distribuição de acordo com sua probabilidade. Agora, comom aumenta o desempenho sofre severamente. Param = 500 eitemsDistribution.size() = 1000 elementos, há muita discussão e a função permanece no loop while por muito tempo. Gere 1000 desses conjuntos e você terá um aplicativo que rastreia.

Existe uma maneira mais eficiente de gerar um conjunto exclusivo de números aleatórios com uma distribuição "predefinida"? A maioria das técnicas de embaralhamento de coleções e similares são uniformemente aleatórias. Qual seria uma boa maneira de resolver isso?

ATUALIZAR: O loop chamarágetNextSample(...) "finalmente"1 + 2 + 3 + ... + m = m(m+1)/2 vezes. Ou seja, na primeira execução, definitivamente obteremos uma amostra para o conjunto. A segunda iteração, pode ser chamada pelo menos duas vezes e assim por diante. E segetNextSample é seqüencial por natureza, ou seja, passa por toda a distribuição cumulativa para encontrar a amostra, então a complexidade do tempo de execução do loop é pelo menos:n*m(m+1)/2, 'n' é o número de elementos na distribuição. E sem = cn; 0<c<=1 então o loop é pelo menos Sigma (n ^ 3). E esse também é o limite inferior!

Se substituirmos a pesquisa sequencial por pesquisa binária, a complexidade seria pelo menos Sigma (log n * n ^ 2). Eficiente, mas pode não ser por uma grande margem.

Além disso, a remoção da distribuição não é possível, pois eu chamo o loop acimak vezes, para gerark tais conjuntos. Esses conjuntos fazem parte de uma 'programação' aleatória de itens. Daí um 'conjunto' de itens.