Оптимизация размера партии на основе истекшего времени между последовательными вызовами

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 -> 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 

Чем больше отношение1, тем лучше. Логично, что это не то же самое, что 0,269 с 32 длиной, чем 0,256 с 128, и, следовательно, необходимо учитывать больше информации.

Возможно, вы создадите более сложный коэффициент ранжирования, который лучше взвешивает две вовлеченные переменные (например, пытается использовать разные показатели). Но я считаю, что наилучшим подходом к этой проблеме является создание системы «зон» и вычисление общего рейтинга из нее. Пример:

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 

ранжирование, связанное с каждой конфигурацией будет результатом сдачи данного ratio1 по отношению к идеальному значению для данной зоны.

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