按比例分配(按比例分配)一组值的值

Question

我需要根据列表中"基础"值的相对权重编写将在列表中按比例分配值的代码.简单地将"基础"值除以"基础"值的总和,然后将该因子乘以原始值以按比例分配工作:

proratedValue = (basis / basisTotal) * prorationAmount;

但是,必须将此计算的结果舍入为整数值.舍入的效果意味着列表中所有项目的proratedValue总和可能与原始prorationAmount不同.

任何人都可以解释如何应用"无损"比例算法,该算法在列表中尽可能准确地按比例分配值,而不会出现舍入错误？

Answer 1

这里简单的算法草图......

1. 运行总计从零开始.
2. 对于第一项,您的标准"按总分基础划分,然后乘以比例".
3. 将运行总计的原始值存储在其他位置,然后在#2中添加刚刚计算的数量.
4. 将运行总计的旧值和新值四舍五入为整数(不要修改现有值,将它们四舍五入为单独的变量),并采用差异.
5. 在步骤4中计算的数字是分配给当前基础的值.
6. 每个基础重复步骤#2-5.

这保证按比例分配的总金额等于输入的比例金额,因为您实际上从未实际修改运行总计(您只需将其舍入值用于其他计算,您不会将其写回).现在处理之前整数舍入的问题,因为舍入误差将在运行总计中随时间累加,并最终在另一个方向上跨越舍入阈值.

基本示例:

Input basis: [0.2, 0.3, 0.3, 0.2]
Total prorate: 47

----

R used to indicate running total here:

R = 0

First basis:
  oldR = R [0]
  R += (0.2 / 1.0 * 47) [= 9.4]
  results[0] = int(R) - int(oldR) [= 9]

Second basis:
  oldR = R [9.4]
  R += (0.3 / 1.0 * 47) [+ 14.1, = 23.5 total]
  results[1] = int(R) - int(oldR) [23-9, = 14]

Third basis:
  oldR = R [23.5]
  R += (0.3 / 1.0 * 47) [+ 14.1, = 37.6 total]
  results[1] = int(R) - int(oldR) [38-23, = 15]

Fourth basis:
  oldR = R [37.6]
  R += (0.2 / 1.0 * 47) [+ 9.4, = 47 total]
  results[1] = int(R) - int(oldR) [47-38, = 9]

9+14+15+9 = 47

Answer 2

TL; DR算法具有最佳(+ 20%)可能的准确度,减慢70%.

Evaulated算法在这里被接受的答案中呈现以及回答类似性质的python问题.

• 分配1 - 基于Amber的算法
• 分配2 - 基于John Machin的算法
• 分发3 - 见下文
• 分发4 - Distribute 3的优化版本(例如,删除了LINQ,使用过的数组)

测试结果(10,000次迭代)

Algorithm    | Avg Abs Diff (x lowest) | Time (x lowest)     
------------------------------------------------------------------
Distribute 1 | 0.5282 (1.1992)         | 00:00:00.0906921 (1.0000)
Distribute 2 | 0.4526 (1.0275)         | 00:00:00.0963136 (1.0620)
Distribute 3 | 0.4405 (1.0000)         | 00:00:01.1689239 (12.8889)
Distribute 4 | 0.4405 (1.0000)         | 00:00:00.1548484 (1.7074)

方法3的准确度提高了19.9%,执行时间比预期慢70.7%.

分发3

尽最大努力尽可能准确地分配金额.

1. 正常分配权重
2. 增加具有最高误差的权重,直到实际分配量等于预期量

牺牲通过循环多次传递来提高准确性.

public static IEnumerable<int> Distribute3(IEnumerable<double> weights, int amount)
{
    var totalWeight = weights.Sum();
    var query = from w in weights
                let fraction = amount * (w / totalWeight)
                let integral = (int)Math.Floor(fraction)
                select Tuple.Create(integral, fraction);

    var result = query.ToList();
    var added = result.Sum(x => x.Item1);

    while (added < amount)
    {
        var maxError = result.Max(x => x.Item2 - x.Item1);
        var index = result.FindIndex(x => (x.Item2 - x.Item1) == maxError);
        result[index] = Tuple.Create(result[index].Item1 + 1, result[index].Item2);
        added += 1;
    }

    return result.Select(x => x.Item1);
}

分发4

public static IEnumerable<int> Distribute4(IEnumerable<double> weights, int amount)
{
    var totalWeight = weights.Sum();
    var length = weights.Count();

    var actual = new double[length];
    var error = new double[length];
    var rounded = new int[length];

    var added = 0;

    var i = 0;
    foreach (var w in weights)
    {
        actual[i] = amount * (w / totalWeight);
        rounded[i] = (int)Math.Floor(actual[i]);
        error[i] = actual[i] - rounded[i];
        added += rounded[i];
        i += 1;
    }

    while (added < amount)
    {
        var maxError = 0.0;
        var maxErrorIndex = -1;
        for(var e = 0; e  < length; ++e)
        {
            if (error[e] > maxError)
            {
                maxError = error[e];
                maxErrorIndex = e;
            }
        }

        rounded[maxErrorIndex] += 1;
        error[maxErrorIndex] -= 1;

        added += 1;
    }

    return rounded;
}

测试线束

static void Main(string[] args)
{
    Random r = new Random();

    Stopwatch[] time = new[] { new Stopwatch(), new Stopwatch(), new Stopwatch(), new Stopwatch() };

    double[][] results = new[] { new double[Iterations], new double[Iterations], new double[Iterations], new double[Iterations] };

    for (var i = 0; i < Iterations; ++i)
    {
        double[] weights = new double[r.Next(MinimumWeights, MaximumWeights)];
        for (var w = 0; w < weights.Length; ++w)
        {
            weights[w] = (r.NextDouble() * (MaximumWeight - MinimumWeight)) + MinimumWeight;
        }
        var amount = r.Next(MinimumAmount, MaximumAmount);

        var totalWeight = weights.Sum();
        var expected = weights.Select(w => (w / totalWeight) * amount).ToArray();

        Action<int, DistributeDelgate> runTest = (resultIndex, func) =>
            {
                time[resultIndex].Start();
                var result = func(weights, amount).ToArray();
                time[resultIndex].Stop();

                var total = result.Sum();

                if (total != amount)
                    throw new Exception("Invalid total");

                var diff = expected.Zip(result, (e, a) => Math.Abs(e - a)).Sum() / amount;

                results[resultIndex][i] = diff;
            };

        runTest(0, Distribute1);
        runTest(1, Distribute2);
        runTest(2, Distribute3);
        runTest(3, Distribute4);
    }
}