• Lazy Sequences in Swift And How They Work
  • Bruno Rocha
  • The Nuggets translation Project
  • Permanent link to this article: github.com/xitu/gold-m…
  • Translator: RickeyBoy

Using higher-order functions like Map and filter is very common in Swift projects because they are simple algorithms that allow you to turn complex ideas into simple single-line functions. Unfortunately, they don’t solve all the problems — at least not in their default implementation. Higher-order functions are very urgent: they use closures to immediately return a new array, whether you need to return ahead of time or just use specific elements of it. When performance is important, you may be forced to write specific helper methods to avoid the urgency of higher-order functions.

let addresses = getFirstThreeAddresses(withIdentifier: "HOME") func getFirstThreeAddresses(withIdentifier identifier: String) -> [Address] {// do not use.filter{}.prefix(3) because we need to return var addresses = [Address]()for address in allAddresses where address.identifier == identifier {
        addresses.append(address)
        if addresses.count == 3 {
            break}}return addresses
}
Copy the code

Fortunately, Swift has a way to maintain its high performance and helper functions while using higher-order functions – lazy-executed versions of the Swift standard library Sequences and Collections are available through the lazy keyword.

The lazy versions of these changes work just like the normal case, with one change: they have custom implementations like Map and filter to keep them lazy — meaning that they actually only perform operations when you need them.

letallNumbers = Array(1... 1000).let normalMap = allNumbers.map { $0* 2} // Whatever you need to do, the mapping will be completedlet lazyMap = allNumbers.lazy.map { $0* 2} // Nothing happens hereprint(lazyMap[0]) // Prints 2, but nothing else is involvedCopy the code

Although a little scary at first, they allow you to reduce most for loops in favor of single-line functions that can return ahead of time. For example, when used to find the first element that satisfies an assertion, here’s how it compares to other methods:

// There are 10000 Address elements in the [Address] array, and one at the beginning"HOME"Address elementlet address = allAddresses.filter { $0.identifier == "HOME"}. First // ~ 0.15sec // func firstAddress(withIdentifier Identifier: String) -> Address? {// Now you can use the library's first(whereMethod, // But let's pretend it doesn't exist for now.for address in allAddresses where address.identifier == identifier {
        return address
    }
    return nil
}

let address = firstAddress(withIdentifier: "HOME") // Immediately // contrastlet address = allAddresses.lazy.filter { $0.identifier == "HOME"}.first // Also returns immediately, and with less code!Copy the code

In addition to writing less code, they are also very helpful for lazy operations in general, making your code easier to read. Suppose you have a shopping app that displays offers from a local database if the user takes too long to complete the purchase:

let offerViews = offersJson.compactMap { database.load(offer: $0) }.map(OfferView.init) // O(n)
var currentOffer = -1

func displayNextOffer() {
    guard currentOffer + 1 < offerViews.count else {
        return
    }
    currentOffer += 1
    offerViews[currentOffer].display(atViewController: self)
}
Copy the code

When this solution worked, it had one major problem: I rushed to map all the JSON content to OfferViews, even though the user didn’t necessarily see all the options. This isn’t a problem if the content offerJson is just a small array, but if the data is huge, pulling everything out of the database at once becomes an immediate problem.

You can achieve the OfferViews required for mapping only by moving the parsing logic to displayNextOffer(), but the quality of your code may be difficult to understand by preserving the raw data:

let offersJson: [[String: Any]] = //
var currentOffer = -1

func displayNextOffer() {
    guard currentOffer + 1 < offerViews.count else {
        return
    }
    currentOffer += 1
    guard let offer = database.load(offer: offersJson[currentOffer]) else {
        return
    }
    let offerView = OfferView(offer: offer)
    offerView.display(atViewController: self)
}
Copy the code

By using lazy, the current offerView will only map to the location of the array when used by displayNextOffer(), which ensures both readability and performance!

let offerViews = offersJson.lazy.compactMap { database.load(offer: $0}.map(offerView.init) // Nothing is happening here! var currentOffer = -1 funcdisplayNextOffer() {
    guard currentOffer + 1 < offerViews.count else {
        return} currentOffer += 1 offerViews[currentOffer]. Display (atViewController: self) // Only the mapping occurs here and only the required elements}Copy the code

Note, however, that lazy sequences will not be cached. This means that if offerViews[0] is used twice, the entire mapping process will also be performed twice. If you want to fetch some elements more than once, put them in a normal array.

Why does this work?

While they look amazing when used, the internal implementation of delay sequences is not as complicated as it seems.

If we print the type of the second example, we can see that even though our lazy-mapped Collection looks like a normal Collection, we are dealing with a different type:

letlazyMap = Array(1... 1000).lazy.map {$0* 2}print(lazyMap) // LazyMapCollection<Array<Int>, Int>
letlazyMap = Array(1... 1000).lazy.filter {$0 % 2 == 0 }.map { $0* 2}print(lazyMap) // LazyMapCollection<LazyFilterCollection<Array<Int>>, Int> The second argument is the map operation's conversion function.Copy the code

Looking at Swift’s source code, we can see its non-urgency by the fact that these methods don’t actually do anything other than return a new type:

(I will use LazySequence rather than LazyCollections code as an example because they are very similar in characteristics. If you don’t understand how Sequences work, take a look at this Apple article.)

Extension LazySequenceProtocol {/// Return a 'LazyMapSequence' type instead of 'Sequence'. /// Each time the result is read one base element by the 'transform' method, /// they will be lazily evaluated. @inlinable public func map<U>(_ transform: @escaping (Elements.Element) -> U) -> LazyMapSequence<Self.Elements, U> {return LazyMapSequence(_base: self.elements, transform: transform)
    }
}
Copy the code

