最初に不足している要素を順序付けられた順序で取得する効率的な方法はありますか？

Question

私は{1、3、5、6、8,9}のような順序付けられたシーケンスを持っています。 は今、私はこのようにそれをやっている：

public static int GetRegisterNumber<T>(this IQueryable<T> enumerable, Func<T, bool> whereFunc, Func<T, int?> selectFunc) 
{ 
    var regNums = enumerable.OrderBy(selectFunc).Where(whereFunc).ToArray(); 

    if (regNums.Count() == 0) 
    { 
     return 1; 
    } 

    for (int i = 0; i < regNums.Count(); i++) 
    { 
     if (i + 1 != regNums[i]) 
     { 
      return regNums[i].Value + 1; 
     } 
    } 

    return regNums.Last().Value + 1; 
} 

しかし、私ははるかに高速な方法があると思います。助言がありますか？

Answer 1

編集：私はちょうどenumerableがIQueryable<T>ですが、selectFuncとwhereFuncはタイプFunc<T, _>であることに気づきました。これにより、バージョンのOrderByとWhereが呼び出されます。代わりにExpression<Func<T, _>>に切り替えることをお勧めします。

あなたが最初regNumsを注文したくない場合は、ここではO（n）のゴルフスタイルのソリューションです：う

1. 、int?にキャストすることによってMax：線で

   var max = regNums.Max(i => (int?)i) ?? 0; 
   return Enumerable.Range(1, max + 1) 
          .Except(regNums) 
          .Min(); 
   

   は、 regNumsが空の場合はnullを返し、合体すると0になります。

2. すべての可能なレジスタのシーケンスを作成します（フルの場合は次の値も含めます）。

3. 現在のレジスタのセットを減算します。

Answer 2

提案：コードをプロファイラで実行してください。それであなたはどこが遅いのか分かります。直観的に、OrderByはこのプログラムで最も遅いものです。しかし、最も遅いものについての直感は、しばしば非常に間違っています。プロファイラを使用します。

もちろん、このプログラムの大きな非効率性も排除する必要があります。 Count（）は、シーケンスを再列挙してカウントすることを忘れないでください。 count（）は、あなたが最後にカウントした時からシーケンスを変更していないことを知りません！おそらく、毎回それを再計算するのではなく、カウントを格納するか、配列を持っているので長さを使用します。

Answer 3

私はおそらく以下のように見ています。 Whereは（セレクタは、正直に言うことができますよう）外に行うことができます。

あなたは1から開始することが予想される場合は：

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    int expected = 1; 
    foreach (T item in enumerable) { 
     if (selectFunc(item) != expected) return expected; 
     expected++; 
    } 
    return expected; 
} 

リスト内の最初の項目で起動するには：

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    bool first = true; 
    int prev = -1; 
    foreach (T item in enumerable) 
    { 
     int val = selectFunc(item); 
     if(first) { 
      prev = val; 
      first = false; 
     } else if (val != prev + 1) { 
      return prev + 1; 
     } 
     prev = val; 
    } 
    return first ? 1 : prev + 1; 
} 

nullを処理する方法がわからないので、私はしませんでした。これはを1回だけと繰り返し、すべてをバッファリングしないことに注意してください。

Answer 4

前述したように、まずプロファイラを使用して、どこが遅いかを調べます。シーケンスが本当に大きく、順序が遅い場合はradix sortというO（kn）を使用できます。ここでkは最大桁数、nはシーケンス内の要素数です。比較に基づく並べ替えアルゴリズムは通常O（n logn）です。

このようにして、アルゴリズム全体はO（kn）になります。これはnに応じて漸近的に速く、結果的にスケーラビリティが向上します。あなたが繰り返しこの操作を実行している場合

var upperBoundValue = values.Last() + 1; 
var firstMissingItem = Enumerable.Range(1, upperBoundValue).Except(values).First(); 

、あなたがしていた最後の場所にインデックスを格納することで、プロセスを最適化することができます：値の入力シーケンスがすでにソートされ、どの程度と仮定すると

Answer 5

あなたがギャップを発見したシーケンス、そしてそこから次の反復を開始します。

Answer 6

なぜバイナリ検索のようなことをしないのですか？

リスト10個の要素があるとします。最初の要素を読んでください。次に、5番目の要素を読んでください。 5番目の要素が最初の要素+ 4でない場合は、欠落している数字があることがわかります。そうでなければ、存在しないことがわかります。次に、最初に見つからない要素が見つかるか、リストの最後に到達するまで、このように繰り返します。

これはもちろん、質問に明記されていないサイズを知っていることを前提としていますが、あなたはそれを知っておくべきです。

O（Nを記録）の代わりにO（n）の

Answer 7

あなたOrderByとWhereが既に適用されていると仮定すると：

int firstMissing = collection.TakeWhile((x, i) => x == ++i).LastOrDefault() + 1; 

Answer 8

あなたは、あなたの質問にLinqToSqlタグを置きます。私はあなたがこのIDを使って新しいレコードを作成できるように、 "最初に利用可能な" IDを探していると推測します。代わりにデータベースのIDENTITYをオンにすることを検討してください。