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

存在以下问题：

• 所有内容都会进入第一个桶 - 我能理解为什么（当然每个后续的情况都满足第一个桶），但我很难理解这些原地操作，以获得我实际想要的谓词。
• 我怀疑在LINQ查询内部使用另一个LINQ查询性能不佳。

事后解决方案和结果：

Dmitry Bychenko提供了一个很好的答案，我只是想为那些将来可能遇到这个答案的人提供一些跟进。我最初尝试解决的是：如何简化用于绘图的大型数据集？

首先，我的第一次尝试其实已经非常接近了。由于我的格子已经被排序，所以我只需要将.First( ... )更改为.Last( ... )

即：

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

虽然这很好，但我想知道Dmitry的解决方案能够表现得更好多少。我使用了一个随机的10000个双精度浮点数集合，并且间隔为0.25的格子进行了测试。（为了公平起见，我从Dmitry的解决方案中删除了.Select(...)转换）

20次运行的平均值给出了结果：

Mine: 602ms
Dmitrys: 3ms

哇...太棒了！速度提高了200倍。200倍！我运行了几次并在调试器中检查才确信LINQ语句在时间戳之前被评估（可靠的.ToArray()拯救了我）。我现在要说，任何想完成相同任务的人都应该绝对使用这种方法。

- darkpbj

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] 

- Dmitry Bychenko

---

在分组之前，您需要对非精确匹配进行反转，否则精确匹配将导致它成为自己的组，而不是该匹配的组。这也是一个现实中应该被提取到命名方法中的东西，而不是尝试在行内执行类似操作的东西。 - Servy

这很酷——易于插入和测试，并且似乎在各种不同的情况下都能正常工作。在我接受之前，我只需要花几分钟来理解这里发生了什么，但这已经开始让整个LINQ更加清晰明了了。 - darkpbj

@Servy：我明白了，谢谢！在处理浮点数时，精确相等是很容易被忽视的情况。 - Dmitry Bychenko

@DmitryBychenko 的回答已经编辑过了，与我之前尝试的方法相比，这是一个非常快速的解决方案！ - darkpbj

@darkpbj：渐近是在大规模上统治的东西。当枚举（如Last等）为O(N)时，二分查找仅为log(N)。 - Dmitry Bychenko

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

- Slai