UPGRADE YOUR SKILLS: Learn advanced Swift and SwiftUI on Hacking with Swift+! >>

Write better code with Swift Algorithms

Write faster, simpler, safer Swift code with this powerful open-source package.

Paul Hudson       @twostraws

Swift’s standard library is packed with types and functions to solve the most common code problems quickly and efficiently, but it doesn’t cover everything. So, for more advanced needs we need to turn to Swift Algorithms: Apple’s open source package of sequence and collection algorithms, tuned for maximum performance and flexibility.

With the 2021 Advent of Code happening right now, this is a great time to see how Swift Algorithms can help you write faster, simpler, and safer code. There’s functionality for uniquing sequences, chunking them, selecting several random elements, compacting them, and more, and most return new, highly-optimized sequence types that are more efficient than flattening everything to a simple array.

Plus, Apple has said that Swift Algorithms provides an opportunity to explore algorithmic problems and solutions before graduating them into the main standard library – you get better code today, and a look in at what the standard library might become in the future. What’s not to like?

Best of all, adding Swift Algorithms to your Xcode project takes only a few moments: go to the File menu, choose Add Packages, select Apple Swift Packages, then select “swift-algorithms” and click Add Package. Now just add import Algorithms to your code, and you’re all set!

In this article I’m going to pick out just a little of what Swift Algorithms can already do, focusing on nine particular algorithms I find most useful. Let’s get to it…

  • Prefer to watch this as a video? Here you go!
Hacking with Swift is sponsored by RevenueCat

SPONSORED Take the pain out of configuring and testing your paywalls. RevenueCat's Paywalls allow you to remotely configure your entire paywall view without any code changes or app updates.

Learn more here

Sponsor Hacking with Swift and reach the world's largest Swift community!

Chaining sequences

If you have two arrays of data and want to loop over them both, you might write something like this:

let names1 = ["Jane", "Elizabeth", "Mary", "Kitty"]
let names2 = ["Daphne", "Eloise", "Francesca", "Hyacinth"]

for name in names1 + names2 {
    print(name)
}

That will print all eight names, but in doing so we’ve had to create a new, temporary array by adding names1 and names2 together. It’s a small cost here, but if your arrays were much larger this would be quite wasteful.

Swift Algorithms has a solution, called chain(): it creates a new sequence by concatenating two others, without performing any additional allocations. Here’s how it looks:

for name in chain(names1, names2) {
    print(name)
}

Behind the scenes chain() stores references to your existing two sequences, and effectively just ties their iterators together so that as one ends another one begins.

This works with other sequence types too, so we can efficiently check whether a value lies within two different ranges:

let tooLow = 0...20
let tooHigh = 80...100
let outOfBounds = chain(tooLow, tooHigh)

let value = 35
print(outOfBounds.contains(value))

Even better, this works across any kinds of sequence, so we could chain a range and an array:

let reservedSeats = 0...50
let unavailableSeats = [61, 68, 75, 76, 77, 92]
let disallowed = chain(reservedSeats, unavailableSeats)

let requestedSeat = 39
print(disallowed.contains(requestedSeat))

Chunking sequences

Ever wanted to break up a sequence into equal chunks, or perhaps based on some criteria? Swift Algorithms provides a few variants of chunking functions that do just that, and they turn complex, error-prone work into one-liners with extreme efficiency.

As an example, we could create an array of students with names and grade letters like this:

struct Student {
    let name: String
    let grade: String
}

let results = [
    Student(name: "Taylor", grade: "A"),
    Student(name: "Sophie", grade: "A"),
    Student(name: "Bella", grade: "B"),
    Student(name: "Rajesh", grade: "C"),
    Student(name: "Tony", grade: "C"),
    Student(name: "Theresa", grade: "D"),
    Student(name: "Boris", grade: "F")
]

Using Swift Algorithms, we could chunk that results array based on grades then print them out neatly:

let studentsByGrade = results.chunked(on: \.grade)

