Recently, a friend of mine asked me to teach him some Swift following the news of the language going open source. I have grabbed the latest Xcode 7 beta 2 and went ahead with a mission to remind myself a syntax and try out the latest Swift 2 additions. Inspired by Protocol-Oriented Programming WWDC session I decided to build a protocol-oriented diff tool for various types of files.
To be able to perform diff for text files one have to solve longest common subsequence problem first. There is an excellent article about the topic on Word Aligned. I will not go any deeper into that, since it is not required to understand the post. Because I did not want to waste too much time building the algorithm myself, I decided to use premade one from Rosetta Code. I quickly ported it to Swift 2, made it into
String extension and run the tests to see whether it performs as expected.
Since I was using a dynamic programming solution the complexity class of the algorithm should be $O(n^2$). Surely my computer is powerful enough to handle this, isn’t it? I have generated two random strings of 500 characters each, ran the tests and… could not believe my eyes. The code wrapped in
measureBlock: took 8.899 seconds to find the solution. What went wrong?