1

次の手順 (説明が続きます) は、非常に小さなリストでは問題なく機能しますが、リストに含まれるアイテムの数が多い (1/2 百万) 場合、アプリケーションは「応答なし」状態になり、完了するまでに約 2.5 分かかります (非常に悪い)時間）。少なくとも (最終的には) 1 億項目のリストを処理する必要があるアプリケーションを追加する可能性があります。

問題のある手順のコードは次のとおりです。

    public void removeItems(List<long> L, SortedList<long, List<long>> _subLists)
    {
        foreach (KeyValuePair<long, List<long>> kvp in _subLists)
        {
            foreach (long duplicate in kvp.Value)
            {
                int j = L.IndexOf(duplicate);
                L.RemoveRange(j,(int)kvp.Key); 

            }
        }
    }

L は long 値のリストです。_subLists は、各値が L からの値のリストであるソートされたリストであり、いくつかの違いの算術級数シリーズを開始します (関係ありません)。その値に関連付けられたキーは、値に含まれる系列の長さです。

例：

L = {1,2,3,5,6,7,18,20,21} _subLists = {2,<20>} {3,<1,5>}

この手順は、単純に L から算術級数級数を削除します。

4

3 に答える 3

10

ビッグ O 表記でのこの手順の実行時間は n^2 になります。これはかなり遅く、リストの 1 つに 1 億のエントリがある場合は、実行時間が遅くなることが予想されます。ここにはスタック オーバーフローの問題はありません。これだけの量のデータを繰り返すのは単に遅いだけです。ここで質問が見当たりません。これをより速くしようとしていますか? もしそうなら、ネストされた for ループが間違いなく問題です。

于 2009-05-11T14:58:22.820 に答える
8

あなたの問題は、非常にコストのかかる操作である L から多くのアイテムを削除していることです。アイテムが削除されるたびに、メモリがコピーされ、削除されたアイテムの上にあるすべてのアイテムが下に移動します。削除するアイテムが多く、シャッフルするアイテムが多いほど、時間がかかります。メモリはパフォーマンスのボトルネックであり、RAM は CPU よりも遅く実行されます。また、ディスクにページングしている場合は、実際に遅くなります。

どうすればこれを改善できますか。

最も簡単なオプションは、アイテムを削除するときにパフォーマンスが向上する L のコンテナーを使用することです。たとえば、LinkedList です。LinkedLists は、要素が削除されたときにアイテムをメモリ内で移動する必要はありませんが、データを格納するためにより多くのメモリが必要です (値ごとに 2 つのポインター)。これがオーバーヘッドが大きすぎる場合は、LinkedList <List <long>>代わりにそれぞれList <long>が最大数の値を保持するようにします。

または、削除アルゴリズムを変更して、リスト L を反復処理し、_subLists にない値を含む新しいリストを作成します。_subLists がデータを格納する方法を変更して、範囲内のアイテムをより迅速に検索できるようにすることができます。

于 2009-05-11T15:11:30.347 に答える
0

もし可能なら：

A) L をソートされた連結リストに変換します。O: n * ログ (n)

B) サブリストを並べ替えられたリストのペアに変換します。最初の項目は L のシーケンスの # であり (投稿されたコード スニペットでは重複しています)、2 番目の項目はシーケンスの長さです。O: n * ログ (n)

C) サブリストを使用して L の 1 回のパスを実行し、L の特定の場所で削除する要素の数を決定します。どちらのリストでも後戻りしないように、両方のリストがソートされているという事実を利用します。の上

使用できる場合は、これから O: n * log(n) の複雑さを取得できるはずです。もちろん、問題のすべての詳細について 100% 確信があるわけではありません。たとえば、L を重複させることはできますか? もしそうなら、サブリストの順序は重要ですか? これらの ?s への回答によっては、そのようなアルゴリズムを破棄または変更することを余儀なくされる場合があります。また、これは明らかにより多くのメモリを使用します。

于 2009-05-11T15:59:45.853 に答える