如何有效地划分排序列表 <double> 值

Question

我有一个双精度列表，它可能包含重复值并按升序排序，需要分成 X 个分区（其中 X 由用户提供），这样：

任何重复值都在同一分区内
分区尽可能包含相同数量的元素；和
保留值的原始顺序（值实际上与必须按顺序处理的事务的键相关联）。

考虑到在同一分区中保留重复值的要求，是否有有效的方法来做到这一点？

Answer 1

此代码没有像将相关代码组合在一起那样的任何智能：

假设，List 的长度为 L。

X = 3; Chunk Size = X;
data1 = Take[data, Chunk Size]
data2 = Skip chunk size members and take next X members;
repeat; 

public static IEnumerable<List<List<double>>>  GetSubList()
{
    List<double> values = new List<double> { 10.0, 15.0, 20.0, 20.0, 21.0 };
    List<List<double>> subPartition = new List<List<double>>();

    var X = 2;
    int chunkSize = X;
    int length = values.Count;

    if (length < X)
    {
       subPartition.Add(values);
       yield return subPartition;
       yield break;
    }

    subPartition.Add(values.Take(chunkSize).ToList());
    while (values.Skip(chunkSize).Any())
    {
        subPartition.Add(values.Skip(chunkSize).Take(X).ToList());
        chunkSize += X;
    }

    yield return subPartition;
}

Answer 2

假设回答我自己的问题的形式不错，这是我最终采用的方法：

1) 计算"ideal"分区大小：valuesCount / numPartitions
2) 第一个分区从索引 0
开始 3) 计算连续的潜在断点指数为：
lastBreakIndex + (unallocatedValuesCount / remainingPartitions)
4) 断点必须落在值的第一次出现处。如果不是，则将断点调整到第一次出现的值或下一个值，以较接近者为准。
5) 使用与每个分区的理想大小的偏差平方和作为质量指标。
6) 添加每个额外的断点时，尝试通过向前和向后移动一个 "value change" 并重新计算质量指标来连续调整每个先前的断点。如果指标较低，请保留更改并重试。

需要进行一些特殊情况检查，例如比请求的分区更少的价值中断。可能还有一些我没有考虑过的边缘情况。但是，这似乎很快就可以根据我尝试过的数据集给出合理的结果。

如何有效地划分排序列表 <double> 值

How to efficiently partition a sorted List<double> values

c#

partitioning

list