任意の格子によるLINQグループのコレクション

Question

私は非常に基本的な何かを逃している場合はお詫び申し上げます。

格子値がバケットの最小値を表す所定の格子配列の場合、値の配列をグループ化する最良の方法は何か。

double[] lattice = { 2.3, 2.8, 4.1, 4.7 }; 
double[] values = { 2.35, 2.4, 2.6, 3, 3.8, 4.5, 5.0, 8.1 }; 

GroupByLattice(values, lattice); 

GroupByLatticeは次のようになりIGroupings返すよう：

2.3 : { 2.35, 2.4, 2.6 } 
2.8 : { 3, 3.8 } 
4.1 : { 4.5 } 
4.7 : { 5.0, 8.1 } 

が編集：

を私はLINQと十分な緑のだが、これは私はいくつかのアップでできる最善であることを照会します。

values.GroupBy(curr => lattice.First(lat => curr > lat)) 

この問題：

• すべてが最初のバケットで終わる - 私はなぜ（最初のバケットがそれぞれのケースを満たしているのか）理解できますが、これらのインプレース操作で自分の頭を包み込むのは難しい私が実際に望む述語。ドミトリーBychenkoは偉大な答えを提供

  、私はちょうどに望んでいた：私は、LINQクエリの内部でLINQクエリを持つことが

死後のソリューションと結果は非常にパフォーマンスのではないだろうと思われる

将来この回答に出くわすかもしれない人々のためにいくつかのフォローアップを提供する。私はもともと、解決しようとしていた：How can I simplify a huge dataset for plotting?

私の最初の試みは実際にはかなり近かった。私の格子はすでに注文されていると私は単純に.First(...)すべてが順調と良いです.Last(...)

すなわち

values.GroupBy(curr => lattice.Last(lat => curr > lat)) 

に変更することが必要ですが、ドミトリーのソリューションを実行する方法をはるかに優れについて興味がありました。私は0.25間隔で格子を持つ10000倍のランダムなセットでそれをテストしました。 WOW ...ええと

Mine: 602ms 
Dmitrys: 3ms 

：

（私は.Select(...)が公正それを維持するドミトリーの溶液から変換引き出された）20回のランの平均が結果を吐き出します！これは200倍の速度向上です。 200x！私はこれを数回実行し、タイムスタンプ（信頼できる.ToArray()レスキュー）の前にLINQ文が評価されていることを確認するために、デバッガで検査しなければなりませんでした。私は今それを言うつもりです、この同じタスクを実行するために探している誰もが最も確かlatticeががをソートであることを提供し、この方法論

Answer 1

を使用する必要がありますあなたはArray.BinarySearchを使用することができます（それはArray.Sort(lattice)で配列をソートするのは簡単です）：

double[] lattice = { 2.3, 2.8, 4.1, 4.7 }; 
    double[] values = { 2.35, 2.4, 2.6, 3, 3.8, 4.5, 5.0, 8.1 }; 

    var result = values 
    .GroupBy(item => { 
     int index = Array.BinarySearch(lattice, item); 

     return index >= 0 ? lattice[index] : lattice[~index - 1]; 
    }) 
    .Select(chunk => String.Format("{0} : [{1}]", 
     chunk.Key, String.Join(", ", chunk))); 

テスト

Console.Write(String.Join(Environment.NewLine, result)); 

成果

2.3 : [2.35, 2.4, 2.6] 
    2.8 : [3, 3.8] 
    4.1 : [4.5] 
    4.7 : [5, 8.1] 

Answer 2

あなたが今までより速く、それが必要な場合は、それらの両方がソートされている場合、あなたは一度だけの配列を反復処理することができます。

double[] lattice = { 2.3, 2.8, 4.1, 4.7 }; 
double[] values = { 2.35, 2.4, 2.6, 3, 3.8, 4.5, 5.0, 8.1 }; 

var result = new List<double>[lattice.Length]; // array of lists 

for (int l = lattice.Length - 1, v = values.Length - 1; l >= 0; l--) // starts from last elements 
{ 
    result[l] = new List<double>(values.Length/lattice.Length * 2); // optional initial capacity of the list 

    for (; v >= 0 && values[v] >= lattice[l]; v--) 
    { 
     result[l].Insert(0, values[v]); 
    } 
}