0

あるリストのアイテムを別のリストから除外する方法について、かなり具体的な質問があります。Except() などの一般的なアプローチは機能しません。その理由は次のとおりです。

  • リスト内の重複に「偶数」インデックスがある場合 - THIS 要素と NEXT 要素を削除する必要があります。
  • リスト内の重複に「奇数」のインデックスがある場合-この要素とその前の1つの要素を削除する必要があります**。
  • リスト内に同じ重複が多数出現する可能性があります。つまり、1 つは「奇数」インデックス、もう 1 つは「偶数」インデックスである可能性があります。

自分で作成したので、解決策を求めているわけではありません。ただし、このメソッドを何度も実行した後、「ANTS パフォーマンス プロファイラー」は、メソッドが実行時間全体の 75% (40 秒中 30 秒) を経過したことを示しています。質問は次のとおりです。同じ操作を実行するためのより高速な方法はありますか? 現在のコードを最適化しようとしましたが、まだパフォーマンスが不足しています。ここにあります：

private void removedoubles(List<int> exclude, List<int> listcopy)
{
    for (int j = 0; j < exclude.Count(); j++)
    {
        for (int i = 0; i < listcopy.Count(); i++)
        {
            if (listcopy[i] == exclude[j])
            {
                if (i % 2 == 0) // even
                {
                    //listcopy.RemoveRange(i, i + 1);
                    listcopy.RemoveAt(i);
                    listcopy.RemoveAt(i);
                    i = i - 1;
                }
                else //odd
                {
                    //listcopy.RemoveRange(i - 1, i);
                    listcopy.RemoveAt(i - 1);
                    listcopy.RemoveAt(i - 1);
                    i = i - 2;
                }
            }
        }
    }
}

どこ：

  • 除外 - 重複のみを含むリスト。このリストには、最大 30 個の要素が含まれる場合があります。
  • listcopy - 重複をチェックする必要があるリスト。「除外」との重複が見つかった場合 → 削除操作を行います。このリストには、最大 2000 個の要素が含まれる場合があります。

LINQ が役立つと思いますが、その構文がよくわかりません。

4

4 に答える 4

5

より高速な方法 ( O(n)) は、次のようにすることです。

  1. excludeリストを調べて( HashSet)O(n)にする
  2. チェックでは、テスト対象の要素がセット内にあるかどうかを確認します (再びO(n))。 a 内の存在のテストは であるためHashSetですO(1)。

アルゴリズムを変更して、excludeコレクションがHashSet最初から になるようにすることもできます。このようにして、ステップ 1 を省略して、さらに高速化することができます。

(あなたの現在の方法はO(n^2)です。)

編集:
別のアイデアは次のとおりです:おそらく、いくつかのリストのコピーを作成し、このメソッドでそれを変更しますか? （パラメータ名に基づいて推測します。）次に、次のように変更できます。元の配列をメソッドに渡し、メソッドに新しい配列を割り当てて返すようにします（メソッドのシグネチャは、のようなものにする必要がありますprivate List<int> getWithoutDoubles(HashSet<int> exclude, List<int> original)）。

編集:
次の方法で入力データを再編成すると、さらに高速になる可能性があります: 項目は常にペア (偶数インデックス + 次の奇数インデックス) で削除されるため、事前にペアにする必要があります。ints のリストが int のペアのリストになるようにします。このようにして、あなたの方法は次のようになります：

private List<Tuple<int, int>> getWithoutDoubles(
              HashSet<int> exclude, List<Tuple<int, int>> original)
{
    return original.Where(xy => (!exclude.Contains(xy.Item1) &&
                                 !exclude.Contains(xy.Item2)))
           .ToList();
}

(最初または 2 番目のアイテムが除外コレクションにあるペアを削除します)。の代わりにTuple、アイテムをカスタム タイプにパックすることができます。

于 2012-05-10T09:02:17.340 に答える
3

結果を取得する別の方法を次に示します。

var a = new List<int> {1, 2, 3, 4, 5};

var b = new List<int> {1, 2, 3};

var c = (from i in a let found = b.Any(j => j == i) where !found select i).ToList();

c には 4,5 が含まれます

于 2013-04-09T21:37:50.933 に答える
2

ループを逆にして、ループが0から始まり、 0になるようにします。これにより、いずれかのケースで.Count - 1変更する必要がなくなり、コレクションごとに1回だけ評価されます。iCount

于 2012-05-10T08:56:37.427 に答える
1

List を LinkedList に変換して試してみることはできますか? List.RemoveAt() は、LinkedList.Remove() よりもコストがかかります。

于 2012-05-10T09:03:23.200 に答える