for (grade, students) in studentsByGrade {
    print("Grade \(grade)")

    for student in students {
        print("\t\(student.name)")
    }

    print()
}

This will automatically create a new chunk whenever the value being checked changes, so you need to be careful if your value jumps around. In our code above the student grades all appear in order – the two As are together, as are the two Cs – so this isn’t a problem, but if we wanted to chunk by student name we should sort them first to make sure the starting letters are grouped together:

let studentsByName = results.sorted { $0.name < $1.name }.chunked(on: \.name.first!)

for (firstLetter, students) in studentsByName {
    print(firstLetter)

    for student in students {
        print("\t\(student.name)")
    }

    print()
}

There’s an alternative chunking method that lets us split up a sequence by number of items in each chunk. For example we could split our students up into pairs like this:

let pairs = results.chunks(ofCount: 2)

for pair in pairs {
    let names = ListFormatter.localizedString(byJoining: pair.map(\.name))
    print(names)
}

That will print “Taylor and Sophie”, “Bella and Rajesh”, and “Tony and Theresa”, but because “Boris” doesn’t have a pair it will be a single-element chunk.

Be careful: chunking data will return an array slice rather than an array, because it’s more efficient. This means if you try and read indices like 0 and 1 for our pair you’ll hit a problem. So, avoid this kind of code:

let pairs = results.chunks(ofCount: 2)

for pair in pairs {
    if pair.count == 2 {
        print("\(pair[0].name) and \(pair[1].name) are working together")
    } else {
        print("\(pair[0].name) is working alone")
    }
}

If you specifically need an array rather than an array slice, convert each item before the loop, like this:

let pairs = results.chunks(ofCount: 2).map(Array.init)

Random sampling

One of my personal favorite features of Swift Algorithms is the randomSample(count:) method, and its counterpart randomStableSample(count:), both of which are enhanced forms of randomElement() that instead select N random, non-duplicate elements.

Of the two, randomSample(count:) is the fastest, and it works on all sequences. However, it doesn’t retain the order of your elements, so you’ll get back N random, non-duplicate elements in any order.

For example:

let lotteryBalls = 1...50
let winningNumbers = lotteryBalls.randomSample(count: 7)
print(winningNumbers)

If you specify a count equal to or greater than the number of items in your sequence, the entire sequence will be returned – still in a random order.

An alternative is randomStableSample(count:), which works a little differently. First, it works only on collections, because it needs to know how many items it’s choosing from, and it also runs a little slower than randomSample(count:). However, it does retain the order of your items, which can be helpful:

let people = ["Chidi", "Eleanor", "Jason", "Tahani"]
let selected = people.randomStableSample(count: 2)
print(selected)

Striding over a sequence

Swift Algorithms adds a new striding(by:) method that moves over a sequence in steps of a certain size, similar to stride(from:through:by) except it works directly on sequences and so is a lot more efficient.

First, the simple example so you can see a direct comparison from old to new. This code prints out all the odd numbers from 1 through 1000:

let numbers = 1...1000
let oddNumbers = numbers.striding(by: 2)

for oddNumber in oddNumbers {
    print(oddNumber)
}

In comparison, we can get the same result using stride(from:through:by:), like this:

let oddNumbers = stride(from: numbers.lowerBound, through: numbers.upperBound, by: 2)

The advantage of using striding() is that it works with more complex collections, such as strings and array slices. So, we can efficiently pull out parts of a string like this:

let inputString = "a1b2c3d4e5"
let letters = inputString.striding(by: 2)

for letter in letters {
    print(letter)
}

I use this recently to handle decrypting columnar transposition ciphers, where plaintext letters are spaced out at fixed intervals in a string.

Finding unique elements

Swift Algorithms includes helpful functionality to find unique elements in a sequence, either based on their natural uniqueness (if your type conforms to Hashable), or using a function you specify.

Let’s start with a simple example: you ask a bunch of people for a number they consider lucky, and get a range of answers. If you want to loop over each unique response, you might do this:

