在数组数组中搜索数组的最有效方法

Question

我有一个大数组 array1，其中填充了已经排序的数字数组，如下例所示。现在我想检查 array1 是否包含 array2.

目前我的函数 searchForArray 运行良好。但是因为我有非常大的 array1 数组，它非常慢。

如何改进我的搜索功能以获得更好的性能？

var array1 = [
    [1, 0], [1, 2], [1, 5], [1 , 12],
    [2, 3], [2, 9], [2, 25],
    [7, 2], [7, 4], [7, 7], [7, 8], [7, 16],
    [8, 20], [8, 35], [8, 40], [8, 50]
];
var array2 = [7, 4];

if (searchForArray(array1, array2)) {
    // Array 2 is in array1
}


function searchForArray(bigArray, searchArray) {
    const a = JSON.stringify(bigArray);
    const b = JSON.stringify(searchArray);
    const c = a.indexOf(b);
    if (c != -1) {
        return true;
    }

    return false;
}

Answer 1

尝试在没有 JSON.stringify():

的情况下进行检查

function arraysEqual(a, b) {
    return a[0] === b[0] && a[1] === b[1]
}

function searchForArray(bigArray, searchArray) {
    return bigArray.some(a => arraysEqual(a, searchArray))
}

Answer 2

这可能会更高效一些，因为您不需要 JSON.stringify 大量的数组。只需查找与您要查找的数组具有相同元素的第一项。

function searchForArray(bigArray, searchArray) {
    return !!bigArray.find(item => item.join(',') === searchArray.join(','));
}

当然这个速度取决于searchArray在bigArray中的位置。如果它在顶部，这是非常快的。如果在底部或根本不存在，如果 searchArray 真的很大，这仍然需要一些时间。但至少这不会占用你所有的记忆。

Answer 3

感谢所有回复或提出建议的人。

我现在实施了一个 binary search 算法，它大大提高了我的性能（需要 110 秒的过程现在可以在 <1 秒内执行）。

也许有人需要类似的东西：

function searchForArray(bigArray, searchArray) {
    var startIndex = 0;
    var endIndex = bigArray.length - 1;
    var startSearchIndex;
    var endSearchIndex;
    var firstIndexFound = false;

    while (startIndex <= endIndex) {
        var middle = Math.floor((startIndex + endIndex) / 2);

        if (bigArray[middle][0] === searchArray[0]) {
            // found the first key
            startIndex = middle;
            endIndex = middle;
            firstIndexFound = true;
            break;
        }
        else if (bigArray[middle][0] < searchArray[0]) {
            // continue searching to the right
            startIndex = middle + 1;
        }
        else {
            // search searching to the left
            endIndex = middle - 1;
        }
    }

    // Get index where to search for second key
    while (startIndex != 0 && bigArray[startIndex - 1][0] === searchArray[0]) {
        startIndex -= 1;
    }
    while (endIndex != bigArray.length - 1 && bigArray[endIndex + 1][0] === searchArray[0]) {
        endIndex += 1;
    }


    while (startIndex <= endIndex) {
        var middle = Math.floor((startIndex + endIndex) / 2);

        if (bigArray[middle][1] === searchArray[1]) {
            // found the second key
            return true;
        }
        else if (bigArray[middle][1] < searchArray[1]) {
            // continue searching to the right
            startIndex = middle + 1;
        }
        else {
            // search searching to the left
            endIndex = middle - 1;
        }
    }

    return false;
}

在数组数组中搜索数组的最有效方法

Most efficient way to search for array in array of arrays

javascript

arrays

sorting

search