テーブルのデータが更新されたときに最小限の変更のみを適用しようとしています (これは iOS アプリであり、テーブル ビューはUITableViewもちろんですが、ここでは関係ないと思います)。これらの変更には、新しいアイテムの追加、古いアイテムの削除、コンテンツを更新せずに既存のアイテムを別の位置に移動することが含まれます。SO に同様の質問があることは知っていますが、それらのほとんどは追加と削除のみを考慮しており、既存のものは無視されるか、単にリロードされます。
ほとんどの場合、移動には数個の既存の要素しか含まれず、テーブルには最大 500 個の要素を含めることができます。
配列内の項目は一意です。
古い配列のアイテムのセットから新しい配列のアイテムのセットを差し引くことで、追加されたアイテムを簡単に取得できます。逆の操作では、削除されたアイテムのセットが生成されます。
したがって、問題は、同じ要素を持つ 2 つの配列間の最小の違いを見つけることに帰着します。
[one, two, three, four]
[one, three, four, two]
これらの配列を比較すると、インデックス 1 から 3 に移動するだけです。
アルゴリズムは、そのような動きが 1 つしかないかどうかを知りません。同様に、変更は次のようになります。
[one, two, three, four, five]
[one, four, five, three, two]
これにより、インデックス 1 が 4 および 2 が 3 に移動し、3 および 4 の 2 つのインデックスが左に移動することはなくなります。これは、実際には変更がはるかに簡単な場合でも、300 個のアイテムが移動する可能性があるためです。ビューに視覚的な変更を適用するという点では、つまり。これには、セルの高さを再計算するか、多くのアニメーションやその他の関連操作を実行する必要がある場合があります。私はそれらを避けたいと思います。例として、項目をお気に入りとしてマークすると、項目がリストの一番上または 300 項目に移動するのに約 400 ミリ秒かかります。これは、私が現在使用しているアルゴリズムでは、たとえば、100 個のアイテムが 1 インデックス上に移動され、1 個がインデックス 0 に移動され、199 個のアイテムがそのまま残されるためです。マークを外すと、1 つのアイテムが 100 インデックス下に移動されます。これは素晴らしいことですが、これは完璧ですが、非常にまれなケースです。
新しい配列で変更されたかどうかを確認して、古い配列でアイテムのインデックスを見つけようとしました。変更があった場合、アイテムを新しいインデックスから古いインデックスに移動し、反対の変更を記録し、要素の順序が等しくなるまで配列を比較しました。しかし、アイテムの位置によっては、実際には変更されていない膨大な量のアイテムが移動する場合があります。
質問は次のとおりです。私は何ができますか?
アイデアや指針はありますか？たぶん、修正されたレーベンシュタイン距離アルゴリズムですか？変更されていないものはそのために機能しますか？もしそうなら、私はおそらく何らかの形でそれを実装する必要があります。
ゴム製のアヒルは話しました：
変更されていないアイテムのシーケンスをすべて見つけて、他のすべてのアイテムを移動することを考えています。それは正しい方向でしょうか？