mac*_*die 9 arrays algorithm diff
我正在尝试在更新表的数据时仅应用最少量的更改(UITableView当然,这是一个iOS应用程序和表视图,但我不认为它在这里是相关的).这些更改包括添加新项目,删除旧项目以及将一些现有项目移动到其他位置而不更新其内容.我知道在SO上有类似的问题,但是大多数问题只考虑添加和删除,现有的要么被忽略要么只是重新加载.
大多数情况下,移动涉及的内容不超过现有元素,表格最多可包含500个元素.
数组中的项是唯一的.
我可以通过从旧数组中的项集合中减去新数组中的项集来轻松获取添加的项.相反的操作将产生一组已删除的项目.
所以问题归结为找到具有相同元素的两个数组之间的最小差异.
[one, two, three, four]
[one, three, four, two]
区分这些数组应该导致从索引1到3的移动.
该算法不知道是否只有一个这样的移动.同样的变化可能是:
[one, two, three, four, five]
[one, four, five, three, two]
这应该导致将索引1移动到4和2到3,而不是向左移动3和4两个索引,因为这可能导致移动300个项目,而实际上更改应该更简单.在将视觉变化应用于视图方面,即.这可能需要重新计算单元格高度或执行大量动画和其他相关操作.我想避免它们.作为示例 - 将项目标记为收藏,导致将项目移动到列表顶部或300项目大约需要400毫秒.这是因为我正在使用的算法,例如,100个项目向上移动一个索引,一个移动到索引0,其他199个未被触及.如果我取消标记它,一个项目会向下移动100个索引,这很好,但这是完美的,但非常罕见的情况.
我已经尝试在旧数组中查找项目索引,检查它是否在新数组中发生了变化.如果有变化我将项目从新索引移动到旧索引,记录相反的变化并比较数组,直到元素顺序相等.但这有时会导致移动实际上没有变化的大块物品,具体取决于这些物品的位置.
任何想法或指针？也许改进的Levenshtein距离算法？未经修改的人可以为此工作吗？如果是这样,我可能不得不以某种形式实现它.
橡皮鸭谈到:
考虑找到所有未更改的项目序列并移动所有其他项目.这可能是正确的方向吗？
我有一个想法，不知道它是否可行..只有我的两分钱。如果您要实现一个类似于数组项上最长公共子序列的算法怎么样？
这个想法是找到保持初始序列的大数据“子串”，首先是最大的。一旦您覆盖了“长序列”中一定阈值百分比的项目，就可以应用更简单的算法来解决剩余的问题。
抱歉，说得比较模糊，这只是一个建议。希望你能解决你的问题。