TapeSampling { public Iterator<T> getSamples() { return new AbstractIterator<T>() { int sampled = 0; int seen = 0; @Override protected T computeNext() { if (sampled == k) { return endOfData(); } while (true) { Preconditions.checkArgument(input.hasNext(), "Not enough input items provided. Declared: " + N + "; got " + seen + "; sampled: " + sampled); T i = input.next(); int r = rGen.nextInt(N - seen) + 1; seen++; if (r <= k - sampled) { sampled++; return i; } } } }; } TapeSampling(final Random rGen, final Iterator<T> input, final int N, final int k); Iterator<T> getSamples();  }
@Test public void testWithHighestRandom() { final int start = 10; final int end = 30; final int k = 10; final Random r = new Random() { @Override public int nextInt(int i) { return i - 1; } }; List<Integer> input = range(start, end); TapeSampling<Integer> res = new TapeSampling<>(r, input.iterator(), input.size(), k); List<Integer> samples = newArrayList(res.getSamples()); List<Integer> expected = range(end - k + 1, end); assertEquals(expected, samples); }
@Test public void testWithLowestRandom() { final int start = 10; final int end = 30; final int k = 10; final Random r = new Random() { @Override public int nextInt(int i) { return 0; } }; List<Integer> input = range(start, end); TapeSampling<Integer> res = new TapeSampling<>(r, input.iterator(), input.size(), k); List<Integer> samples = newArrayList(res.getSamples()); List<Integer> expected = range(start, start + k - 1); assertEquals(expected, samples); }
@Test public void allItemsWhenKisN() { final int start = 11; final int end = 20; final int k = 10; final Random r = new Random(); List<Integer> input = range(start, end); TapeSampling<Integer> res = new TapeSampling<>(r, input.iterator(), input.size(), k); List<Integer> samples = newArrayList(res.getSamples()); List<Integer> expected = input; assertEquals(expected, samples); }
@Test public void sampleExactlyK() { final int start = 11; final int end = 1000; final int k = 10; final Random r = new Random(); List<Integer> input = range(start, end); TapeSampling<Integer> res = new TapeSampling<>(r, input.iterator(), input.size(), k); assertEquals("Must sample exactly " + k + " items", k, Iterators.size(res.getSamples())); }
@Test public void sampleBias() { int size = 200; int k = 20; int[] counts = new int[size]; Random r = new Random(42); int testCount = 100 * size; for (int i = 0; i < testCount; i++) { List<Integer> input = range(0, size - 1); TapeSampling<Integer> res = new TapeSampling<>(r, input.iterator(), input.size(), k); Iterator<Integer> it = res.getSamples(); while (it.hasNext()) { counts[it.next()]++; } } int expectedCount = testCount / (size / k); for (int i = 0; i < size; i++) { assertTrue(counts[i] > expectedCount* 0.9 && counts[i] < expectedCount * 1.1); } }