Оптимизация размера пакета на основе прошедшего времени между последовательными вызовами
Я начал играть с попыткой создать следующее:
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; } }
}
3 ответа
Основная проблема, которую я вижу здесь, - это создание "шкалы оптимальности", то есть почему вы считаете, что 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
Ранжирование, связанное с каждой конфигурацией, будет результатом установки данного отношения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.
Эти значения можно сравнить, и, таким образом, вы автоматически узнаете, что второй случай намного лучше первого.
Это всего лишь простой пример, но я думаю, что он дает достаточно хорошее представление о том, что является настоящей проблемой: настройка точного ранжирования, позволяющая точно определить, какая конфигурация лучше.
Я бы пошел с рейтингом подход, как предложил варокарбас.
Вот начальная реализация, чтобы вы начали:
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();
}
}
- Опишите целевую функцию
fкоторый отображает размер партииsи время выполненияt(s)на счетf(s,t(s)) - Попробуйте много
sзначения и оценкиf(s,t(s))для каждого - Выбрать
sзначение, которое максимизируетf