Пропорционально распределить (пропорционально) значение по набору значений

Мне нужно написать код, который будет распределять значение по списку в зависимости от относительных весов "базовых" значений в списке. Простое разделение "базисных" значений на сумму "базисных" значений, а затем умножение фактора на исходное значение на пропорциональную работу в определенной степени:

proratedValue = (basis / basisTotal) * prorationAmount;

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

Может ли кто-нибудь объяснить, как применять "без потерь" алгоритм оценки, который пропорционально распределяет значение по списку как можно точнее, не испытывая ошибок округления?

6 ответов

Простой алгоритм эскиза здесь...

  • Иметь общее число, начинающееся с нуля.
  • Сделайте свой стандартный "разделите основу на общую базу, затем умножьте на количество долей" для первого элемента.
  • Сохраните исходное значение текущей работы в другом месте, затем добавьте сумму, которую вы только что рассчитали, в # 2.
  • Завершите как старое значение, так и новое значение текущей суммы целых чисел (не изменяйте существующие значения, не округлите их до отдельных переменных) и не используйте разницу.
  • Число, вычисленное на шаге 4, - это значение, присвоенное текущему основанию.
  • Повторите шаги № 2-5 для каждого базиса.

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

Основной пример:

Input basis: [0.2, 0.3, 0.3, 0.2]
Total prorate: 47
----
R used to indicate running total here:
R = 0
First basis:
 oldR = R [0]
 R += (0.2 / 1.0 * 47) [= 9.4]
 results[0] = int(R) - int(oldR) [= 9]
Second basis:
 oldR = R [9.4]
 R += (0.3 / 1.0 * 47) [+ 14.1, = 23.5 total]
 results[1] = int(R) - int(oldR) [23-9, = 14]
Third basis:
 oldR = R [23.5]
 R += (0.3 / 1.0 * 47) [+ 14.1, = 37.6 total]
 results[1] = int(R) - int(oldR) [38-23, = 15]
Fourth basis:
 oldR = R [37.6]
 R += (0.2 / 1.0 * 47) [+ 9.4, = 47 total]
 results[1] = int(R) - int(oldR) [47-38, = 9]
9+14+15+9 = 47


TL; DR с лучшей (+ 20%) возможной точностью, на 70% медленнее.

Проявленные алгоритмы, представленные в принятом ответе здесь, а также ответ на вопрос python аналогичного характера.

  • Распространение 1 - на основе Янтарный алгоритм
  • Распространение 2 - на основе алгоритма Джона Мачина
  • Распространение 3 - см. ниже
  • Распределить 4 - оптимизированную версию Распространять 3 (например, удалить LINQ, используемые массивы)

Результаты тестирования (10000 итераций)

Algorithm | Avg Abs Diff (x lowest) | Time (x lowest) 
------------------------------------------------------------------
Distribute 1 | 0.5282 (1.1992) | 00:00:00.0906921 (1.0000)
Distribute 2 | 0.4526 (1.0275) | 00:00:00.0963136 (1.0620)
Distribute 3 | 0.4405 (1.0000) | 00:00:01.1689239 (12.8889)
Distribute 4 | 0.4405 (1.0000) | 00:00:00.1548484 (1.7074)

Способ 3 имеет точность на 19,9%, что на 70,7% меньше, чем ожидалось.

Распределить 3

Делает все возможное, чтобы максимально быть максимально точным при распределении суммы.

  • Распределите веса как обычно
  • Приращение веса с максимальной ошибкой до фактической распределенной суммы равно ожидаемой сумме.

Достигает скорости для точности, делая более одного прохода через петлю.

public static IEnumerable<int> Distribute3(IEnumerable<******> weights, int amount)
{
 var totalWeight = weights.Sum();
 var query = from w in weights
 let fraction = amount * (w / totalWeight)
 let integral = (int)Math.Floor(fraction)
 select Tuple.Create(integral, fraction);
 var result = query.ToList();
 var added = result.Sum(x => x.Item1);
 while (added < amount)
 {
 var maxError = result.Max(x => x.Item2 - x.Item1);
 var index = result.FindIndex(x => (x.Item2 - x.Item1) == maxError);
 result[index] = Tuple.Create(result[index].Item1 + 1, result[index].Item2);
 added += 1;
 }
 return result.Select(x => x.Item1);
}
</******></int>

Распределить 4

public static IEnumerable<int> Distribute4(IEnumerable<******> weights, int amount)
{
 var totalWeight = weights.Sum();
 var length = weights.Count();
 var actual = new ******[length];
 var error = new ******[length];
 var rounded = new int[length];
 var added = 0;
 var i = 0;
 foreach (var w in weights)
 {
 actual[i] = amount * (w / totalWeight);
 rounded[i] = (int)Math.Floor(actual[i]);
 error[i] = actual[i] - rounded[i];
 added += rounded[i];
 i += 1;
 }
 while (added < amount)
 {
 var maxError = 0.0;
 var maxErrorIndex = -1;
 for(var e = 0; e < length; ++e)
 {
 if (error[e] > maxError)
 {
 maxError = error[e];
 maxErrorIndex = e;
 }
 }
 rounded[maxErrorIndex] += 1;
 error[maxErrorIndex] -= 1;
 added += 1;
 }
 return rounded;
}
</******></int>

Жгут проводов

static void Main(string[] args)
{
 Random r = new Random();
 Stopwatch[] time = new[] { new Stopwatch(), new Stopwatch(), new Stopwatch(), new Stopwatch() };
 ******[][] results = new[] { new ******[Iterations], new ******[Iterations], new ******[Iterations], new ******[Iterations] };
 for (var i = 0; i < Iterations; ++i)
 {
 ******[] weights = new ******[r.Next(MinimumWeights, MaximumWeights)];
 for (var w = 0; w < weights.Length; ++w)
 {
 weights[w] = (r.**********() * (MaximumWeight - MinimumWeight)) + MinimumWeight;
 }
 var amount = r.Next(MinimumAmount, MaximumAmount);
 var totalWeight = weights.Sum();
 var expected = weights.Select(w => (w / totalWeight) * amount).ToArray();
 Action<int, distributedelgate=""> runTest = (resultIndex, func) =>
 {
 time[resultIndex].Start();
 var result = func(weights, amount).ToArray();
 time[resultIndex].Stop();
 var total = result.Sum();
 if (total != amount)
 throw new Exception("Invalid total");
 var diff = expected.Zip(result, (e, a) => Math.Abs(e - a)).Sum() / amount;
 results[resultIndex][i] = diff;
 };
 runTest(0, Distribute1);
 runTest(1, Distribute2);
 runTest(2, Distribute3);
 runTest(3, Distribute4);
 }
}
</int,>


Ok. Я вполне уверен, что исходный алгоритм (как написано) и отправленный код (как написано) не совсем отвечают на почту для тестового примера, описанного @Mathias.

Мое намеренное использование этого алгоритма - несколько более конкретное приложение. Вместо вычисления% используя (@amt / @SumAmt), как показано в исходном вопросе. У меня есть фиксированная сумма, которая должна быть разделена или распределена по нескольким элементам на основе% split, определенного для каждого из этих элементов. Разделение% сумм до 100%, однако, прямое умножение часто приводит к десятичным знакам, которые (когда они вынуждены округлять до целого $) не суммируются с общей суммой, которую я разделяю. Это ядро ​​проблемы.

Я уверен, что исходный ответ от @Dav не работает в тех случаях, когда (как описано в @Mathias) округленные значения равны между несколькими срезами. Эта проблема с исходным алгоритмом и кодом может быть суммирована с одним тестовым примером:

Возьмите $100 и разделите его на 3 пути, используя 33.333333% в качестве вашего процента.

Используя код, отправленный @jtw (при условии, что это точная реализация исходного алгоритма), вы получите неверный ответ на выделение $33 на каждый элемент (в результате общая сумма составляет $99), поэтому он не прошел тест.

Я думаю, что более точный алгоритм может быть:

  • Иметь общее число, начинающееся с 0
  • Для каждого элемента в группе:
  • Рассчитайте не округленное количество выделения как ( [Amount to be Split] * [% to Split] )
  • Рассчитайте кумулятивный остаток как [Remainder] + ( [UnRounded Amount] - [Rounded Amount] )
  • Если Round( [Remainder], 0 ) > 1 ИЛИ текущий элемент - это последний элемент в списке, затем установите выделение элемента = [Rounded Amount] + Round( [Remainder], 0 )
  • else set item allocation = [Rounded Amount]
  • Повторить для следующего элемента

Реализовано в T-SQL, оно выглядит так:

-- Start of Code --
Drop Table #SplitList
Create Table #SplitList ( idno int , pctsplit decimal(5, 4), amt int , roundedAmt int )
-- Test Case #1
--Insert Into #SplitList Values (1, 0.3333, 100, 0)
--Insert Into #SplitList Values (2, 0.3333, 100, 0)
--Insert Into #SplitList Values (3, 0.3333, 100, 0)
-- Test Case #2
--Insert Into #SplitList Values (1, 0.20, 57, 0)
--Insert Into #SplitList Values (2, 0.20, 57, 0)
--Insert Into #SplitList Values (3, 0.20, 57, 0)
--Insert Into #SplitList Values (4, 0.20, 57, 0)
--Insert Into #SplitList Values (5, 0.20, 57, 0)
-- Test Case #3
--Insert Into #SplitList Values (1, 0.43, 10, 0)
--Insert Into #SplitList Values (2, 0.22, 10, 0)
--Insert Into #SplitList Values (3, 0.11, 10, 0)
--Insert Into #SplitList Values (4, 0.24, 10, 0)
-- Test Case #4
Insert Into #SplitList Values (1, 0.50, 75, 0)
Insert Into #SplitList Values (2, 0.50, 75, 0)
Declare @R Float
Declare @Results Float
Declare @unroundedAmt Float
Declare @idno Int
Declare @roundedAmt Int
Declare @amt Float
Declare @pctsplit Float
declare @rowCnt int
Select @R = 0
select @rowCnt = 0
-- Define the cursor 
Declare SplitList Cursor For 
Select idno, pctsplit, amt, roundedAmt From #SplitList Order By amt Desc
-- Open the cursor
Open SplitList
-- Assign the values of the first record
Fetch Next From SplitList Into @idno, @pctsplit, @amt, @roundedAmt
-- Loop through the records
While @@FETCH_STATUS = 0
Begin
 -- Get derived Amounts from cursor
 select @unroundedAmt = ( @amt * @pctsplit )
 select @roundedAmt = Round( @unroundedAmt, 0 )
 -- Remainder
 Select @R = @R + @unroundedAmt - @roundedAmt
 select @rowCnt = @rowCnt + 1
 -- Magic Happens! (aka Secret Sauce)
 if ( round(@R, 0 ) >= 1 ) or ( @@CURSOR_ROWS = @rowCnt ) Begin
 select @Results = @roundedAmt + round( @R, 0 )
 select @R = @R - round( @R, 0 )
 End
 else Begin
 Select @Results = @roundedAmt
 End
 If Round(@Results, 0) <> 0
 Begin
 Update #SplitList Set roundedAmt = @Results Where idno = @idno
 End
 -- Assign the values of the next record
 Fetch Next From SplitList Into @idno, @pctsplit, @amt, @roundedAmt
End
-- Close the cursor
Close SplitList
Deallocate SplitList
-- Now do the check
Select * From #SplitList
Select Sum(roundedAmt), max( amt ), 
case when max(amt) <> sum(roundedamt) then 'ERROR' else 'OK' end as Test 
From #SplitList
-- End of Code --

Что дает окончательный результат для тестового примера:

idno pctsplit amt roundedAmt
1 0.3333 100 33
2 0.3333 100 34
3 0.3333 100 33

Насколько я могу судить (и у меня есть несколько тестовых примеров в коде), это довольно эффективно обрабатывает все эти ситуации.


Проблема заключается в том, чтобы определить, что такое "приемлемая" политика округления, или, другими словами, то, что вы пытаетесь свести к минимуму. Рассмотрим сначала эту ситуацию: у вас есть только 2 одинаковых элемента в вашем списке и пытаются выделить 3 единицы. В идеале вы хотели бы выделить одну и ту же сумму для каждого элемента (1.5), но это явно не произойдет. "Лучшее", что вы могли бы сделать, скорее всего, выделит 1 и 2, или 2 и 1. Итак,

  • может быть несколько решений для каждого размещения
  • идентичные элементы могут не получать одинаковое распределение

Затем я выбрал 1 и 2 над 0 и 3, потому что я предполагаю, что вы хотите минимизировать разницу между идеальным распределением и целым распределением. Возможно, это не то, что вы считаете "хорошим распределением", и это вопрос, о котором вам нужно подумать: что бы сделать распределение лучше, чем другое? Одной возможной функцией значения может быть минимизация "общей ошибки", т.е. Сумма абсолютных значений различий между вашим распределением и "идеальным", неограниченным распределением. Мне кажется, что что-то, вдохновленное Branch and Bound, может работать, но это нетривиально. Предполагая, что решение Dav всегда создает распределение, которое удовлетворяет ограничению (что, я надеюсь, это так), я полагаю, что не гарантировано дать вам "лучшее" решение, "лучшее", определяемое любым показателем расстояния/соответствия, в конечном итоге принятие. Моя причина в том, что это жадный алгоритм, который в задачах целочисленного программирования может привести вас к решениям, которые действительно не подходят для оптимального решения. Но если вы можете жить с "несколько правильным" распределением, то я говорю, иди за ней! Выполнение этого "оптимально" не кажется тривиальным. Удачи!


Это проблема apportionment, для которой существует много известных методов. У всех есть определенные патологии: парадокс Алабамы, парадокс населения или отказ от правила квоты. (Балински и Янг доказали, что ни один метод не может избежать всех трех.) Вероятно, вы захотите, чтобы он следовал правилу цитаты и избегал парадокса Алабамы; парадокс населения не так сильно беспокоит, так как нет большого различия в количестве дней в месяц между разными годами.


Я думаю, что пропорциональные распределения - это ответ: http://www.sangakoo.com/en/unit/proportional-distributions-direct-and-inverse

licensed under cc by-sa 3.0 with attribution.