Un modo migliore per creare campioni

Question

Un modo migliore per creare campioni

#1 da (1 voti)

0

Ho fatto questo pezzo di codice per creare esempi di bernulli, ma penso che sia un algoritmo così pesante perché ogni volta che chiamo questa funzione ricorsiva creo un nuovo vettore che viene passato ad esso. C'è un modo per rendere questo algoritmo più veloce?

Ecco l'algoritmo e la descrizione:

Come già detto, questa funzione crea ricorsivamente i campioni di bernulli. Se n , ovvero il numero di elementi che devono essere trovati, è uguale a 0, stampo il campione.

Altrimenti al campione che viene passato aggiungo ogni elemento della popolazione (devo creare un vettore per ognuno di questi nuovi campioni), e chiamo la funzione con questo nuovo esempio en (il numero di elementi da trovato) decrementato.

private static void distribuzioneBernoulli(int n, Vector<Float> population, Vector<Float> sample){
    // exit condition, when n equals 0 the fuction doesn't self-calls
    if(n==0){
        JOptionPane.ShowMessageDialog(null, campione);
    }

    // Every element of the population is added to the sample,
    // and is recalled the function
    for(int x = 0; x < population.size(); x++){
        Vector<Float> aggiunta = new Vector<Float>(sample);
        aggiunta.add(population.elementAt(x));
        distribuzioneBernoulli(n-1, population, aggiunta);
    }
}

recursion java algorithms sample

posta giacomotb 30.11.2013 - 10:20

fonte

1 risposta

Leggi altre domande sui tag recursion java algorithms sample

Quale potrebbe essere il livello del modello quando si utilizzano Web-Services e nessun database in Django? Tabella degli schemi per i token di integrazione multipla

score 1 · Answer 1

Non stai calcolando alcun campione. Invece, stai creando tutte le possibili sequenze dagli elementi su population di lunghezza n . Considera population = {1, 1, 2, 3} e n = 3 . Quindi produrrai:

1 1 1    1 1 1    2 1 1    3 1 1
1 1 1    1 1 1    2 1 1    3 1 1
1 1 2    1 1 2    2 1 2    3 1 2
1 1 3    1 1 3    2 1 3    3 1 3
1 1 1    1 1 1    2 1 1    3 1 1
1 1 1    1 1 1    2 1 1    3 1 1
1 1 2    1 1 2    2 1 2    3 1 2
1 1 3    1 1 3    2 1 3    3 1 3
1 2 1    1 2 1    2 2 1    3 2 1
1 2 1    1 2 1    2 2 1    3 2 1
1 2 2    1 2 2    2 2 2    3 2 2
1 2 3    1 2 3    2 2 3    3 2 3
1 3 1    1 3 1    2 3 1    3 3 1
1 3 1    1 3 1    2 3 1    3 3 1
1 3 2    1 3 2    2 3 2    3 3 2
1 3 3    1 3 3    2 3 3    3 3 3

Il numero di sequenze è population.sizeⁿ (qui: 4³ = 64).

Un campione di Bernoulli restituirebbe uno di queste sequenze con uguale probabilità.

Se vuoi restituire un campione di Bernoulli, allora il codice seguente sarebbe meglio:

static <T> List<T> bernoulliSample(int size, List<T> population, Random rng) {
  assert population != null;
  assert rng != null;
  List<T> sequence = new ArrayList<T>(size);
  for (int i = 0; i < size; i++) {
    sequence.add(population.get(rng.nextInt(population.size())));
  }
  return sequence;
}

Se vuoi costruire tutte le possibili sequenze (≠ permutazioni), allora possiamo pre-allocare una struttura dati che contiene tutte le sequenze. Tuttavia, potrebbe essere preferibile restituire un oggetto Iterator o Iterable che calcola le sequenze in modo pigramente.

Eager solution

static <T> List<List<T>> allSequences(int size, List<T> population) {
  assert population != null;
  assert size >= 0;
  int sequenceCount = ipow(population.size(), n); // see http://stackoverflow.com/a/10517609/1521179

  List<List<T>> sequences = new ArrayList<List<T>>(sequenceCount);

  for (int i = 0; i < sequenceCount; i++) {
    sequences.add(sequenceAt(i, population));
  }

  return sequences;
}

Ora cos'è sequenceAt ? Ogni intero nell'intervallo [0, sequenceCount) può essere tradotto in una sequenza specifica, proprio come i numeri decimali possono essere tradotti in ottale. La differenza qui è che al posto delle cifre, abbiamo elementi in population .

private static <T> List<T> sequenceAt(int size, int n, List<T> population) {
  List<T> sequence = new ArrayList<T>(size);

  for (int i : asBase(size, n, population.size())) {
    sequence.add(population.get(i));
  }

  return sequence;
}

Tieni presente che non vengono copiati attorno agli elenchi di semi-completati qui e non facciamo affidamento sulla ricorsione.

Questo metodo qui trasformerà un intero in un elenco di cifre in un'altra base:

private static int[] asBase(int size, int n, int base) {
  int digits[] = new int[size];

  for (int i = size - 1, rem = n; i >= 0; i--, rem /= base) {
    digits[i] = rem % base;
  }

  return digits;
}

Soluzione pigra

Questo può riutilizzare i metodi di supporto da sopra la soluzione.

class Sequences<T> implements Iterable<List<T>> {

  private final List<T> population;
  private final int     count;
  private final int     size;

  public Sequences(int size, List<T> population) {
    assert population != null;
    this.population = population;

    assert size >= 0;
    this.size = size:

    this.count = ipow(population.size(), size); // see http://stackoverflow.com/a/10517609/1521179
  }

  public Iterator<List<T>> iterator() {
    return new Iterator<List<T>>() {
      int cursor = 0;

      public boolean hasNext() {
        return cursor < count;
      }

      public List<T> next() {
        if (!hasNext()) throw new NoSuchElementException();
        return sequenceAt(size, cursor++, population);
      }

      public void remove() {
        throw new UnsupportedOperationException();
      }

      // sequenceAt, asBase
    };
  }

  // ipow

}

Ora potremmo stampare tutte le sequenze come

for (List<Integer> sequence : new Sequences<Integer>(3, Arrays.asList(1, 1, 2, 3))) {
    for (int i : sequence) System.out.print(i + " ");
    System.out.println();
}

Con entrambe queste soluzioni possiamo saltare l'indirezione dalla traduzione di un numero a una sequenza specifica. Invece, potremmo mantenere una serie di indici direttamente e aggiornarli dopo ogni sequenza. Una soluzione del genere potrebbe essere più efficiente, poiché comporta un numero inferiore di allocazioni.