CODEWITHSUNDEEP
javascriptarrayssortingsearch
Stephan Häberle
Stephan Häberle

Reputation: 390

Most efficient way to search for array in array of arrays

I've got an large array array1 filled with arrays of numbers already sorted like in the example below. Now I want to check, if the array1 contains the array2.

Currently I've got the function searchForArray which works fine. But as I've got very large arrays for array1, it's very slow.

How can I improve my search function for better performance?

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;
}

Upvotes: 2

Views: 573

Answers (4)

user22244332
user22244332

Reputation: 9

You could alternatively convert your array of arrays into a hash table (implementation is up to you). Here is one such example:

We will compute the key for each element by summing up the values in the array and keep an array of arrays for the resulting values (since we can have more than one element with the same sum)

var array1 = {
    1: [[1, 0]],
    3: [[1, 2]],
    5: [[2, 3]],
    6: [[1, 5]],
    9: [[7, 2]],
    11: [[1, 12], [2, 9], [7, 4]],
    14: [[7, 7]],
    15: [[7, 8]],
    23: [[7, 16]],
    27: [[2, 25]],
    28: [[8, 20]],
    43: [[8, 35]],
    48: [[8, 40]],
    58: [[8, 50]]
}

This allows us to determine if some other element is present in the list in O(1) time on average.

const a = [2, 9]

const s = a.reduce((partialSum, a) => partialSum + a, 0)

const v = map[s]

for (let i = 0; i < v.length; i++) {
    if (JSON.stringify(v[i]) == JSON.stringify(a)) {
        console.log(true)
        return;d
    }
}

console.log(false)

Note that this is only practical when the list is known ahead of time, otherwise it will take O(n) just to construct the hash table

Upvotes: 0

Axifive
Axifive

Reputation: 1151

Try check without 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))
}

Upvotes: 0

Stephan H&#228;berle
Stephan H&#228;berle

Reputation: 390

Thanks to everybody who replied or gave some suggestions.

I now implemented a binary search algorithm, which speeds up my performance by far (process which took 110 sec are now executed in <1 sec).

Maybe there's someone who needs something similar:

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;
}

Upvotes: 2

funkizer
funkizer

Reputation: 4897

This might be a little more performant, because you don't need to JSON.stringify a huge array of arrays. Just look for the first item that has the same elements as the array you're looking for.

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

Of course the speed of this depends on where searchArray exists in bigArray. If it's at the top, this is very fast. If in the bottom or does not exist at all, this will still take some time if searchArray is really huge. But at least this won't hog all your memory.

Upvotes: 1

Related Questions