let allNumbers = [3, 7, 8, 8, 7, 67, 8, 7, 13, 8, 3, 7, 31]
let uniqueNumbers = allNumbers.uniqued().sorted()

for number in uniqueNumbers {
    print("\(number) is a lucky number")
}

If you need something more advanced, uniqued(on:) lets us provide a function that accepts one element from the sequence, and return any kind of Hashable data that should be used in the uniquing test. Using key paths as functions, we can code to go through an array of cities and choose only one city per country:

struct City {
    let name: String
    let country: String
}

let destinations = [
    City(name: "Hamburg", country: "Germany"),
    City(name: "Kyoto", country: "Japan"),
    City(name: "Osaka", country: "Japan"),
    City(name: "Naples", country: "Italy"),
    City(name: "Florence", country: "Italy"),
]

let selectedCities = destinations.uniqued(on: \.country)

for city in selectedCities {
    print("Visit \(city.name) in \(city.country)")
}

In this situation, uniqued(on:) will always return the first unique element of several options, so the above code will return Hamburg, Kyoto, and Naples.

Stripping out optionality

Swift standard library provides compactMap() for transforming an element into some kind of optional result, but then unwrapping that optional and removing any nils. However, it’s common to see compactMap { $0 } as a way of performing no transformation but just keeping the optional unwrap and removal steps, like this:

let numbers = [10, nil, 20, nil, 30]
let safeNumbers = numbers.compactMap { $0 }
print(safeNumbers.count)

That works, but Swift Algorithms provides a better version just called compacted():

let numbers = [10, nil, 20, nil, 30]
let safeNumbers = numbers.compacted()
print(safeNumbers.count)

Okay, so it’s only a few characters less to type, but it’s also much clearer what you mean – the $0 usage of compactMap() always felt more of a workaround than an intentional feature.

However, compacted() has another important benefit which is that it’s always lazy, as opposed to being lazy only when you request it. So, the work of unwrapping and removing will only happen when you actually use it, which makes it a lot more efficient when you chain operations together.

Improving nested loops

Nested loops let us loop over one sequence every time we loop over another, and Swift Algorithms provides a product() function that gives us extra control for that same situation.

For example, if we have two arrays of people and games, we could use product() to loop over every combination so that every person gets to play every game:

let people = ["Sophie", "Charlotte", "Maddie", "Sennen"]
let games = ["Mario Kart", "Boomerang Fu"]

let allOptions = product(people, games)

for option in allOptions {
    print("\(option.0) will play \(option.1)")
}

That prints “Sophie will play Mario Kart”, “Sophie will play Boomerang Fu”, “Charlotte will play Mario Kart”, “Charlotte will play Boomerang Fu”, and so on.

The first parameter to product() can be any sequence because it’s looped over once, but the second parameter needs to be a collection because it’s looped over repeatedly. Of course, you can also provide the same collection to both parameters if you want, meaning that we could print a complete set of multiplication tables like this:

let range = 1...12
let allMultiples = product(range, range)

for pair in allMultiples {
    print("\(pair.0) x \(pair.1) is \(pair.0 * pair.1)")
}

You might be think this is no better than using nested for loops, but the magic is that product() gives us a new collection that we can manipulate further. For example, perhaps we want to select 20 random questions from all possible multiplication tables, like this:

let range = 1...12
let questionCount = 20
let allMultiples = product(range, range).shuffled().prefix(questionCount)

for pair in allMultiples {
    print("\(pair.0) x \(pair.1) is \(pair.0 * pair.1)")
}

If you’ve been following this carefully, you might recognize that we can just use randomSample(count:) rather than shuffling and prefixing:

let allMultiples = product(range, range).randomSample(count: questionCount)

One slight downside to use product() right now is that it works with only two parameters, meaning that if you need to iterate over several collections then you need to nest your product() calls. So, we could make the world’s most tedious game of Cluedo/Clue like this:

