javascript - 需要提高找到最早等于给定总和的对的函数的性能

Question

我有一个接受数组和数字的函数。它扫描数组以查找数组中最早出现的两个数字，这些数字加起来等于该数字。我想知道，在性能方面，什么可以帮助这个功能运行得更快。它必须在 6 秒内处理大约 10,000,000 个项目的列表。我现在已经重构了几次，但仍然没有到达那里。

速度最好的数组迭代方法是什么？我假设 for 循环是最慢的，所以我选择了 map。有没有更快的方法？每个()？

注意:提供的数组可以有重复的、正的或负的数字(假设最多 1000000……现在)。

var low_pair = function (ints, s) {
    var lowNum = ints.length, lowMatch, highNum, clone = [], i;

    for (i = 0; i < ints.length; i++) {
        clone[i] = ints.map(function (n, ind) {
            if (ind !== i && ints[i] + n == s) {
                i > ind ? highNum = i : highNum = ind;
                if (highNum < lowNum) {
                    lowNum = highNum;
                    lowMatch = [ints[i], ints[ind]];
                }
            }
        });
    }
    return lowMatch;
};

Answer 1

我们将创建一个函数，返回最早的元素对，这些元素加起来达到所需的总和:

function find_pair(l, s) {
    var min_indexes = {};
    for (var i = 0; i < l.length; i++) {
        var a = l[i];
        if ((s - a) in min_indexes)
            return [s - a, a];
        if (!(a in min_indexes))
            min_indexes[a] = i;
    }
}

为此，对于我们处理的每个数字，我们都会存储其最小索引。如果我们当前正在处理数字 a，我们会检查 s - a 是否设置了最小索引。如果是，这意味着我们找到了我们想要的总和，并且我们返回了两个元素。

例如:

> var l = [2, 3, 4, 5, 5, 7, 8]
> find_pair(l, 10)
[5, 5]
> find_pair(l, 6)
[2, 4]
> find_pair(l, 5)
[2, 3]
> find_pair(l, 15)
[7, 8]
> find_pair([5, 9, 13, -3], 10)
[13, -3]