benchmark kdtreesearcher

## Comprehensive KDTree Performance Benchmark
## Tests various combinations of n (data points), d (dimensions)
## Outputs CSV results for analysis

clear all;

## Test configurations
n_values = [1000, 2500, 5000, 10000, 20000];
d_values = [2, 3, 5, 10, 20];
n_queries = 200;
k_neighbors = 5;
n_trials = 3;  ## Number of trials per configuration

## Initialize results storage
results = {};
row_idx = 1;

printf("Running comprehensive KDTree benchmark...\n");
printf("Configurations: %d\n", length(n_values) * length(d_values));
printf("Trials per config: %d\n\n", n_trials);

for n = n_values
  for d = d_values
    printf("Testing n=%d, d=%d... ", n, d);

    ## Generate random data
    rng(42);  ## Fixed seed for reproducibility
    X_train = rand(n, d);
    X_query = rand(n_queries, d);

    ## Warmup (JIT compilation)
    kdtree = KDTreeSearcher(X_train(1:100, :));
    [idx, dist] = knnsearch(kdtree, X_query(1:10, :), 'K', k_neighbors);

    ## Time build phase
    build_times = zeros(1, n_trials);
    for trial = 1:n_trials
      tic;
      kdtree = KDTreeSearcher(X_train);
      build_times(trial) = toc;
    endfor
    avg_build = mean(build_times);

    ## Time query phase
    query_times = zeros(1, n_trials);
    for trial = 1:n_trials
      kdtree = KDTreeSearcher(X_train);
      tic;
      [idx, dist] = knnsearch(kdtree, X_query, 'K', k_neighbors);
      query_times(trial) = toc;
    endfor
    avg_query = mean(query_times);

    ## Store results
    results{row_idx, 1} = n;
    results{row_idx, 2} = d;
    results{row_idx, 3} = avg_build;
    results{row_idx, 4} = avg_query;
    results{row_idx, 5} = avg_build + avg_query;
    results{row_idx, 6} = avg_query / n_queries;  ## per-query time

    printf("Build: %.4fs, Query: %.4fs, Total: %.4fs\n", avg_build, avg_query, avg_build + avg_query);

    row_idx = row_idx + 1;
  endfor
endfor

## Convert to matrix for easier handling
n_configs = length(n_values) * length(d_values);
result_matrix = zeros(n_configs, 6);
for i = 1:n_configs
  for j = 1:6
    result_matrix(i, j) = results{i, j};
  endfor
endfor

## Save as CSV
csv_filename = "kdtree_benchmark_results.csv";
fid = fopen(csv_filename, "w");
fprintf(fid, "n,d,build_time,query_time,total_time,per_query_time\n");
for i = 1:n_configs
  fprintf(fid, "%d,%d,%.6f,%.6f,%.6f,%.6f\n", ...
          result_matrix(i,1), result_matrix(i,2), result_matrix(i,3), ...
          result_matrix(i,4), result_matrix(i,5), result_matrix(i,6));
endfor
fclose(fid);

printf("\n=== Summary Statistics ===\n");
printf("Total configurations tested: %d\n", n_configs);
printf("Build time range: %.4f - %.4f s\n", min(result_matrix(:,3)), max(result_matrix(:,3)));
printf("Query time range: %.4f - %.4f s\n", min(result_matrix(:,4)), max(result_matrix(:,4)));
printf("Results saved to: %s\n", csv_filename);