Most efficient way to search for array in array of arrays

Question

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

does your array1 always have that sorted nature? the 1st element of the inner arrays seem to be sorted, you could always use that for a binary search. — tsamridh86
– tsamridh86, Commented Aug 3, 2021 at 10:50
this question has a better place in : codereview.stackexchange.com if in case it gets downvoted by the community here — tsamridh86
– tsamridh86, Commented Aug 3, 2021 at 10:51
@SamridhTuladhar yes it's always sorted like that in nature. I'll try to implement a binary search to test how the performance increases. — Stephan Häberle
– Stephan Häberle, Commented Aug 3, 2021 at 11:00
its depends on your size of data, your constraints of time complexity and space complexity. With the small data sample like this, linear search is prefered, because you don't have to go extra miles to sort it. FYI: there also are TreeMap and HashMap — Mike
– Mike, Commented Aug 3, 2021 at 11:08
@HoangLe I've got very large arrays with size up to 20'000 elements. The data in the array are already automatically sorted as shown above so I don't have to implement a sort algorithm. — Stephan Häberle
– Stephan Häberle, Commented Aug 3, 2021 at 11:29

Stephan Häberle · Accepted Answer · 2021-08-03 12:41:29Z

2

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

answered Aug 3, 2021 at 12:41

Stephan Häberle

3904 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tsamridh86 Over a year ago

i would strongly recommend to use let and const instead of var. This will make sure that the variables remain in the scope and don't fiddle with the rest of the code.

tsamridh86 Over a year ago

also super glad to see something taking 110s being decreased to <1s 😁

Stephan Häberle Over a year ago

Thanks for your input, as I didn't work that much with javascript until now I usually declare everything with var. I'll check out let and const for the future :)

funkizer · Accepted Answer · 2021-08-03 11:39:43Z

1

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.

answered Aug 3, 2021 at 11:39

funkizer

4,9271 gold badge21 silver badges21 bronze badges

1 Comment

Stephan Häberle Over a year ago

Thanks for your reply. Unfortunately this doesn't increase my performance.

Axifive · Accepted Answer · 2021-08-03 13:57:57Z

0

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

edited Aug 3, 2021 at 13:57

answered Aug 3, 2021 at 10:52

Axifive

1,1512 gold badges19 silver badges31 bronze badges

2 Comments

Stephan Häberle Over a year ago

Thanks, I'll give it a try and let you know if it's faster

Axifive Over a year ago

@StephanHäberle, I changed answer, for my tests it faster

user22244332 · Accepted Answer · 2023-08-09 14:52:01Z

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

Collectives™ on Stack Overflow

Most efficient way to search for array in array of arrays

4 Answers 4

3 Comments

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related