优化批量大小

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

主要的问题，我在这里看到的是创造了“optimity规模”，也就是你为什么认为32 - > 119ms可以接受，256 - > 1100ms不可以;或为什么某些配置比其他配置更好。

一旦完成，算法将很简单：只是返回每个输入条件的排名值，并根据“哪一个获得更高的价值”做出决定。

创建此比例尺的第一步是找出更好地描述您正在寻找的理想行为的变量。简单的第一种方法：长度/时间。也就是说，从您的输入：

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 

比率越大越好。从逻辑上讲，长度为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. 

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

这只是一个简单的例子，但我想提供一个足够好的洞察力，看看这里真正的问题：建立一个准确的排名，以便完美地识别哪个配置更好。

Answer 2

我会去像varocarbas建议的排名方法。

这里是一个初步实现，让你开始：

public sealed class DataFlowOptimizer<T> 
{ 
    private readonly IEnumerable<T> _collection; 
    private RateRecord bestRate = RateRecord.Default; 
    private uint batchLength = 1; 

    private struct RateRecord 
    { 
     public static RateRecord Default = new RateRecord { Length = 1, ElapsedTicks = 0 }; 
     private float _rate; 

     public int Length { get; set; } 
     public long ElapsedTicks { get; set; } 
     public float Rate 
     { 
      get 
      { 
       if(_rate == default(float) && ElapsedTicks > 0) 
       { 
        _rate = ((float)Length)/ElapsedTicks; 
       } 

       return _rate; 
      } 
     } 
    } 

    public DataFlowOptimizer(IEnumerable<T> collection) 
    { 
     _collection = collection; 
    } 

    public int BatchLength { get { return (int)batchLength; } } 
    public float Rate { get { return bestRate.Rate; } } 

    public IEnumerable<IList<T>> GetBatch() 
    { 
     var stopwatch = new Stopwatch(); 

     var batch = new List<T>(); 
     var benchmarks = new List<RateRecord>(5); 
     IEnumerator<T> enumerator = null; 

     try 
     { 
      enumerator = _collection.GetEnumerator(); 

      uint count = 0; 
      stopwatch.Start(); 

      while(enumerator.MoveNext()) 
      { 
       if(count == batchLength) 
       { 
        benchmarks.Add(new RateRecord { Length = BatchLength, ElapsedTicks = stopwatch.ElapsedTicks }); 

        var currentBatch = batch.ToList(); 
        batch.Clear(); 

        if(benchmarks.Count == 10) 
        { 
         var currentRate = benchmarks.Average(x => x.Rate); 
         if(currentRate > bestRate.Rate) 
         { 
          bestRate = new RateRecord { Length = BatchLength, ElapsedTicks = (long)benchmarks.Average(x => x.ElapsedTicks) }; 
          batchLength = NextPowerOf2(batchLength); 
         } 
         // Set margin of error at 10% 
         else if((bestRate.Rate * .9) > currentRate) 
         { 
          // Shift the current length and make sure it's >= 1 
          var currentPowOf2 = ((batchLength >> 1) | 1); 
          batchLength = PreviousPowerOf2(currentPowOf2); 
         } 

         benchmarks.Clear(); 
        } 
        count = 0; 
        stopwatch.Restart(); 

        yield return currentBatch; 
       } 

       batch.Add(enumerator.Current); 
       count++; 
      } 
     } 
     finally 
     { 
      if(enumerator != null) 
       enumerator.Dispose(); 
     } 

     stopwatch.Stop(); 
    } 

    uint PreviousPowerOf2(uint x) 
    { 
     x |= (x >> 1); 
     x |= (x >> 2); 
     x |= (x >> 4); 
     x |= (x >> 8); 
     x |= (x >> 16); 

     return x - (x >> 1); 
    } 

    uint NextPowerOf2(uint x) 
    { 
     x |= (x >> 1); 
     x |= (x >> 2); 
     x |= (x >> 4); 
     x |= (x >> 8); 
     x |= (x >> 16); 

     return (x+1); 
    } 
} 

示例程序LinqPad：

public IEnumerable<int> GetData() 
{ 
    return Enumerable.Range(0, 100000000); 
} 

void Main() 
{ 
    var optimizer = new DataFlowOptimizer<int>(GetData()); 

    foreach(var batch in optimizer.GetBatch()) 
    { 
     string.Format("Length: {0} Rate {1}", optimizer.BatchLength, optimizer.Rate).Dump(); 
    } 
} 

Answer 3

1. 描述一个目标函数f映射的批次数量s和运行时t(s)得分f(s,t(s))
2. 尝试很多s值和评估f(s,t(s))为每一个
3. 选择s价值最大化f