let suspects = ["Colonel Mustard", "Professor Plum", "Mrs White"]
let locations = ["kitchen", "library", "study", "hall"]
let weapons = ["candlestick", "dagger", "lead pipe", "rope"]
let guesses = product(product(suspects, locations), weapons)

for guess in guesses {
    print("Was it \(guess.0.0) in the \(guess.0.1) with the \(guess.1)?")
}

That’s pretty much how my 8-year-old plays the game, so not a bad result for only a handful of lines of code!

Sliding windows into sequences

Another of my favorite additions in Swift Algorithms is the ability to read overlapping subsequences of a sequence, which is great for doing things like calculating moving averages across a sequence.

If you just want all neighboring pairs you can use the lazy adjacentPairs() method in an sequence, like this:

let numbers = (1...100).adjacentPairs()

for pair in numbers {
    print("Pair: \(pair.0) and \(pair.1)")
}

However, for more advanced uses there’s also a windows(ofCount:) method that lets you control how big your sliding window should be. So, we could make groups of 5 like this:

let numbers = (1...100).windows(ofCount: 5)

for group in numbers {
    let strings = group.map(String.init)
    print(ListFormatter.localizedString(byJoining: strings))
}

When that runs it will print “1, 2, 3, 4 and 5”, “2, 3, 4, 5 and 6”, “3, 4, 5, 6 and 7”, and so on. These are all subsequences of the original sequence, so once again it’s extremely efficient.

I used windows(ofCount:) recently while decoding a Vigenère cipher, because it allowed me to look through a huge string of letters and find all the repeating substrings.

Minimum and maximum

Finally, Swift Algorithms comes with enhanced methods for calculating the minimum and maximum values in a sequence. You can provide a custom test if you want, but if your sequence conforms to Comparable you’ll get the default test of <, like this:

let names = ["John", "Paul", "George", "Ringo"]

if let (first, last) = names.minAndMax() {
    print(first)
    print(last)
}

It also provides methods for reading multiple of the highest and lowest values at the same time, like this:

let scores = [42, 4, 23, 8, 16, 15]
let threeLowest = scores.min(count: 3)
print(threeLowest)

Internally that will sort and prefix or suffix the results if you’re trying to read more than 10% of the whole sequence, but otherwise it uses a faster algorithm – it just does the right thing automatically, like so much of Swift Algorithms.

And there’s more!

I’ve just touched on a handful of my favorites from Swift Algorithms, but there’s a whole lot more functionality waiting for you and it’s all as powerful as the examples we’ve just looked at.

To find out more, I encourage you to visit the Swift Algorithms repository on GitHub: https://github.com/apple/swift-algorithms – it’s all open source Swift code, so you can explore it for yourself and see just how they squeeze out so much efficiency from their code.

There’s also a video from WWDC21 that you’ll find useful: Meet the Swift Algorithms and Collections packages.

Now go forth and write better code – thanks to Swift Algorithms!

Hacking with Swift is sponsored by RevenueCat

SPONSORED Take the pain out of configuring and testing your paywalls. RevenueCat's Paywalls allow you to remotely configure your entire paywall view without any code changes or app updates.

Learn more here

Sponsor Hacking with Swift and reach the world's largest Swift community!

BUY OUR BOOKS
Buy Pro Swift Buy Pro SwiftUI Buy Swift Design Patterns Buy Testing Swift Buy Hacking with iOS Buy Swift Coding Challenges Buy Swift on Sundays Volume One Buy Server-Side Swift Buy Advanced iOS Volume One Buy Advanced iOS Volume Two Buy Advanced iOS Volume Three Buy Hacking with watchOS Buy Hacking with tvOS Buy Hacking with macOS Buy Dive Into SpriteKit Buy Swift in Sixty Seconds Buy Objective-C for Swift Developers Buy Beyond Code

Was this page useful? Let us know!

 
Unknown user

You are not logged in

Log in or create account
 

Link copied to your pasteboard.