@Test public void reservoirSamplingMultipleElements() { final List<Integer> a = Arrays.asList(0, 1); final int[] counts = new int[a.size()]; for (int i = 0; i < 10000000; i++) { final List<Integer> rrr = ReservoirSamplingMultipleItems.reservoirSampling(a.iterator(), 1); counts[rrr.get(0)]++; } System.out.println(Arrays.toString(counts)); }
public static <T> List<T> reservoirSampling(final Iterator<T> stream, final int s) { final List<T> R = new ArrayList<>(s); int k = 1; while (stream.hasNext() && k <= s) { final T nextElement = stream.next(); R.add(nextElement); k++; } while (stream.hasNext()) { final T nextElement = stream.next(); final double pOfReplacement = (double) s / (double) k; final double randomNumber = ThreadLocalRandom.current().nextDouble(); if (randomNumber < pOfReplacement) { final int randomIndex = ThreadLocalRandom.current().nextInt(s); R.set(randomIndex, nextElement); } k++; } return R; }
ReservoirSamplingMultipleItems { public static <T> List<T> reservoirSampling(final Iterator<T> stream, final int s) { final List<T> R = new ArrayList<>(s); int k = 1; while (stream.hasNext() && k <= s) { final T nextElement = stream.next(); R.add(nextElement); k++; } while (stream.hasNext()) { final T nextElement = stream.next(); final double pOfReplacement = (double) s / (double) k; final double randomNumber = ThreadLocalRandom.current().nextDouble(); if (randomNumber < pOfReplacement) { final int randomIndex = ThreadLocalRandom.current().nextInt(s); R.set(randomIndex, nextElement); } k++; } return R; } }
ReservoirSamplingMultipleItems { public static <T> List<T> reservoirSampling(final Iterator<T> stream, final int s) { final List<T> R = new ArrayList<>(s); int k = 1; while (stream.hasNext() && k <= s) { final T nextElement = stream.next(); R.add(nextElement); k++; } while (stream.hasNext()) { final T nextElement = stream.next(); final double pOfReplacement = (double) s / (double) k; final double randomNumber = ThreadLocalRandom.current().nextDouble(); if (randomNumber < pOfReplacement) { final int randomIndex = ThreadLocalRandom.current().nextInt(s); R.set(randomIndex, nextElement); } k++; } return R; }  }
ReservoirSamplingMultipleItems { public static <T> List<T> reservoirSampling(final Iterator<T> stream, final int s) { final List<T> R = new ArrayList<>(s); int k = 1; while (stream.hasNext() && k <= s) { final T nextElement = stream.next(); R.add(nextElement); k++; } while (stream.hasNext()) { final T nextElement = stream.next(); final double pOfReplacement = (double) s / (double) k; final double randomNumber = ThreadLocalRandom.current().nextDouble(); if (randomNumber < pOfReplacement) { final int randomIndex = ThreadLocalRandom.current().nextInt(s); R.set(randomIndex, nextElement); } k++; } return R; }  static List<T> reservoirSampling(final Iterator<T> stream, final int s); }
ReservoirSamplingMultipleItems { public static <T> List<T> reservoirSampling(final Iterator<T> stream, final int s) { final List<T> R = new ArrayList<>(s); int k = 1; while (stream.hasNext() && k <= s) { final T nextElement = stream.next(); R.add(nextElement); k++; } while (stream.hasNext()) { final T nextElement = stream.next(); final double pOfReplacement = (double) s / (double) k; final double randomNumber = ThreadLocalRandom.current().nextDouble(); if (randomNumber < pOfReplacement) { final int randomIndex = ThreadLocalRandom.current().nextInt(s); R.set(randomIndex, nextElement); } k++; } return R; }  static List<T> reservoirSampling(final Iterator<T> stream, final int s);  }