Databases
StackOverflow2013
Postsdbo
POMinimal change between two arrays
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMinimal change between two arrays
    primarykey
    data
    text
    <p>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 <code>UITableView</code> of course, but I don't think it's relevant here). Those changes include adding new items, removing old ones and also <strong>moving some existing ones to a different position without updating their content</strong>. 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.</p> <p>Mostly the moves involve not more than a few existing elements and the table can have up to 500 elements.</p> <p>Items in the arrays are unique.</p> <p>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.</p> <p>So the problem comes down to finding the minimal differences between two arrays having the same elements.</p> <pre><code>[one, two, three, four] [one, three, four, two] </code></pre> <p>Diffing those arrays should result in just a move from index 1 to 3.</p> <p>The algorithm doesn't know if there's only one such move. Just as well the change can be:</p> <pre><code>[one, two, three, four, five] [one, four, five, three, two] </code></pre> <p>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. <strong>In terms of applying the visual change to the view, that is.</strong> 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.</p> <p>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.</p> <h2>So the question is: what can I do?</h2> <p>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.</p> <hr> <p>Rubber duck talked:</p> <p>Thinking about finding all unchanged sequences of items and moving around all the other items. Could it be the right direction?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USmacbirdie
    1. USmacbirdie
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMinimal change between two arrays
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMinimal change between two arrays
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POMinimal change between two arrays
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO[this might help](http://stackoverflow.com/questions/10529049/is-there-a-specialized-algorithm-faster-than-quicksort-to-reorder-data-acegbdf) (in particular the accepted answer: find the cycles and swap).
      singulars
      1. POMinimal change between two arrays
      1. USassylias
    2. COI don't understand yet. In your first example, I get that conceptually it is a move from index 1 to 3. However, in practice if you update a table you will need to touch all of memory locations 1, 2, and 3. What am I missing?
      singulars
      1. POMinimal change between two arrays
      1. USmicans
    3. COIt's actually not about memory locations of 1, 2 and 3. It's more of a problem of applying the minimal number of changes in the table view's cells, because the less are modified, the less operations the view has to perform to update smoothly. If I move or reload 299 items instead of one that happened to be moved from the end to beginning, table view will have to invoke e.g. 299 cell height recalculations or effectively 299 separate object animations instead of just one. Edited the question for clarity.
      singulars
      1. POMinimal change between two arrays
      1. USmacbirdie
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload