Page Extraction for Pagination in Java - Sort vs Heap vs Heapify

Bench.java

package bench;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.IntSummaryStatistics;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.IntStream;

public class Bench {

    public static void main(String[] args) {
        test();
        int n = 10_000;
        int from = 0;
        int count = 25;
        int iterations = 5;
        int pages = 10;
        repeat("sort", new SortExtractor<>(), n, from, count, iterations, pages);
        repeat("heap", new HeapExtractor<>(false), n, from, count, iterations, pages);
        repeat("heapify", new HeapExtractor<>(true), n, from, count, iterations, pages);
    }

    static void test() {
        test(new SortExtractor<>());
        test(new HeapExtractor<>(false));
        test(new HeapExtractor<>(true));
    }

    static void test(Extractor<Integer> e) {
        List<Integer> elements = List.of(3, 2, 1, 5, 4);
        assert List.of(1).equals(e.extract(elements, Integer::compareTo, 0, 1));
        assert List.of(5).equals(e.extract(elements, Integer::compareTo, 4, 1));
        assert List.of(1, 2, 3, 4, 5).equals(e.extract(elements, Integer::compareTo, 0, 5));
        assert List.of(4, 5).equals(e.extract(elements, Integer::compareTo, 3, 2));
        assert List.of(3).equals(e.extract(elements, Integer::compareTo, 2, 1));
    }

    static void repeat(String label, Extractor<Integer> extractor, int n, int from, int count, int iterations, int pages) {
        System.out.printf("[%s]\n", label);
        for (int i = 0; i < pages; i++) {
            repeat(extractor, n, from + i * count, count, iterations);
        }
    }

    static void repeat(Extractor<Integer> extractor, int n, int from, int count, int iterations) {
        IntSummaryStatistics stats = IntStream.range(0, iterations)
                .map(x -> run(extractor, n, from, count))
                .summaryStatistics();
        System.out.printf("from=%d, count=%d, iters=%d, min=%d, max=%d, avg=%d\n",
                from, count, iterations, stats.getMin(), stats.getMax(), (int) stats.getAverage());
    }

    static int run(Extractor<Integer> extractor, int n, int from, int count) {
        Random random = new Random();
        List<Integer> elements = random.ints(n).boxed().toList();
        IntCmp c = new IntCmp();
        extractor.extract(elements, c, from, count);
        return c.count;
    }

    interface Extractor<T> {
        List<T> extract(List<T> elems, Comparator<T> comparator, int from, int count);
    }

    static class SortExtractor<T> implements Extractor<T> {
        @Override
        public List<T> extract(List<T> elems, Comparator<T> comparator, int from, int count) {
            List<T> copy = new ArrayList<>(elems);
            copy.sort(comparator);
            return copy.subList(from, from + count);
        }
    }

    record HeapExtractor<T>(boolean heapify) implements Extractor<T> {
        @Override
        public List<T> extract(List<T> elems, Comparator<T> comparator, int from, int count) {
            List<Comparing<T>> cmpElems = elems.stream().map(e -> new Comparing<>(e, comparator)).toList();
            PriorityQueue<Comparing<T>> minHeap;
            if (heapify) {
                minHeap = new PriorityQueue<>(cmpElems); // this constructor uses heapify internally
            } else {
                minHeap = new PriorityQueue<>();
                minHeap.addAll(cmpElems); // this method performs a standard heap insert for each
            }
            for (int i = 0; i < from; i++) {
                minHeap.remove(); // discard leading elements
            }
            List<T> result = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                result.add(minHeap.remove().element); // gather results in target window
            }
            return result;
        }
    }

    static class IntCmp implements Comparator<Integer> {
        int count;

        @Override
        public int compare(Integer left, Integer right) {
            count++;
            return left.compareTo(right);
        }
    }

    record Comparing<T>(T element, Comparator<T> comparator) implements Comparable<Comparing<T>> {
        @Override
        public int compareTo(Comparing<T> c) {
            return comparator.compare(element, c.element);
        }
    }

}

out.txt

[sort]
from=0, count=25, iters=5, min=120360, max=120446, avg=120419
from=25, count=25, iters=5, min=120337, max=120460, avg=120382
from=50, count=25, iters=5, min=120345, max=120467, avg=120390
from=75, count=25, iters=5, min=120354, max=120436, avg=120384
from=100, count=25, iters=5, min=120278, max=120377, avg=120339
from=125, count=25, iters=5, min=120316, max=120516, avg=120400
from=150, count=25, iters=5, min=120304, max=120407, avg=120341
from=175, count=25, iters=5, min=120333, max=120413, avg=120381
from=200, count=25, iters=5, min=120317, max=120459, avg=120387
from=225, count=25, iters=5, min=120268, max=120476, avg=120387
[heap]
from=0, count=25, iters=5, min=22972, max=23574, avg=23391
from=25, count=25, iters=5, min=23744, max=24261, avg=23993
from=50, count=25, iters=5, min=24539, max=24919, avg=24688
from=75, count=25, iters=5, min=24901, max=25309, avg=25156
from=100, count=25, iters=5, min=25590, max=26064, avg=25842
from=125, count=25, iters=5, min=26294, max=26803, avg=26475
from=150, count=25, iters=5, min=26867, max=27309, avg=27079
from=175, count=25, iters=5, min=27535, max=27836, avg=27681
from=200, count=25, iters=5, min=28028, max=28436, avg=28275
from=225, count=25, iters=5, min=28637, max=29138, avg=28859
[heapify]
from=0, count=25, iters=5, min=19311, max=19460, avg=19409
from=25, count=25, iters=5, min=19955, max=20063, avg=20011
from=50, count=25, iters=5, min=20585, max=20687, avg=20647
from=75, count=25, iters=5, min=21066, max=21334, avg=21246
from=100, count=25, iters=5, min=21773, max=21885, avg=21845
from=125, count=25, iters=5, min=22428, max=22533, avg=22490
from=150, count=25, iters=5, min=23013, max=23162, avg=23070
from=175, count=25, iters=5, min=23590, max=23840, avg=23717
from=200, count=25, iters=5, min=24270, max=24402, avg=24337
from=225, count=25, iters=5, min=24795, max=24973, avg=24878