0

I've done this piece of code for creating bernulli samples, but I think that it is a so heavy algorithm because every time I call this recursive function I create a new vector that is passed to it. Is there a way for making this algorithm faster?

Here is the algorithm and the description:

As already said, this function creates bernulli samples recursively. If n, that is the number of elements that should be found, is equals 0 I print the sample.

Else to the sample that is passed I add every element of the population (I have to create a vector for everyone of this new samples), and I call the function with this new sample and n(the number of element to be found) decremented.

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

You are not calculating any samples. Instead, you are creating all possible sequences out of the elements on population of length n. Consider population = {1, 1, 2, 3} and n = 3. Then you would produce:

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

The number of sequences is population.sizen (here: 4³ = 64).

A Bernoulli sample would return one of these sequences with equal probability.

If you want to return a Bernoulli sample, then the following code would be better:

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

If you want to construct all possible sequences (≠ permutations), then we can pre-allocate a data structure that holds all sequences. However, it might be better to return an Iterator or Iterable object that computes the sequences lazily.

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

Now what is sequenceAt? Each integer in the range [0, sequenceCount) can be translated into a specific sequence, much like decimal numbers can be translated into octal. The difference here is that instead of digits, we have items 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;
}

Notice that we don't copy around any half-finished lists here, and we don't rely on recursion.

This method here will transform an integer into a list of digits in another 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;
}

Lazy solution

This can reuse the helper methods from above solution.

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

}

Now we could print out all sequences like

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

With both of these solutions we could skip the indirection from translating a number to a specific sequence. Instead, we could maintain an array of indices directly and update it after each sequence. Such a solution could be more efficient, as it results in fewer allocations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.