Such magic comes from the internal implementation of these unique types. For example, if we look at LazyMapSequence and LazyFilterSequence, we can see that they are just regular Sequences that store an operation and apply their corresponding immediate methods only during iteration:

/ / _base is original Sequence extension LazyMapSequence. The Iterator: IteratorProtocol, Sequence { @inlinable public mutating func next() -> Element? {return _base.next().map(_transform)
    }
}
Copy the code
extension LazyFilterSequence.Iterator: IteratorProtocol, Sequence {
    @inlinable
    public mutating func next() -> Element? {
        while let n = _base.next() {
            if _predicate(n) {
                return n
            }
        }
        return nil
    }
}
Copy the code

LazyCollectionPerformance dilemma of

It would have been nice to end here, but it’s important to know that lazy sequences are actually flawed — especially if the underlying type is Collection.

In our original example, our method gets the first three addresses that satisfy a condition. This can also be simplified to a single line function by chaining lazy operations together:

let homeAddresses = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)
Copy the code

But let’s see how this particular example compares to direct execution:

allAddresses.filter { $0.identifier == "HOME" }.prefix(3) // ~0.11 secs
Array(allAddresses.lazy.filter { $0.identifier == "HOME"}. The prefix (3)) / / ~ 0.22 secsCopy the code

Even though the lazy version stops immediately after three addresses are found, it executes twice as fast as the rush version!

The unfortunate reason is the subtle difference between Sequences and Collections. Intercepting the head elements of a Sequence is as simple as moving the required elements to a single Array, but slicing Collections requires knowing the index of the end bit of the slice required:

public func prefix(_ maxLength: Int) -> SubSequence {
    _precondition(maxLength >= 0, "Can't take a prefix of negative length from a collection")
    let end = index(startIndex, offsetBy: maxLength, limitedBy: endIndex) ?? endIndex
    returnself[startIndex..<end] } @inlinable public subscript(bounds: Range<Index>) -> Slice<Self> { _failEarlyRangeCheck(bounds, bounds: startIndex.. <endIndex)return Slice(base: self, bounds: bounds)
}
Copy the code

The problem is that in Collection terminology, endIndex is not the index of the last element, but the index after the last element (index(startIndex, offsetBy:maxLength)). For our lazy filter function, this means that in order to cut to get the first three home addresses, we have to find four home addresses — they may not even exist.

This document, Certain lazy Types, illustrates this problem:

/// - Note: Get 'endIndex', get 'last', and /// any method that relies on 'endIndex' or on the number of elements in the collection header to move, /// may not match the performance guaranteed by the 'Collection' protocol. /// So you know, for '${Self}'The common operation of an instance /// may be more than the complexity described in the documentation. public struct LazyPrefixWhileCollection<Base: Collection> {Copy the code

Worse, because a Slice is just a window of the original Collection, So converting it to Array requires calling the function on the count property of the Collection using the lazy filter method — but since the lazy.filter(_:) operation does not comply with the RandomAccessCollection protocol, Count can only be found by traversing the entire Collection.

Due to the lack of caching for the Lazy Sequence, this causes the entire filtering/slicing process to occur again. Thus, if the fourth element does not exist or is too far away from the third element, the lazy version will perform twice as fast as the original.

The good news is that this can be avoided – if you are not sure whether your lazy operation will run in a reasonable amount of time, you can ensure efficiency by treating the result as a Sequence. This removes the reverse traversal feature of BidirectionalCollection, but ensures that forward operations will once again be fast.

let sequence: AnySequence = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)
letResult = Array(sequence) // ~ 0.004s!Copy the code

Conclusion

Using lazy objects allows you to write high-performance, complex things quickly — at the cost of knowing Swift’s internal mechanics to prevent major problems. Like all features, they have great advantages and equal disadvantages, and in this case, you need to understand the major differences between Sequences and Collections and use the best features from both. Once mastered, mapping to specific elements becomes very simple and intuitive.

Follow me on Twitter @rocktheBruno and let me know if you’d like to share any corrections or suggestions.

References and excellent articles

Filter.swift SR-4164 LazyPrefixWhileCollection LazySequenceProtocol Sequence

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.