8
\$\begingroup\$

I was trying to solve Project Euler:Problem 14 using Swift 3, but it takes ages to give me an answer, which is a sign that my code is absolute garbage performance-wise. What could I do to increase the performance of the code?

import UIKit

/* The following iterative sequence is defined for the set of positive integers:

 n → n/2 (n is even)
 n → 3n + 1 (n is odd)

 Using the rule above and starting with 13, we generate the following sequence:

 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

 Which starting number, under one million, produces the longest chain?

 NOTE: Once the chain starts the terms are allowed to go above one million. */


func collatzSeq(starting: Int) -> [Int] {

    var collatzArray = [starting]

    while collatzArray.last != 1 {
        if collatzArray.last! % 2 == 0 {
            collatzArray.append(collatzArray.last!/2)
        } else {
            collatzArray.append((3*collatzArray.last!)+1)
        }
    }
    return collatzArray
}

var longestChain = 0
for index in 1...999999 {
    if collatzSeq(starting: index).count > longestChain {
        longestChain = index
        print("Starting at \(longestChain) produces the longest chain.")
    }
    }   
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Pretty interesting approach, thank you for sharing :D \$\endgroup\$ – Nox Mar 10 '17 at 8:30
6
\$\begingroup\$

A very simple optimization is to redo your collatzSeq() function to just return the count instead of building a million lists.

To do this, simply keep track of current value of the sequence and the count of the elements. When the current value reaches 1, return the count.

This avoids the enormous overhead of allocating a huge number of lists and inserting a bunch of elements, and deallocating the lists.

The next optimization is what Ebrown mentioned in his answer: memoization. Reusing the same values over and over means that you only need to do a million of the function evaluations in total.

\$\endgroup\$
6
\$\begingroup\$

The biggest performance impact you have is that you lack caching / memoization.

Consider the chain that starts at 3:

3 10 5 16 8 4 2 1

Then consider the chain that starts at 5:

5 16 8 4 2 1

The entire chain is the same from the 5 onward, as it should be, because we've defined a clear, non-stateful algorithm that means that no matter what any time we hit the number 5 or 4, etc., we'll end up with the same result.

Consider your example chain:

13 40 20 10 5 16 8 4 2 1

And now we have three chains that can be sped up already, but there are far more. The chain starting at 26 will then follow the exact same chain from the 13 onwards, likewise for the 52 chain which follows 26 onwards, etc. That's just from our 13. For each chain we cache, the chain that starts at \$2n\$ is already going to be significantly faster.

The best option here is to store the chain size of each index in a dictionary, then do a lookup if possible. Any time you build a new sequence (so with our 3 we would have built the sequences from 10, 5, 16, 8, and 4) you store the 'length' in the collatz memoization array.

You can do this easiest with recursion, have collatzSequence remove the while and simply have an if for the == 1 condition, and the % 2 == 0 condition. Then when you need a new calculation call collatzSequence again, and store the down-chain results in our dictionary/list/array, whatever data-structure you pick.

You don't need to store the entire chain itself, that's not a requirement of the problem. You only need to store the chain count.

I have a Java example here: Locating the largest Collatz Sequence with memoization, it's really ugly and there is plenty you could improve upon to do it better and more efficiently.

The Swift example might look something like the following (spoiler blocked, hover to reveal):

 var collatzCache = [Int: Int]()
 func collatzSeqLength(num: Int) -> Int {
     if let cacheLength = collatzCache[num] {
         return cacheLength
     }

     if num == 1 {
         return 1;
     }

     var newVal = num
     if num % 2 == 0 {
         newVal = num / 2
     } else {
         newVal = num * 3 + 1
     }

     let lastSeqLength = collatzSeqLength(num: newVal) + 1
     collatzCache[num] = lastSeqLength
     return collatzCache[num]!
 }

Test code:

for i in 1...100 {
    let len = collatzSeqLength(num: i)
    let lenOrig = collatzSeq(starting: i).count
    print("Seq length for \(i): \(len), \(lenOrig)")
}

Timing my code, roughly 0.48s in the playground. Timing your code is roughly 66.89s in the playground. Obviously we got a lot of speed improvement doing our memoization. Of course, we also want to fix the Int64 issue as mentioned in another answer, and once I've done so a new timing test indicates that running your version from 1...999 takes roughly the same time as my version from 1...99999...I would consider that a huge performance impact.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your help! this does indeed increase the performance immensely \$\endgroup\$ – Nox Mar 9 '17 at 20:02
4
\$\begingroup\$

Your program would not be portable to 32-bit platforms, where Int is equivalent to Int32. As pointed out in the collatz-sequence tag wiki, the Collatz sequence starting at 159487 contains a number that exceeds 231.

You should therefore use Int64 for elements of the Collatz sequence.

\$\endgroup\$
  • \$\begingroup\$ Thank you for pointing this out! I guess I will start being more careful about what type of value I should use \$\endgroup\$ – Nox Mar 9 '17 at 20:04
  • \$\begingroup\$ @Nyktox: The same happens with 64 bit, not that much later. Take as a consolation that your program in Swift crashes when a similar program in C, C++, Objective-C or Java would have silently given you the wrong result. \$\endgroup\$ – gnasher729 Mar 10 '17 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.