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;

public class Benchmark {

    private static final Random RNG = new Random(12345);

    public static void main(final String[] args) throws Exception {

	final int[] N_LIST = { 1000, 2000, 5000, 10000, 20000, 50000 };
	final int REP = 5;

	// --- Create the 4 CSV writers ---
	PrintWriter abrInsert = new PrintWriter(new FileWriter("ABR_insert.csv"));
	PrintWriter abrSearch = new PrintWriter(new FileWriter("ABR_search.csv"));
	PrintWriter arnInsert = new PrintWriter(new FileWriter("ARN_insert.csv"));
	PrintWriter arnSearch = new PrintWriter(new FileWriter("ARN_search.csv"));

	// Header line : n,1000,2000,...
	writeHeader(abrInsert, N_LIST);
	writeHeader(abrSearch, N_LIST);
	writeHeader(arnInsert, N_LIST);
	writeHeader(arnSearch, N_LIST);

	// Scenarios
	List<String> scenarios = Arrays.asList("ASCENDANT", "ALEATOIRE");

	// Process each structure
	for (String structure : Arrays.asList("ABR", "ARN")) {

	    for (String scenario : scenarios) {

		// Buffers for one line of insert & search results
		List<Double> insertLine = new ArrayList<>();
		List<Double> searchLine = new ArrayList<>();

		for (int n : N_LIST) {

		    long insertSum = 0;
		    long searchSum = 0;

		    for (int r = 0; r < REP; r++) {

			List<Integer> keys = new ArrayList<>();
			for (int i = 0; i < n; i++)
			    keys.add(i);

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

			long[] result = structure.equals("ABR") ? benchmarkABR(keys, n) : benchmarkARN(keys, n);

			insertSum += result[0];
			searchSum += result[1];
		    }

		    insertLine.add(insertSum / (double) REP);
		    searchLine.add(searchSum / (double) REP);

		    System.out.printf("Done %s %s n=%d\n", structure, scenario, n);
		}

		// Write to correct CSV
		if (structure.equals("ABR")) {
		    writeScenarioLine(abrInsert, scenario, insertLine);
		    writeScenarioLine(abrSearch, scenario, searchLine);
		} else {
		    writeScenarioLine(arnInsert, scenario, insertLine);
		    writeScenarioLine(arnSearch, scenario, searchLine);
		}
	    }
	}

	abrInsert.close();
	abrSearch.close();
	arnInsert.close();
	arnSearch.close();

	System.out.println("4 CSV créés au format tableau.");
    }

    // -------------------------------------------------------
    // Helper: header line
    // -------------------------------------------------------
    private static void writeHeader(PrintWriter pw, int[] nList) {
	pw.print("n");
	for (int n : nList)
	    pw.print("," + n);
	pw.println();
    }

    // -------------------------------------------------------
    // Helper: write one scenario line
    // -------------------------------------------------------
    private static void writeScenarioLine(PrintWriter pw, String scenario, List<Double> values) {
	pw.print(scenario);
	for (double v : values)
	    pw.printf(",%.2f", v);
	pw.println();
    }

    // -------------------------------------------------------
    // Benchmark ABR / ARN
    // -------------------------------------------------------

    private static long[] benchmarkABR(List<Integer> keys, int n) {
	Collection<Integer> tree = new ArbreBinaireRecherche<>();
	return runBenchmark(tree, keys, n);
    }

    private static long[] benchmarkARN(List<Integer> keys, int n) {
	Collection<Integer> tree = new RedBlackTree<>();
	return runBenchmark(tree, keys, n);
    }

    private static long[] runBenchmark(Collection<Integer> tree, List<Integer> keys, int n) {
	long t0 = System.nanoTime();
	for (Integer k : keys)
	    tree.add(k);
	long t1 = System.nanoTime();

	long t2 = System.nanoTime();
	for (int x = 0; x < 2 * n; x++)
	    tree.contains(x);
	long t3 = System.nanoTime();

	return new long[] { t1 - t0, t3 - t2 };
    }
}