Good algorithm for reloading a batch of UICollectionView or UITableView changes?

Question

Setup: I have a UICollectionView or UITableView that’s backed by a simple array data source. I keep a copy of that data source in the controller.

Now, I get a notification from the system that there’s new data available. I get a new array where items may have been added, removed and changed positions.

So now I have two data objects:

• previous array that's in sync with what the UI is currently showing
• new array where items have been added, removed, moved

To get the UI in sync with the new array, I need to generate a bunch of UI calls. In case of UICollectionView, those are

- (void)insertItemsAtIndexPaths:(NSArray *)indexPaths
- (void)moveItemAtIndexPath:(NSIndexPath *)indexPath toIndexPath:(NSIndexPath *)newIndexPath
- (void)deleteItemsAtIndexPaths:(NSArray *)indexPaths

And there’s a similar set of methods for UITableView.

I specifically don’t want to reload the whole table because that’s more expensive than just working with a few items.

So, the question is: given the previous and new data source array, how do I generate the correct set of UI calls, and when do I "swap out" my old data source for the new?

Answer 1

I'd see this as largely equivalent to the diff / patch problem, where the aim is to find the minimal number of changes between one text file and another and then to apply those changes. In that case, the implementation defines the operations:

• add or insert
• delete
• change

... but not move. The reason for omitting move isn't immediately obvious to me but I'd strongly suspect that including move would require a very costly computation to find the optimal movement.

So, if we restrict the operations to those listed above, the Hunt-McIlroy algorithm described in An Algorithm for Differential File Comparison, or one of its descendents, would find a close-to-optimal set of changes.

The difference between your problem and the classic diff / patch is that you have a two-dimensional table, while diff / patch deals with a one-dimensional set of items (lines of text). The best way to convert the 2-D problem into the 1-D problem would depend on the particular characteristics of the changes that tend to be made in your data table.

For example, if the table is n rows by m columns and changes tend to be grouped in rows or rows are inserted or deleted as a whole, then you would likely be best to consider the table as if it was a text file and do the diff line by line. Alternatively, if changes tend to be grouped in columns or columns are inserted or deleted, you could do the diff column by column. If the alterations include inserting or deleting individual cells (which result in the subsequent cells shifting right or left as a result), you could treat the table as if each cell in the table was on a separate line of the text file, linearising the table in either row-first or column-first order.

Without knowing the details of your problem in this respect, however, my inclination would be to avoid premature optimisation. Thus, I'd tend to start by implementing the Hunt-McIlroy algorithm row-by-row if m < n, or column-by-column if n < m, then profile the application in use for a while before deciding that either a more sophisticated version of the algorithm or an alternative mapping of your problem to the Hunt-McIlroy solution was warranted.

A good discussion of a variety of diff algorithms can be found here on stackoverflow.

Answer 2

I have worked on an app that deals with a very similar problem that i was able to solve. I was expecting a complicated solution but it was really simple. Here is how you can solve it:

1) Create a new array in which you will receive new items and call it let us say 'moreItems', also synthesise it of course.

@property (nonatomic, readonly) NSMutableArray *moreItems;

2) In viewDidLoad of the ViewController that is linked with your TableView or CollectionView, alloc/init this array:

moreItems = [[NSMutableArray alloc] init];

3) Now you need to add your existing array let us say it was "items" to the new array that you have just created named 'moreItems'. You can do this using 'addObjectsFromArray'

[moreItems addObjectsFromArray:[channel items]];

'channel items' contains the objects it has received earlier and it will add these items to the newly created array called 'moreItems'. I am assuming you are collecting data from some web service, so you can implement this step in connectionDidFinsihLoading.

4) Now change your data source of TableView/CollectionView and replace it with the new array that is 'moreItems'

5) Next issue is that you don't want to reload the whole tableview and want to deal with new items. To have this functionality, you need to persist items. You can use archiving or core data whatever you are comfortable with.

6) The items that are already fetched, you will have to persist them let us say with archiving. And show them in the tableview when the user opens the app while it grabs more items that are updated on the web service.So first show the persisted items immediately and then handle the new items.

7) You need to look for some unique object, in my case it was the 'link' as every item has a different link and i can sort and handle them on this basis. You also need to use

- (BOOL) isEqual:(id)object

to compare the links on the web service and the links that are already in the tableview. This step is necessary because then your app won't add the items with links that are already in the tableview.

8) If there is some date associated with each item, you can use that date to sort them and show the new ones on top by using 'sortUsingComparator'

9) Also you need to use "[[self tableView] insertRowsAtIndexPath:rows withRowAnimation:UITableViewRowAnimationTop" to have that effect that shows user the new items have been added on top of the earlier ones.

Hope this helps.

Answer 3

I specifically don’t want to reload the whole table because that’s more expensive than just working with a few items.

Are you sure this is true? Unless you have pathological case where every single cell is visible on your screen and there are hundreds of them, I find it hard to believe how will the "efficient" way be any faster than the "brute force" way.

Calling reloadData will only ask your delegate to update those cells that will end up visible on screen, it will not cause the entire table view to recreate every single of its cells.

If you're implementing some methods that change the complexity of calculating dimensions (like tableView:heightForRowAtIndexPath) you won't get any benefit using "efficient" way since the table view will have to recalculate all its heights anyway.

I'm not sure if solutions you are looking for will fix the problem, but let's just hope that I'm terribly wrong.

Answer 4

If your data source already has diff information, UITableView reloadRowsAtIndexPaths:withRowAnimation: will make it less-performance intensive: