Benchmark.java

package collection;

import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Random;

class Benchmark {
  private static final Random RNG = new Random(12345);

  public static void main(final String[] args) throws Exception {
    final int[] ns = {1000, 2000, 5000, 10000, 20000, 50000}; // adapte
    final int reps = 5; // répétitions pour moyenne
    String outFile = "benchmark_results.csv";

    try (PrintWriter pw = new PrintWriter(new FileWriter(outFile))) {
      pw.println("structure,scenario,n,phase,avg_millis");

      for (String structure : Arrays.asList("ABR", "ARN")) {
        for (String scenario : Arrays.asList("random", "ascending")) {
          for (int n : ns) {
            long insertSum = 0;
            long searchSum = 0;

            for (int r = 0; r < reps; r++) {
              List<Integer> keys = new ArrayList<>();

              for (int i = 0; i < n; i++) {
                keys.add(i);
              }

              if (scenario.equals("random")) {
                Collections.shuffle(keys, new Random(RNG.nextLong()));
              }

              // choose structure
              Collection<Integer> tree = structure.equals("ARN")
                  ? new RedBlackTree<>() : new BinarySearchTree<>();

              long t0 = System.nanoTime();

              for (Integer k : keys) {
                tree.add(k);
              }

              long t1 = System.nanoTime();
              long insertMs = (t1 - t0);
              insertSum += insertMs;

              // search phase: 0 .. 2n-1
              long t2 = System.nanoTime();

              for (int x = 0; x < 2 * n; x++) {
                tree.contains(x);
              }

              long t3 = System.nanoTime();
              long searchMs = (t3 - t2);
              searchSum += searchMs;
            }

            pw.printf("%s,%s,%d,insert,%.2f%n", structure, scenario, n,
                insertSum / (double) reps);
            pw.printf("%s,%s,%d,search,%.2f%n", structure, scenario, n,
                searchSum / (double) reps);
            pw.flush();

            System.out.printf("Done %s %s n=%d%n", structure, scenario, n);
          }
        }
      }
    }
    System.out.println("Wrote results to " + outFile);
  }
}