c# - 根据连续调用之间耗时优化批量大小

Question

我已经开始尝试创建以下内容:

public static IEnumerable<List<T>> OptimizedBatches<T>(this IEnumerable<T> items)

那么这个扩展方法的客户端会像这样使用它:

foreach (var list in extracter.EnumerateAll().OptimizedBatches()) 
{
   // at some unknown batch size, process time starts to 
   // increase at an exponential rate
}

这是一个例子:

batch length         time
    1                 100ms
    2                 102ms
    4                 110ms
    8                 111ms
    16                118ms
    32                119ms
    64                134ms
    128               500ms <-- doubled length but time it took more than doubled
    256               1100ms <-- oh no!!

从上面可以看出，最佳批处理长度是 64，因为 64/134 是最佳的长度/时间比。

所以问题是使用什么算法根据迭代器步骤之间的连续时间自动选择最佳批处理长度？

这是我目前所拥有的——还没有完成...

class LengthOptimizer
{
    private Stopwatch sw;
    private int length = 1;
    private List<RateRecord> rateRecords = new List<RateRecord>();

    public int Length
    {
        get
        {
            if (sw == null)
            {
                length = 1;
                sw = new Stopwatch();
            }
            else
            {
                sw.Stop();
                rateRecords.Add(new RateRecord { Length = length, ElapsedMilliseconds = sw.ElapsedMilliseconds });
                length = rateRecords.OrderByDescending(c => c.Rate).First().Length;
            }
            sw.Start();
            return length;
        }
    }
}

struct RateRecord
{
    public int Length { get; set; }
    public long ElapsedMilliseconds { get; set; }
    public float Rate { get { return ((float)Length) / ElapsedMilliseconds; } }
}

Answer 1

我在这里看到的主要问题是创建“优化尺度”，也就是说，为什么您认为 32 -> 119 毫秒是可以接受的，而 256 -> 1100 毫秒不是；或者为什么某些配置比其他配置更好。

完成此操作后，算法将很简单:只需返回每个输入条件的排名值，并根据“哪个获得更高的值”做出决策。

创建此量表的第一步是找出能更好地描述您正在寻找的理想行为的变量。一个简单的第一种方法:长度/时间。也就是说，根据您的输入:

batch length           time             ratio1
    1                 100ms              0.01
    2                 102ms              0.019  
    4                 110ms              0.036  
    8                 111ms              0.072
    16                118ms              0.136
    32                119ms              0.269  
    64                134ms              0.478
    128               500ms              0.256
    256               1100ms             0.233

ratio1越大越好。从逻辑上讲，长度为 32 的 0.269 与长度为 128 的 0.256 是不同的，因此必须考虑更多信息。

您可能会创建一个更复杂的排名比率，以更好地加权两个相关变量(例如，尝试不同的指数)。但我认为解决这个问题的最佳方法是创建一个“区域”系统并从中计算通用排名。示例:

Zone 1 -> length from 1 to 8; ideal ratio for this zone = 0.1
Zone 2 -> length from 9 to 32; ideal ratio for this zone = 0.3
Zone 3 -> length from 33 to 64; ideal ratio for this zone = 0.45
Zone 4 -> length from 65 to 256; ideal ratio for this zone = 0.35

与每个配置相关的排名将是将给定比率 1 与给定区域的理想值相比较的结果。

2      102ms        0.019 -> (zone 1) 0.019/0.1 = 0.19 (or 1.9 in a 0-10 scale)
16     118ms        0.136 -> (zone 2) 0.136/0.3 = 0.45 (or 4.5 in a 0-10 scale)  
etc.

可以比较这些值，因此您会自动知道第二种情况比第一种情况好得多。

这只是一个简单的例子，但我想这足以让我们深入了解这里的真正问题是什么:设置准确的排名可以完美地识别哪种配置更好。