（ソートされたリストで）より高い値が見つかるまで、あらゆる種類のコレクションをすばやく検索する

Question

リストからすべてのアイテムをすばやく取得する方法を探しています。このリストには時間値が含まれており、特定の時間より前にすべてが必要です。 明らかに、注文されたリストは簡単でなければなりません。あなたが定義したものよりも高い値でリスト内の1つのアイテムを見つけたら、それは止めることができます。

私は高速であると主張しているが、ある時点までのすべての時間を見つけるための良い方法はありません。

私はこの方法（良いと速いもの）を作る方法を知っていましたが、最良の方法が何であるか分かりません。それを使用するための最良の方法はされていない、次のように私は現在、このキューを使用しています

（私が思うだろう）：

while (mDisposing == false) 
{ 
    if (this.mIdleChoresRunning == true) 
    { 
     try 
     { 
      if ((mIdleChoreQueue.First != null) && (Timing.IsTimeOutByTicksNow(mIdleChoreQueue.First.AddTime, mIdleChoreQueue.First.WaitTime))) 
      { 
       //var item = mIdleChoreQueue.Dequeue(); 
       var chore = mIdleChores[mIdleChoreQueue.First.IdleChoreIdentification]; 
       mIdleChoreQueue.First.AddTime = Environment.TickCount; 
       mIdleChoreQueue.First.WaitTime = chore.IdleMiliSeconds; 

       mTaskQueue.EnqueueTask(() => 
       //Task.Factory.StartNew(() => 
       { 
        chore.Execute(mIdleChoreQueue.First.Context); 
       }); 

       mIdleChoreQueue.UpdatePriority(mIdleChoreQueue.First, mIdleChoreQueue.First.AddTime + mIdleChoreQueue.First.WaitTime); 
      } 
      else 
      { 
       Thread.Sleep(10); 
      } 
     } 
     catch (Exception exception) 
     { 
      mLogger.Error("ExecuteIdleChores() EXCEPTION", exception); 
     } 
    } 
    else 
    { 
     Thread.Sleep(100); 
    } 
} 

は、私は、コレクションの種類を気にしない明確にするために、すべてのI .Where（）操作は本当に遅いですので

mIdleChoreList.Where(x => Timing.IsTimeOutByTicksNow(x.AddTime, x.WaitTime)); 

：希望は、より私の項目を取得（およびそれらを実行する）ためのより高速な方法です。

Answer 1

ソートされたリストについては、どのアイテムを見つけるための最も早い方法はbinary search（O（log n））です。

注：理論的には、基本的なWhere(x => ChekcTime(x))を含む、特定のポイント（それはO（n）自体）よりも前のアイテムのリストが必要なようです。

Answer 2

時間軸に基づいて項目を挿入する二重リンクリスト（c＃のソートリスト）を考えてみましょう。処理する項目はリストの最初の項目になります。アイテムを処理し、処理し、時間値を増やし、新しい時間値をリストに戻す必要がある場合は、アイテムを簡単に削除します。リストはソートされているので、アイテムは適切な場所に配置されます。最もオーバーヘッドは挿入時に発生します。

リンクリストの詳細はこちらC＃ https://msdn.microsoft.com/en-us/library/ms132319(v=vs.110).aspx カスタムクラスをリストに追加する場合は、カスタム比較クラスを使用できます。例えばプロパティ、TimeToExecute、およびIncrementValueを持つクラスを作成し、TimeToExecuteに基づいて挿入します。

バイナリ検索ツリー（C＃のソート済み辞書）を参照することもできます。ソートされた辞書とソートされたリストの違いは、ソートされた辞書での挿入が高速であることです。ただし、処理するアイテムの追跡/検索が遅くなります。 （あなたlinqのwhere句を使用することができますが、パフォーマンスは最速ではありません）。

ハッシュマップは、挿入の高速化の利点がありますが、ソートされた辞書のように、処理する値を探す必要があります。

あなたが探しているもの、つまり特定の時間を正確に把握している場合は、辞書/ハッシュマップが最適です。範囲を探している場合でも、辞書全体をスキャンする必要があります。