Project Euler problem 14 (longest Collatz sequence) in Swift 3

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.")
    }
    }

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(first: T, next: @escaping (T) -> T?) -> UnfoldSequence

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  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.

StackExchange Code Review Q#157362, answer score: 8