これはおそらくスタックオーバーフローの問題です

Question

実際に小さなリストでは、次の手順（説明が続きます）はうまくいきますが、リストに含まれる項目数が多い場合（1/2 million）、アプリケーションは「応答しません」状態になり、仕上げには約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は、長い値のリストです。 _subListsは並べ替えられたリストです。各値は、Lからの の値のリストであり、相違点（関連しない）の算術進行シリーズを開始します。 その値に関連付けられたキーは、値に含まれる系列の長さです。

例：

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

手順だけで、かなり遅く、1つがあなたが遅い実行時間を期待することができ、大きなO記法で、この手順の実行時間は、2をn ^うL.

Answer 1

から等差数列シリーズを削除しますリストの1億エントリがあります。ここでスタックオーバーフローの問題はありません。このデータを繰り返し処理するのは単純です。私は本当にここに質問が表示されません、あなたはこれをより速くするために探していますか？もしそうなら、ネストされたforループは間違いなく問題です。

Answer 2

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

これをどのように改善できますか？

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

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

Answer 3

可能な場合：

A）ソートされたリンクリストにLに変換します。 O：n * log（n）

B）サブリストをソートされたリストのペアに変換します。ここで、最初のアイテムはLのシーケンス内の＃（ポストされたコードスニペットの複製）で、2番目のアイテムはシーケンス。 O：n * log（n）

C）サブリストを使用してLを1回実行し、L内の所定の場所で削除する要素の数を決定します。両方のリストがバックトラックしないようにソートされているいずれかのリスト。O：n

O：n * log（n）の複雑さを利用できるようにする必要があります。 もちろん、問題の詳細については100％確信しているわけではありません。たとえば、Lに重複がありますか？もしそうなら、サブリストの順序は重要ですか？あなたは、それらの答えに応じて、そのようなアルゴリズムを排除したり修正したりすることを余儀なくされるかもしれません。また、これは明らかにより多くのメモリを使用します。