A set of LINQ groups with arbitrary lattice

Question

Sorry if I am missing something very basic.

For a given array of lattices, in which lattice values ​​represent the minimum for their bucket, the best way to group an array of values.

eg.

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);

so GroupByLattice returns IGroupings that look like this:

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

change

I'm green enough with LINQ queries that this is the best I can with:

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

Problems with this:

• It all ends in the first bucket - I can understand why (of course, the first bucket suits the occasion for each of them), but it's hard for me to wrap my head around these operations in place to get the predicate that I really want.
• I suspect LINQ query inside LINQ query will not be very efficient

Solution and results after Mortem:

, , . : ?

-, . , a .First( ... ) a .Last( ... )

.

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

, , . 10000 , 0,25. ( .Select(...) , )

20 :

Mine: 602ms
Dmitrys: 3ms

Uh... WOW!. 200 . 200x! , , LINQ (Trusty .ToArray() ). , , , , ,

Answer 1

, lattice ( Array.Sort(lattice)), Array.BinarySearch:

  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]);
    }
}