优化百万级数据处理：AoC 2023 Day5 Part2 JavaScript性能问题求助

核心问题分析 #

你遇到的问题本质是直接遍历单个种子值的方式在官方输入下完全不可行——官方种子是[起始值, 长度]的区间组合，总覆盖量可能达到数十亿级别，遍历每个值会直接耗尽内存或导致运行时间无限长。示例数据因为区间规模小，所以能正常运行。

优化思路：区间映射替代单值遍历 #

不需要处理每个种子，而是把种子当作区间集合，依次通过每个映射表（种子→土壤，土壤→肥料…）进行区间转换，最终在所有最终区间里提取最小值。

优化后的代码示例 #

const fs = require('fs');

function parseInput(input) {
    const sections = input.split('\n\n');
    // 解析种子区间
    const seeds = sections[0].match(/\d+/g).map(Number);
    const seedRanges = [];
    for (let i = 0; i < seeds.length; i += 2) {
        seedRanges.push([seeds[i], seeds[i] + seeds[i + 1] - 1]); // [起始值, 结束值] 闭区间
    }

    // 解析所有映射表
    const maps = sections.slice(1).map(section => {
        const lines = section.split('\n').slice(1);
        return lines.map(line => {
            const [destStart, srcStart, length] = line.match(/\d+/g).map(Number);
            return {
                srcStart,
                srcEnd: srcStart + length - 1,
                offset: destStart - srcStart
            };
        }).sort((a, b) => a.srcStart - b.srcStart); // 按源区间起始排序，保证处理顺序正确
    });

    return { seedRanges, maps };
}

function transformRanges(ranges, map) {
    const result = [];
    for (const [start, end] of ranges) {
        let currentStart = start;
        for (const entry of map) {
            if (currentStart > end) break;
            // 当前区间在映射区间之前，直接加入结果
            if (currentStart < entry.srcStart) {
                result.push([currentStart, Math.min(end, entry.srcStart - 1)]);
                currentStart = entry.srcStart;
            }
            // 当前区间与映射区间重叠，转换后加入结果
            if (currentStart <= entry.srcEnd) {
                const overlapStart = currentStart;
                const overlapEnd = Math.min(end, entry.srcEnd);
                result.push([overlapStart + entry.offset, overlapEnd + entry.offset]);
                currentStart = overlapEnd + 1;
            }
        }
        // 处理剩余未被映射的区间
        if (currentStart <= end) {
            result.push([currentStart, end]);
        }
    }
    return result;
}

function findMinLocation(input) {
    const { seedRanges, maps } = parseInput(input);
    let currentRanges = seedRanges;
    for (const map of maps) {
        currentRanges = transformRanges(currentRanges, map);
    }
    // 从所有最终区间中提取最小起始值
    return Math.min(...currentRanges.map(range => range[0]));
}

// 读取输入文件
const input = fs.readFileSync('input.txt', 'utf8');
console.log(findMinLocation(input));

关键优化点 #

1. 内存占用骤降：完全避免存储单个种子值，内存占用从O(数十亿)降到O(区间数量)，区间数量最多仅几百个
2. 运行时间大幅缩短：每个映射步骤仅处理当前区间集合，时间复杂度与区间数量、映射规则数量成正比，无需等待数小时甚至更久
3. 逻辑严谨：通过区间拆分与匹配，确保所有数值范围都被正确转换，不会遗漏任何可能的最小值

内容的提问来源于stack exchange，提问作者helloworld