CODEWITHSUNDEEP
swift
lurning too koad
lurning too koad

Reputation: 2964

More efficient way of searching multiple arrays for singular item?

I need to search multiple large arrays in search of one item. If that item is in at least one of the arrays, the result should be true. Between the three examples below, is one more efficient than the other? Or is there a more efficient way?

let arr1 = ["a", "b", "c"]
let arr2 = ["d", "e", "f"]
let arr3 = ["g", "h", "i"]

let q = "h"

if arr1.contains(q) || arr2.contains(q) || arr3.contains(q) {
    print("y")
}

for arr in [arr1, arr2, arr3] {
    if arr.contains(q) {
        print("y")
        break
    }
}

if (arr1 + arr2 + arr3).contains(q) {
    print("y")
}

And I suppose I should ask, if I'm able to make these arrays sets (if I can safely do that knowing they are all unique), would that change anything?

Upvotes: 0

Views: 63

Answers (2)

runcoderun
runcoderun

Reputation: 531

Assuming the arrays contain unsorted elements that are unique across all arrays:

Arrays:

Option 1 has a worst-case running time of 3n. Option 2 has a worst-case running time of 3n. Option 3 has a worst-case running time of 6n

Eliminating constant factors, the asymptotic running time of all three is On.

Sets:

Conversion from array to set is also a On operation. It would make sense to just make one set and add everything to it. Once done, the .contains() lookup has a time complexity of enter image description here.

Upvotes: 1

Azamat Zhurtbayev
Azamat Zhurtbayev

Reputation: 233

The first two approaches are equivalent - they stop processing as soon as they have found existing solution and do not create any additional lists, i.e. they scan existing lists and if e.g. the first list contains the target element, the second and third arrays will not be touched at all.

But the third option is different - it first concatenates all the arrays into a new one and then scan the new list. In this case if you have large arrays you will face doubled memory consumption at the moment of this operation. Also, it may take additional time to join lists into a new one.

Changing lists to check for a single element will not help in any way, because this transformation will scan the whole list, that is the same operation that is done during search. But if you have a large amount of search requests then it is reasonable to use sets, preferably sorted sets, e.g. tree set.

Upvotes: 1

Related Questions