Can the combination of filter and map be optimized?

Using Swift
1

Can the combination of filter and map be optimized?
Time complexity: 2N->N
Now the filter and map operations use two for loops. Can we optimize to use one for loop
like this:

struct Person {
    var name = ""
    var age = 0
}

let person1 = Person(name: "Tom", age: 10)
let person2 = Person(name: "Jack", age: 18)
let person3 = Person(name: "John", age: 20)
let persons = [person1, person2, person3]

let result1 = persons.filter { (model) -> Bool in
    return model.age >= 18
}.map { (person) -> String in
    return person.name
}
print(result1)

var result2: [String] = []
for person in persons where person.age >= 18 {
    result2.append(person.name)
}
print(result2)
2

Isn't that what compactMap(:_) does?

3 Likes
3

No

4

Yes, that will do it. Depending on whether you want to filter on the original values or the mapped values, it looks like one of these:

let filteredThenMapped = someSequence.compactMap {
  return condition($0) ? transform($0) : nil
}

let mappedThenFiltered = someSequence.compactMap {
  let x = tranform($0)
  return condition(x) ? x : nil
}
1 Like
6

I think there's a misconception at what you're trying to do. Are you reducing it from 2N to N? Yes. Does it change anything? Not much. You're still doing the same operations, it's just written differently. That's a common pitfall with Big O because "N" is very subjective.

You're probably getting a small improvement from not having to allocate the intermediate array from filter, but the loops themselves (which you pointed as the problem) are still the same.

1 Like
7

More precisely, O(2N) = O(N). If you want to be more precise about runtimes, you have to be more specific about your constants and that's a bit difficult to do. Still, I think in general, single-pass through an array should probably be somewhat more efficient because at least it reduces the number of lookups (but if your operations on the elements are complex enough, they will dominate the algorithm anyway).

I was under the impression that you can achieve the single-loop effect by just using lazy, though, i.e.

let result = persons.lazy.filter { $0.age >= 18 }.map { $0.name }
print(Array(result))
1 Like