One of the most interesting of the WWDC 2018 videos was the Embracing Algorithms session which introduced a couple of interesting new ways to approach common problems using some of the additions provided in Swift.
EdenList for iOS was originally started in 2009 (which was based off of the original Mac project started in 2003), several years before Swift was announced, so it was inevitable that it was to be written in Objective-C. The method deleteCheckedItems is 20 lines of code which iterates through the list and removes any item which has been selected.
- (void) deleteCheckedItems
{
int recordsCount = [records count];
for (int i = recordsCount-1; i >= 0; i--)
{
NSDictionary *rowData = [self.records objectAtIndex: i];
if (rowData != NULL)
{
NSNumber *num = [rowData objectForKey: @"CheckBox"];
if (num != nil && [num boolValue] == YES)
{
[records removeObjectAtIndex: i];
}
}
}
[self updateVisibleRecords];
}
When I rewrote EdenList in Swift, I was able to reduce the amount of code for the same method by nearly half. This was certainly a nice boon to be working in Swift by writing less, but still readable, code.
func deleteCheckedItems() {
let recordsCount = self.records.count
for (index, record) in self.records.reversed().enumerated() {
if record.itemChecked == true {
// index is returned sequentially, not in reverse order, so the proper index needs to be calculated
let itemIndex = recordsCount - index - 1
self.records.remove(at: itemIndex)
}
}
self.updateVisibleRecords()
self.saveFile()
}
The Embracing Algorithms session displayed a couple of ways to write this functionality, first by starting with moving sequentially through the array, but then displaying another method which was closer to what I employed by going through the array in reverse. However, the session had an even simpler version than the algorithm I used.
func deleteSelection() {
for i in (0..<shapes.count).reversed() {
if shapes[i].isSelected {
shapes.remove(at: i)
}
}
}
Nice. However, as it was pointed out in the session, this algorithm results in a time complexity of O(n2) due to the for loop and then each remove(at:) method taking another O(n) operations. As we learned from our CS 102 class, an algorithm with O(n2) time complexity will grow exponentially, which results in a poor case for arbitrarily large data sets.
For an app like EdenList, any given list probably would not go much past a couple hundred items, but that does not discount other cases where the data sets could easily number in the millions or billions or more. Are there more effective methods? Indeed there are.
Another option to filter the contents of the array using Objective-C is by using a combination of an NSPredicate and NSMutableArray's filterUsingPredicate method. This greatly cuts down on the amount of necessary code.
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"CheckBox == %@", @YES];
[self.records filterUsingPredicate: predicate];
With the introduction of higher order functions (e.g. map, reduce, filter) in Swift, filtering the contents of an array can be easily accomplished with the filter function.
let filteredArray = someArray.filter { $0.someBoolAttribute == true }
However, there is yet another way to remove select items from an array in Swift. Enter the removeAll(where:) method which has a linear O(n) time complexity, far better than the quadratic time that the original algorithm required. The removeAll gains this efficiency by using a half-stable partition to move the items to delete to the end of the array and then removing the subrange at the end of the array, which is far cheaper than removing one item at a time and then having to readjust the ordering of the entire array.
func deleteCheckedItems() {
self.records.removeAll { $0.itemChecked }
self.updateVisibleRecords()
self.saveFile()
}
The final version of deleteCheckedItems has been slimmed down to a mere quarter of the original Objective-C version. Not only is the code much more concise, it is also much faster. Thus is the advantage of better algorithms, but taking advantage of the improvements in the latest version(s) of Swift.