優化批量大小

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