The main performance bottleneck of your code was already pointed out in the other answers: building lots of arrays (without need).
I'll like to point out how some Swift techniques can be used to achieve
the goal in a functional (and fast) way.
First, I would separate the computation of the next Collatz number into
a separate function:
func collatzFunc(n: Int64) -> Int64? {
if n == 1 {
return nil
} else if n % 2 == 0 {
return n/2
} else {
return 3*n + 1
}
}
or, using the conditional operator:
func collatzFunc(n: Int64) -> Int64? {
return n == 1 ? nil : n % 2 == 0 ? n/2 : 3*n + 1
}
(As already pointed out in other answers, we must operate on Int64
here). For reasons which become apparent shortly, this function returns nil
when called with 1, i.e. when the sequence "ends".
Now, instead of building an array with all elements, we build a
sequence, using sequence(first:next:)
from the Swift Standard Library:
Returns a sequence formed from first and repeated lazy applications of next.
func sequence<T>(first: T, next: @escaping (T) -> T?) -> UnfoldSequence<T, (T?, Bool)>
Our collatzFunc is exactly what is needed as the next parameter.
For example,
let seq = sequence(first: 13, next: collatzFunc)
creates the Collatz sequence starting at 13. But in contrast to your
function, all elements are evaluated lazily, i.e. on demand when
the sequence is enumerated.
for n in seq { print(n) }
would print that Collatz sequence. But we need only the length,
so we define a collatzLength function. A straightforward
implementation would be
func collatzLength(n: Int) -> Int {
var count = 0
for _ in sequence(first: Int64(n), next: collatzFunc) {
count += 1
}
return count
}
The for-loop enumerates the sequence and increments a count for
each element. Since the sequence element itself is not needed,
the "wildcard pattern" _ is used as the loop variable.
This can be written more concisely/functionally using
reduce():
func collatzLength(n: Int) -> Int {
return sequence(first: Int64(n), next: collatzFunc)
.reduce(0, { (count, _) in count + 1 })
}
Finally, we have to find the number (under one million) which has the
longest Collatz length. This can be done with a for-loop, as you did.
Alternatively, one can consider that as the maximum of all
(n, collatzLength(n)) pairs with respect to the second component:
let (maxN, maxLength) = (1...999_999)
.map { ($0, collatzLength(n: $0)) }
.max { $0.1 < $1.1 }!
This code, compiled with Xcode with optimization ("Release" configuration)
runs in about 0.8 seconds on my 1.2 GHz Intel Core m5 MacBook.
EBrown demonstrated
how to use caching/memoization to increase the performance.
Here is a similar but slightly different approach. Instead of
caching all computed values in a dictionary, cache only the
computed values for n up to a maximum value in an array.
With the cache array size equal to the maximal needed n (1 million
in our case), this turned out to be very fast.
let cacheSize = 1_000_000
var cache = [Int](repeating: 0, count: cacheSize)
cache[1] = 1
func collatzLengthCached(n: Int64) -> Int {
if let smallN = Int(exactly: n), smallN < cacheSize {
if cache[smallN] > 0 {
return cache[smallN]
}
let len = 1 + collatzLengthCached(n: collatzFunc(n: n)!)
cache[smallN] = len
return len
}
return 1 + collatzLengthCached(n: collatzFunc(n: n)!)
}
let (maxN, maxLength) = (1...999_999)
.map { ($0, collatzLengthCached(n: $0)) }
.max { $0.1 < $1.1 }!
This code, compiled with Xcode with optimization ("Release" configuration)
runs in about 0.08 seconds on my 1.2 GHz Intel Core m5 MacBook.
