Algorithmische Komplexität und Datenstrukturen

// Performance-Vergleich verschiedener Datenstrukturen
class PerformanceBenchmark {
    static measureTime(fn, iterations = 1000000) {
        const start = performance.now();
        for (let i = 0; i < iterations; i++) {
            fn();
        }
        const end = performance.now();
        return end - start;
    }
    
    static compareDataStructures() {
        const size = 10000;
        const data = Array.from({length: size}, (_, i) => `item-${i}`);
        
        // Array vs Set für Membership-Tests
        const array = [...data];
        const set = new Set(data);
        const map = new Map(data.map((item, index) => [item, index]));
        
        console.log("Membership Test (1000 Operationen):");
        
        // Array.includes() - O(n)
        const arrayTime = this.measureTime(() => {
            array.includes(`item-${Math.floor(Math.random() * size)}`);
        }, 1000);
        
        // Set.has() - O(1) durchschnittlich
        const setTime = this.measureTime(() => {
            set.has(`item-${Math.floor(Math.random() * size)}`);
        }, 1000);
        
        // Map.has() - O(1) durchschnittlich  
        const mapTime = this.measureTime(() => {
            map.has(`item-${Math.floor(Math.random() * size)}`);
        }, 1000);
        
        console.log(`Array: ${arrayTime.toFixed(2)}ms`);
        console.log(`Set: ${setTime.toFixed(2)}ms`);
        console.log(`Map: ${mapTime.toFixed(2)}ms`);
    }
}

// Optimierte Sortieralgorithmen
class SortingAlgorithms {
    static quickSort(arr, low = 0, high = arr.length - 1) {
        if (low < high) {
            const pi = this.partition(arr, low, high);
            this.quickSort(arr, low, pi - 1);
            this.quickSort(arr, pi + 1, high);
        }
        return arr;
    }
    
    static partition(arr, low, high) {
        const pivot = arr[high];
        let i = low - 1;
        
        for (let j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
        
        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }
    
    // Heap Sort für garantierte O(n log n) Performance
    static heapSort(arr) {
        const n = arr.length;
        
        // Build heap
        for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
            this.heapify(arr, n, i);
        }
        
        // Extract elements
        for (let i = n - 1; i > 0; i--) {
            [arr[0], arr[i]] = [arr[i], arr[0]];
            this.heapify(arr, i, 0);
        }
        
        return arr;
    }
    
    static heapify(arr, n, i) {
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest !== i) {
            [arr[i], arr[largest]] = [arr[largest], arr[i]];
            this.heapify(arr, n, largest);
        }
    }
}

// Memory-effiziente Datenverarbeitung
class MemoryOptimization {
    // Generator für große Datenmengen
    static* fibonacciSequence(limit) {
        let a = 0, b = 1;
        while (a < limit) {
            yield a;
            [a, b] = [b, a + b];
        }
    }
    
    // Lazy Evaluation für Datenverarbeitung
    static createLazyArray(data) {
        return {
            *[Symbol.iterator]() {
                for (const item of data) {
                    yield item;
                }
            },
            
            map(fn) {
                const self = this;
                return {
                    *[Symbol.iterator]() {
                        for (const item of self) {
                            yield fn(item);
                        }
                    },
                    map: this.map,
                    filter: this.filter,
                    take: this.take,
                    toArray: this.toArray
                };
            },
            
            filter(predicate) {
                const self = this;
                return {
                    *[Symbol.iterator]() {
                        for (const item of self) {
                            if (predicate(item)) {
                                yield item;
                            }
                        }
                    },
                    map: this.map,
                    filter: this.filter,
                    take: this.take,
                    toArray: this.toArray
                };
            },
            
            take(count) {
                const self = this;
                return {
                    *[Symbol.iterator]() {
                        let taken = 0;
                        for (const item of self) {
                            if (taken >= count) break;
                            yield item;
                            taken++;
                        }
                    },
                    toArray: this.toArray
                };
            },
            
            toArray() {
                return [...this];
            }
        };
    }
}

// Verwendung der Optimierungen
const largeDataset = Array.from({length: 1000000}, (_, i) => i);
const lazyResult = MemoryOptimization.createLazyArray(largeDataset)
    .filter(x => x % 2 === 0)
    .map(x => x * 2)
    .take(10)
    .toArray();

console.log("Lazy evaluation result:", lazyResult);