go-learn/packages/core/bench/group-bench.mts

/**
 * Микро-бенчмарк: flood fill vs union-find для поиска групп и дамэ
 * на случайных позициях 19×19. Запуск: npx tsx packages/core/bench/group-bench.mts
 * (tsx — эфемерный инструмент прогона, не зависимость пакета).
 * Случайность — только createSeededRng с фиксированным seed (детерминизм).
 */
import { performance } from 'node:perf_hooks';
import { createSeededRng } from '../src/index.js';

const SIZE = 19;
const CELLS = SIZE * SIZE;
const POSITIONS = 40;
const ITERATIONS = 300;

/** Случайная позиция: клетки заняты с вероятностью density, цвет 50/50. */
function randomPosition(seed: number, density: number): Uint8Array {
  const rng = createSeededRng(seed);
  const grid = new Uint8Array(CELLS);
  for (let index = 0; index < CELLS; index += 1) {
    if (rng.next() < density) grid[index] = rng.next() < 0.5 ? 1 : 2;
  }
  return grid;
}

/** Соседи клетки по индексу. */
function neighborIndices(index: number): number[] {
  const x = index % SIZE;
  const y = Math.floor(index / SIZE);
  const result: number[] = [];
  if (x > 0) result.push(index - 1);
  if (x < SIZE - 1) result.push(index + 1);
  if (y > 0) result.push(index - SIZE);
  if (y < SIZE - 1) result.push(index + SIZE);
  return result;
}

/** Flood fill: группы + число дамэ (как в движке, groupAt). */
function groupsFloodFill(grid: Uint8Array): number {
  const seen = new Uint8Array(CELLS);
  let groups = 0;
  let liberties = 0;
  for (let start = 0; start < CELLS; start += 1) {
    if (grid[start] === 0 || seen[start] === 1) continue;
    groups += 1;
    const color = grid[start];
    const stack = [start];
    seen[start] = 1;
    const libs = new Set<number>();
    while (stack.length > 0) {
      const current = stack.pop() as number;
      for (const next of neighborIndices(current)) {
        if (grid[next] === 0) libs.add(next);
        if (grid[next] === color && seen[next] === 0) {
          seen[next] = 1;
          stack.push(next);
        }
      }
    }
    liberties += libs.size;
  }
  return groups * 1000 + liberties;
}

/** Union-find: группы + число дамэ. */
function groupsUnionFind(grid: Uint8Array): number {
  const parent = new Int32Array(CELLS);
  for (let index = 0; index < CELLS; index += 1) parent[index] = index;
  const find = (value: number): number => {
    let root = value;
    while (parent[root] !== root) root = parent[root] ?? root;
    let node = value;
    while (parent[node] !== node) {
      const next = parent[node] ?? node;
      parent[node] = root;
      node = next;
    }
    return root;
  };
  for (let index = 0; index < CELLS; index += 1) {
    if (grid[index] === 0) continue;
    for (const next of neighborIndices(index)) {
      if (grid[next] === grid[index]) parent[find(index)] = find(next);
    }
  }
  const libsByRoot = new Map<number, Set<number>>();
  for (let index = 0; index < CELLS; index += 1) {
    if (grid[index] === 0) continue;
    const root = find(index);
    let libs = libsByRoot.get(root);
    if (libs === undefined) {
      libs = new Set<number>();
      libsByRoot.set(root, libs);
    }
    for (const next of neighborIndices(index)) {
      if (grid[next] === 0) libs.add(next);
    }
  }
  let liberties = 0;
  for (const libs of libsByRoot.values()) liberties += libs.size;
  return libsByRoot.size * 1000 + liberties;
}

/** Прогон одного алгоритма на наборе позиций; возвращает мс и контрольную сумму. */
function measure(
  positions: Uint8Array[],
  algorithm: (grid: Uint8Array) => number,
): { ms: number; checksum: number } {
  let checksum = 0;
  const started = performance.now();
  for (let iteration = 0; iteration < ITERATIONS; iteration += 1) {
    for (const grid of positions) checksum = (checksum + algorithm(grid)) % 1000003;
  }
  return { ms: performance.now() - started, checksum };
}

const rng = createSeededRng(7);
const densities = [0.35, 0.55, 0.75];
let totalFlood = 0;
let totalUnion = 0;
for (const density of densities) {
  const positions = Array.from({ length: POSITIONS }, (_, index) =>
    randomPosition(Math.floor(rng.next() * 100000), density),
  );
  const flood = measure(positions, groupsFloodFill);
  const union = measure(positions, groupsUnionFind);
  if (flood.checksum !== union.checksum) {
    console.warn(`ОШИБКА: контрольные суммы не совпали (${flood.checksum} != ${union.checksum})`);
    process.exitCode = 1;
  }
  totalFlood += flood.ms;
  totalUnion += union.ms;
  console.warn(
    `density=${density}: flood fill ${flood.ms.toFixed(1)} мс, union-find ${union.ms.toFixed(1)} мс, ` +
      `отношение u/f ${(union.ms / flood.ms).toFixed(2)}`,
  );
}
console.warn(
  `ИТОГО: flood fill ${totalFlood.toFixed(1)} мс, union-find ${totalUnion.toFixed(1)} мс, ` +
    `отношение u/f ${(totalUnion / totalFlood).toFixed(2)} ` +
    `(${POSITIONS * ITERATIONS * densities.length} прогонов позиций 19x19)`,
);