18

私の会社の猫飼いアプリケーションは、猫の車列を追跡しています。定期的に(それぞれが) と比較previousOrderし、変化を cat-wrangler に通知する必要があります。currentOrderArrayList<Cat>

各猫は一意で、各リストに 1 回しか表示されません (またはまったく表示されません)。ほとんどの場合、previousOrderとcurrentOrderリストは同じ内容を同じ順序で持っていますが、次のいずれかが発生する可能性があります (頻度の高いものから低いものへ)。

  1. 猫の順番が完全に入れ替わる
  2. 猫は個別にリスト内を上下に移動します
  3. 車列の特定の時点で、新しい猫が加わります
  4. 猫は車列を離れます

これは、私には編集距離の問題のように見えます。previousOrder理想的には、一致させるために必要な手順を決定するアルゴリズムを探していますcurrentOrder。

  • 位置Fluffyに移動12
  • Snuggles位置に挿入37
  • 消去Mr. Chubbs
  • 等

アルゴリズムは、シナリオ #1 も認識する必要があります。この場合、新しい順序が完全に伝達されます。

これに対する最善のアプローチは何ですか？

(この投稿とその投稿は同様の質問を提起しますが、どちらもソートされたリストを扱っています。私のものは順序付けられていますが、ソートされていません。)

編集

レーベンシュタイン アルゴリズムは素晴らしい提案ですが、マトリックスを作成するための時間/空間の要件が気になります。私の主な目標は、できるだけ早く変更を決定して伝達することです。追加を見つけて、「これが新しい猫で、これが現在の注文です」という行に沿ってメッセージを送信するよりも高速です。

4

5 に答える 5

10

これは、2 つのリストをマージするためにまとめたアルゴリズムoldですnew。これは最もエレガントでも効率的でもありませんが、私が使用しているデータには問題ないようです。

newは最新のデータ リストであり、oldは に変換する必要がある古いリストですnew。アルゴリズムは、oldリストに対して操作を実行します - それに応じて項目の削除、移動、および挿入を行います。

for(item in old)
    if (new does not contain item)
        remove item from old

for(item in new)
    if (item exists in old)
        if (position(item, old) == position(item, new))
            continue // next loop iteration
        else
            move old item to position(item, new)
    else
        insert new item into old at position(item, new)

2 番目のループで項目の位置をより予測しやすくするために、削除はすべて前もって行われます。

この背後にある原動力は、サーバーからのデータのリストを<table>ブラウザー DOM の行と同期することでした (javascript を使用)。データが変更されるたびにテーブル全体を再描画したくないため、これが必要でした。リスト間の違いは小さい可能性が高く、影響を受けるのは 1 行または 2 行のみです。データを探しているアルゴリズムではない可能性があります。そうでない場合は、お知らせください。これを削除します。

おそらく、このために行うことができるいくつかの最適化があります。しかし、それは私と私が扱っているデータにとって十分なパフォーマンスと予測可能性を備えています.

于 2011-06-01T13:54:20.383 に答える
2

レーベンシュタイン距離計量。

http://www.levenshtein.net/

于 2011-06-01T13:06:11.093 に答える
2

これを解決する効率的な方法は、動的計画法を使用することです。ウィキペディアには、密接に関連する問題の疑似コードがあります: Computing Levenshtein distance。

実際の操作を追跡し、「スクランブル」操作を組み込むことはそれほど難しくありません。

于 2011-06-01T13:07:37.943 に答える
1

質問者が Java ソリューションを探していたことは知っていますが、C# で実装するアルゴリズムを探しているときにこの質問に出くわしました。

これは、単純な IListDifference 値の列挙を生成する私のソリューションです: ItemAddedDifference、ItemRemovedDifference、または ItemMovedDifference のいずれかです。

ソース リストの作業コピーを使用して、アイテムごとに、ターゲット リストと一致するように変換するために必要な変更を確立します。

public class ListComparer<T>
    {
        public IEnumerable<IListDifference> Compare(IEnumerable<T> source, IEnumerable<T> target)
        {
            var copy = new List<T>(source);

            for (var i = 0; i < target.Count(); i++)
            {
                var currentItemsMatch = false;

                while (!currentItemsMatch)
                {
                    if (i < copy.Count && copy[i].Equals(target.ElementAt(i)))
                    {
                        currentItemsMatch = true;
                    }
                    else if (i == copy.Count())
                    {
                        // the target item's index is at the end of the source list
                        copy.Add(target.ElementAt(i));
                        yield return new ItemAddedDifference { Index = i };
                    }
                    else if (!target.Skip(i).Contains(copy[i]))
                    {
                        // the source item cannot be found in the remainder of the target, therefore
                        // the item in the source has been removed 
                        copy.RemoveAt(i);
                        yield return new ItemRemovedDifference { Index = i };
                    }
                    else if (!copy.Skip(i).Contains(target.ElementAt(i)))
                    {
                        // the target item cannot be found in the remainder of the source, therefore
                        // the item in the source has been displaced by a new item
                        copy.Insert(i, target.ElementAt(i));
                        yield return new ItemAddedDifference { Index = i };
                    }
                    else
                    {
                        // the item in the source has been displaced by an existing item
                        var sourceIndex = i + copy.Skip(i).IndexOf(target.ElementAt(i));
                        copy.Insert(i, copy.ElementAt(sourceIndex));
                        copy.RemoveAt(sourceIndex + 1);
                        yield return new ItemMovedDifference { FromIndex = sourceIndex, ToIndex = i };
                    }
                }
            }

            // Remove anything remaining in the source list
            for (var i = target.Count(); i < copy.Count; i++)
            {
                copy.RemoveAt(i);
                yield return new ItemRemovedDifference { Index = i };
            }
        }
    }

これが IEnumerable でカスタム拡張メソッドを使用していることに気付きました - 'IndexOf':

public static class EnumerableExtensions
{
    public static int IndexOf<T>(this IEnumerable<T> list, T item)
    {
        for (var i = 0; i < list.Count(); i++)
        {
            if (list.ElementAt(i).Equals(item))
            {
                return i;
            }
        }

        return -1;
    }
}
于 2014-03-07T20:31:10.557 に答える