Minimal change between two arrays

Question

I'm trying to apply only the minimal number of changes when table's data is updated (it's an iOS app and table view is the UITableView of course, but I don't think it's relevant here). Those changes include adding new items, removing old ones and also moving some existing ones to a different position without updating their content. I know there are similar questions on SO, but most of them only take the adds and removes into account and existing ones are either ignored or simply reloaded.

Mostly the moves involve not more than a few existing elements and the table can have up to 500 elements.

Items in the arrays are unique.

I can easily get added items by subtracting the set of items in new array from the set of items in the old array. And the opposite operation will yield a set of deleted items.

So the problem comes down to finding the minimal differences between two arrays having the same elements.

[one, two, three, four]
[one, three, four, two]

Diffing those arrays should result in just a move from index 1 to 3.

The algorithm doesn't know if there's only one such move. Just as well the change can be:

[one, two, three, four, five]
[one, four, five, three, two]

Which should result in moving index 1 to 4 and 2 to 3, not moving 3 and 4 two indexes to the left, because that could result in moving 300 items, when in fact the change should be much simpler. In terms of applying the visual change to the view, that is. That may require recalculating cell heights or performing lots of animations and other related operations. I would like to avoid them. As an example - marking an item as favorite that causes moving the item to top of the list or 300 items takes about 400 milliseconds. That's because with the algorithm I'm using currently, e.g. 100 items are moved one index up, one moved to index 0, 199 other are left untouched. If I unmark it, one item is moved 100 indices down and that's great, but that is the perfect, but a very rare, case.

I have tried finding item's index in old array, checking if it changed in the new array. If there were a change I moved the item from new index to old one, recorded the opposite change and compared arrays until there're equal in terms of element order. But that sometimes results in moving the huge chunks of items that actually were not changed, depending on those items' position.

So the question is: what can I do?

Any ideas or pointers? Maybe a modified Levenshtein distance algorithm? Could the unmodified one work for that? I'll probably have to implement it in one form or another if so.

---

Rubber duck talked:

Thinking about finding all unchanged sequences of items and moving around all the other items. Could it be the right direction?

Answer 1

I have an idea, don't know if it would work.. Just my two cents. How about if you would implement an algorithm similar to the longest common subsequences on your array items.

The idea would be to find large "substrings" of data that have kept the initial sequence, the largest ones first. Once you've covered a certain threshold percent of items in 'long sequences' apply a more trivial algorithm for solving the remaining problems.

Sorry for being rather vague, it's just meant to be a sugestion. Hope you solve your problem.