pareto-optimizations.ts•10.7 kB
/**
* OPTIMIZATION: Performance enhancements for Pareto Frontier operations
* These provide spatial indexing, caching, and efficient dominance checking
*/
import type { ParetoPoint, ParetoObjective } from './pareto-frontier';
/**
* OPTIMIZATION: Spatial index for O(log n) dominance checking
*/
export class DominanceIndex {
private kdTree: KDTree | null = null;
private points: ParetoPoint[] = [];
private needsRebuild = false;
addPoint(point: ParetoPoint): void {
this.points.push(point);
this.needsRebuild = true;
}
removePoints(toRemove: ParetoPoint[]): void {
const idsToRemove = new Set(toRemove.map(p => p.candidate.id));
this.points = this.points.filter(p => !idsToRemove.has(p.candidate.id));
this.needsRebuild = true;
}
isDominated(point: ParetoPoint): boolean {
this.ensureIndexBuilt();
if (!this.kdTree || this.points.length === 0) {
return false;
}
// Use k-d tree for efficient spatial queries
const objectiveVector = this.pointToVector(point);
const nearestNeighbors = this.kdTree.nearest(objectiveVector, Math.min(10, this.points.length));
return nearestNeighbors.some(neighbor =>
this.dominatesVector(this.pointToVector(neighbor.point), objectiveVector)
);
}
findDominated(point: ParetoPoint): ParetoPoint[] {
this.ensureIndexBuilt();
if (!this.kdTree || this.points.length === 0) {
return [];
}
const objectiveVector = this.pointToVector(point);
const dominated: ParetoPoint[] = [];
// Check all points for domination (could be optimized further with spatial queries)
for (const existingPoint of this.points) {
const existingVector = this.pointToVector(existingPoint);
if (this.dominatesVector(objectiveVector, existingVector)) {
dominated.push(existingPoint);
}
}
return dominated;
}
private ensureIndexBuilt(): void {
if (this.needsRebuild || !this.kdTree) {
this.buildIndex();
this.needsRebuild = false;
}
}
private buildIndex(): void {
if (this.points.length === 0) {
this.kdTree = null;
return;
}
const vectorPoints = this.points.map(point => ({
point,
vector: this.pointToVector(point)
}));
this.kdTree = new KDTree(vectorPoints);
}
private pointToVector(point: ParetoPoint): number[] {
const vector: number[] = [];
point.objectives.forEach(value => vector.push(value));
return vector;
}
private dominatesVector(a: number[], b: number[]): boolean {
if (a.length !== b.length) return false;
let betterInAny = false;
for (let i = 0; i < a.length; i++) {
const aVal = a[i];
const bVal = b[i];
if (aVal === undefined || bVal === undefined) return false;
if (aVal < bVal) return false; // Assuming maximize objectives
if (aVal > bVal) betterInAny = true;
}
return betterInAny;
}
}
/**
* OPTIMIZATION: Simple K-D Tree implementation for spatial indexing
*/
class KDTree {
private root: KDNode | null = null;
private dimension: number = 0;
constructor(points: Array<{ point: ParetoPoint; vector: number[] }>) {
if (points.length === 0) return;
const firstPoint = points[0];
if (!firstPoint || !firstPoint.vector) return;
this.dimension = firstPoint.vector.length;
this.root = this.buildTree(points, 0);
}
nearest(target: number[], k: number = 1): Array<{ point: ParetoPoint; distance: number }> {
if (!this.root) return [];
const result: Array<{ point: ParetoPoint; distance: number }> = [];
this.searchNearest(this.root, target, k, result, 0);
return result.sort((a, b) => a.distance - b.distance).slice(0, k);
}
private buildTree(points: Array<{ point: ParetoPoint; vector: number[] }>, depth: number): KDNode | null {
if (points.length === 0) return null;
const axis = depth % this.dimension;
points.sort((a, b) => {
const aVal = a.vector[axis];
const bVal = b.vector[axis];
return (aVal || 0) - (bVal || 0);
});
const median = Math.floor(points.length / 2);
const medianPoint = points[median];
if (!medianPoint) return null;
const node = new KDNode(medianPoint);
node.left = this.buildTree(points.slice(0, median), depth + 1);
node.right = this.buildTree(points.slice(median + 1), depth + 1);
return node;
}
private searchNearest(
node: KDNode | null,
target: number[],
k: number,
result: Array<{ point: ParetoPoint; distance: number }>,
depth: number
): void {
if (!node) return;
const distance = this.euclideanDistance(node.data.vector, target);
if (result.length < k) {
result.push({ point: node.data.point, distance });
} else {
const maxIndex = result.reduce((maxIdx, curr, idx) => {
const maxItem = result[maxIdx];
return (curr && maxItem && curr.distance > maxItem.distance) ? idx : maxIdx;
}, 0);
const maxItem = result[maxIndex];
if (maxItem && distance < maxItem.distance) {
result[maxIndex] = { point: node.data.point, distance };
}
}
const axis = depth % this.dimension;
const targetVal = target[axis];
const nodeVal = node.data.vector[axis];
if (targetVal === undefined || nodeVal === undefined) return;
const diff = targetVal - nodeVal;
const nearNode = diff < 0 ? node.left : node.right;
const farNode = diff < 0 ? node.right : node.left;
this.searchNearest(nearNode, target, k, result, depth + 1);
// Check if we need to search the other side
const maxDist = result.length < k ? Infinity :
Math.max(...result.map(r => r?.distance || 0).filter(d => d !== undefined));
if (Math.abs(diff) < maxDist) {
this.searchNearest(farNode, target, k, result, depth + 1);
}
}
private euclideanDistance(a: number[], b: number[]): number {
let sum = 0;
for (let i = 0; i < a.length; i++) {
const aVal = a[i];
const bVal = b[i];
if (aVal === undefined || bVal === undefined) continue;
sum += Math.pow(aVal - bVal, 2);
}
return Math.sqrt(sum);
}
}
class KDNode {
data: { point: ParetoPoint; vector: number[] };
left: KDNode | null = null;
right: KDNode | null = null;
constructor(data: { point: ParetoPoint; vector: number[] }) {
this.data = data;
}
}
/**
* OPTIMIZATION: Objective cache for expensive calculations
*/
export class ObjectiveCache {
private cache = new Map<string, Map<string, number>>();
private accessTimes = new Map<string, number>();
private readonly maxCacheSize = 1000;
private readonly ttl = 3600000; // 1 hour
getCachedObjectives(candidateId: string, _objectiveExtractors: ParetoObjective[]): Map<string, number> | null {
const cached = this.cache.get(candidateId);
if (!cached) return null;
// Check TTL
const accessTime = this.accessTimes.get(candidateId) || 0;
if (Date.now() - accessTime > this.ttl) {
this.cache.delete(candidateId);
this.accessTimes.delete(candidateId);
return null;
}
// Update access time
this.accessTimes.set(candidateId, Date.now());
return cached;
}
setCachedObjectives(candidateId: string, objectives: Map<string, number>): void {
// Enforce cache size limit
if (this.cache.size >= this.maxCacheSize) {
this.evictOldest();
}
this.cache.set(candidateId, new Map(objectives));
this.accessTimes.set(candidateId, Date.now());
}
private evictOldest(): void {
let oldestId = '';
let oldestTime = Infinity;
for (const [id, time] of this.accessTimes) {
if (time < oldestTime) {
oldestTime = time;
oldestId = id;
}
}
if (oldestId) {
this.cache.delete(oldestId);
this.accessTimes.delete(oldestId);
}
}
clear(): void {
this.cache.clear();
this.accessTimes.clear();
}
}
/**
* OPTIMIZATION: Hypervolume cache for expensive calculations
*/
export class HypervolumeCache {
private cache = new Map<string, { value: number; timestamp: number }>();
private readonly maxCacheSize = 100;
private readonly ttl = 1800000; // 30 minutes
get(key: string): { value: number; timestamp: number } | null {
const cached = this.cache.get(key);
if (!cached) return null;
// Check TTL
if (Date.now() - cached.timestamp > this.ttl) {
this.cache.delete(key);
return null;
}
return cached;
}
set(key: string, value: { value: number; timestamp: number }): void {
// Enforce cache size limit
if (this.cache.size >= this.maxCacheSize) {
this.evictOldest();
}
this.cache.set(key, value);
}
private evictOldest(): void {
let oldestKey = '';
let oldestTime = Infinity;
for (const [key, entry] of this.cache) {
if (entry.timestamp < oldestTime) {
oldestTime = entry.timestamp;
oldestKey = key;
}
}
if (oldestKey) {
this.cache.delete(oldestKey);
}
}
clear(): void {
this.cache.clear();
}
}
/**
* OPTIMIZATION: Efficient diversity computation using sampling
*/
export class DiversityCalculator {
static computeDiversitySampled(points: ParetoPoint[], sampleSize: number = 25): number {
if (points.length < 2) return 0;
const actualSampleSize = Math.min(sampleSize, points.length);
const sampledPoints = this.randomSample(points, actualSampleSize);
let totalDistance = 0;
let count = 0;
for (let i = 0; i < sampledPoints.length; i++) {
const pointI = sampledPoints[i];
if (!pointI) continue;
for (let j = i + 1; j < sampledPoints.length; j++) {
const pointJ = sampledPoints[j];
if (!pointJ) continue;
totalDistance += this.computeDistance(pointI, pointJ);
count++;
}
}
// Scale back to approximate full diversity
const scaleFactor = (points.length * (points.length - 1)) / (actualSampleSize * (actualSampleSize - 1));
return count > 0 ? (totalDistance / count) * scaleFactor : 0;
}
private static randomSample<T>(array: T[], size: number): T[] {
const shuffled = [...array].sort(() => 0.5 - Math.random());
return shuffled.slice(0, size);
}
private static computeDistance(a: ParetoPoint, b: ParetoPoint): number {
let sumSquares = 0;
a.objectives.forEach((aValue, objName) => {
const bValue = b.objectives.get(objName) || 0;
if (!isNaN(aValue) && !isNaN(bValue)) {
sumSquares += Math.pow(aValue - bValue, 2);
}
});
return Math.sqrt(sumSquares);
}
}