Swift Coding Challenge: Incremental Updates to Views

UITableView and UICollectionView are two very common classes we all use for our iOS apps. If we are storing our data in CoreData, we may not get incremental update information when the data we are displaying changes (see Ray Wenderlich's tutorial for NSFetchedResultsController if you haven't already). What's the problem?

Well imagine you have 100,000 cells in your table or collection view. When one of them changes, reloading all of the data feels very heavy handed. Not only is it a performance problem, but if you can supply the changes in the context of move, insert, delete iOS will do some nice animations for you right out of the box. 

I had this problem with Yearn, so I wrote a quick a dirty algorithm that takes two arrays and figures out the deltas (remove, insert, and move) so that it can pass them along to the view. The good news was that it ran just fine. Until Apple took Photos on the Mac out of beta. All of a sudden people's iPhoto libraries got a LOT bigger, and updates got SLOW as they went from a thousand or so photos to tens of thousands. 

The graph shows the number of seconds taken to generate the deltas. You can see it goes from "choppy" at 1000 to "the developer is an idiot" at 10,000.  

So whilst working on the new version I focused on this piece of code as it's pretty core to the user experience. I came up with another simple solution that was scaling much more nicely. 

Screen Shot 2015-05-15 at 14.22.53.png

You can see I had given up testing the naive implementation at 10,000, but the new algorithm is just taking a third of a second at that point. Not really getting interesting until 100,000.

I'm going to go ahead with my new algorithm but I have only had two stabs at this so far, and it just doesn't seem very Swift-y. Below is an XCode Test with a slot for you to implement your own algorithm. There are performance tests so you can benchmark against my two solutions. It's in GIST so feel free to fork and share your version, or post it in the comments. I'd love to see what you come up with (anything at all, including perhaps worse but interesting strategies). 

Just navigate down to 

    //This implementation is intentionally left blank... so you can add your own

And have at it. Both my implementations are there for your reference (and horror).