Last active
March 12, 2023 09:10
-
-
Save brascene/c5e2322e4905dfdcfa52f12c9f2e1bcd to your computer and use it in GitHub Desktop.
Get n-th fibonacci number in Swift
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
import CoreFoundation | |
// MARK: Without recursion | |
func fib(_ n: Int) -> Int { | |
guard n > 1 else { return n } | |
var arr = Array.init(repeating: 1, count: n) | |
for i in 2..<n { | |
arr[i] = arr[i - 1] + arr[i - 2] | |
} | |
return arr.last! | |
} | |
// MARK: With recursion (a lot faster) | |
func fibR(_ n: Int) -> Int { | |
guard n > 1 else { return n } | |
return fibR(n - 1) + fibR(n - 2) | |
} | |
// MARK: Helper function for measure execution time | |
public func measure(label: String? = nil, tests: Int = 1, printResults output: Bool = true, setup: @escaping () -> Void = { return }, _ block: @escaping () -> Void) -> Double { | |
guard tests > 0 else { fatalError("Number of tests must be greater than 0") } | |
var avgExecutionTime : CFAbsoluteTime = 0 | |
for _ in 1...tests { | |
setup() | |
let start = CFAbsoluteTimeGetCurrent() | |
block() | |
let end = CFAbsoluteTimeGetCurrent() | |
avgExecutionTime += end - start | |
} | |
avgExecutionTime /= CFAbsoluteTime(tests) | |
if output { | |
let avgTimeStr = "\(avgExecutionTime)".replacingOccurrences(of: "e|E", with: " × 10^", options: .regularExpression, range: nil) | |
if let label = label { | |
print(label, "▿") | |
print("\tExecution time: \(avgTimeStr)s") | |
print("\tNumber of tests: \(tests)\n") | |
} else { | |
print("Execution time: \(avgTimeStr)s") | |
print("Number of tests: \(tests)\n") | |
} | |
} | |
return avgExecutionTime | |
} | |
// MARK: Results | |
let timeNoR = measure(label: "Without recursion", printResults: true) { | |
let n = fib(10) | |
print("Without recursion: \(n)") | |
} | |
let timeR = measure(label: "Using recursion", printResults: true) { | |
let n = fibR(10) | |
print("Using recursion: \(n)") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment