[algorithm] 반올림 백분율을 100 %까지 만드는 방법
float숫자로 표시된 아래의 네 가지 백분율을 고려하십시오 .
13.626332%
47.989636%
9.596008%
28.788024%
-----------
100.000000%
이 백분율을 정수로 나타내야합니다. 단순히을 사용 Math.round()하면 총 101 %로 끝납니다.
14 + 48 + 10 + 29 = 101
를 사용 parseInt()하면 총 97 %가됩니다.
13 + 47 + 9 + 28 = 97
총 100 %를 유지하면서 정수로 백분율을 나타내는 좋은 알고리즘은 무엇입니까?
편집 : 의견과 답변 중 일부를 읽은 후에는이를 해결하는 방법이 많이 있습니다.
내 생각에 숫자에 충실하기 위해 “올바른”결과는 실제 값에 비해 얼마나 많은 오차 반올림이 발생하는지에 따라 정의 된 전체 오차를 최소화하는 결과입니다.
value rounded error decision
----------------------------------------------------
13.626332 14 2.7% round up (14)
47.989636 48 0.0% round up (48)
9.596008 10 4.0% don't round up (9)
28.788024 29 2.7% round up (29)
동점 (3.33, 3.33, 3.33)의 경우 임의의 결정을 내릴 수 있습니다 (예 : 3, 4, 3).
답변
여기에 대한 답변 중 어느 것도 올바르게 해결하지 못하는 것 같으므로 underscorejs를 사용하는 반 난독 화 버전이 있습니다 .
function foo(l, target) {
var off = target - _.reduce(l, function(acc, x) { return acc + Math.round(x) }, 0);
return _.chain(l).
sortBy(function(x) { return Math.round(x) - x }).
map(function(x, i) { return Math.round(x) + (off > i) - (i >= (l.length + off)) }).
value();
}
foo([13.626332, 47.989636, 9.596008, 28.788024], 100) // => [48, 29, 14, 9]
foo([16.666, 16.666, 16.666, 16.666, 16.666, 16.666], 100) // => [17, 17, 17, 17, 16, 16]
foo([33.333, 33.333, 33.333], 100) // => [34, 33, 33]
foo([33.3, 33.3, 33.3, 0.1], 100) // => [34, 33, 33, 0]답변
원래 십진 데이터에 의존하는 것에 대해 걱정하지 않는다면이 작업을 수행하는 많은 방법이 있습니다.
가장 많이 사용되는 첫 번째 방법은 가장 큰 나머지 방법입니다.
기본적으로
- 모든 것을 반올림
- 합계와 100의 차이 얻기
- 소수 부분의 내림차순으로 항목에 1을 더하여 차이 분배
귀하의 경우 다음과 같이 진행됩니다.
13.626332%
47.989636%
9.596008%
28.788024%
정수 부분을 취하면
13
47
9
28
최대 97 개까지 추가하고 3 개를 더 추가하려고합니다. 자 이제 소수점 이하 부분을 봅니다.
.626332%
.989636%
.596008%
.788024%
그리고 합계가 100에 도달 할 때까지 가장 큰 것을 취하십시오.
14
48
9
29
또는 정수 값 대신 소수점 이하 하나를 표시하도록 선택할 수 있습니다. 따라서 숫자는 48.3과 23.9 등이 될 것입니다. 이것은 분산을 100에서 많이 떨어 뜨립니다.
답변
아마도 이것을하기위한 “최상의”방법 ( “최상의”가 주관적인 용어이기 때문에 인용 된)은 당신이있는 곳의 (통합적이지 않은) 탈리를 유지하고 그 값을 반올림 하는 것 입니다.
그런 다음 기록과 함께 사용하여 어떤 값을 사용해야하는지 알아 내십시오. 예를 들어, 제공 한 값을 사용하십시오.
Value CumulValue CumulRounded PrevBaseline Need
--------- ---------- ------------ ------------ ----
0
13.626332 13.626332 14 0 14 ( 14 - 0)
47.989636 61.615968 62 14 48 ( 62 - 14)
9.596008 71.211976 71 62 9 ( 71 - 62)
28.788024 100.000000 100 71 29 (100 - 71)
---
100
각 단계에서 숫자 자체를 반올림하지 않습니다. 대신, 당신은 라운드 축적 된 최고의 정수에서 값과 일을 그 이전의 기준에서 값이 있는지에 도달 – 그 기준이 이전 행의 누적 값 (둥근)입니다.
당신이 있기 때문에이 작동 하지 각 단계에서 정보가 손실보다는 더 지능적으로 정보를 사용하여. ‘올바른’반올림 된 값은 마지막 열에 있으며 합계가 100임을 알 수 있습니다.
위의 세 번째 값에서이 값과 각 값의 반올림 차이를 확인할 수 있습니다. 9.596008일반적으로 반올림 되지만 10누적 된 71.211976올림은 올림됩니다 . 이는 이전 기준선에 추가하기 만하면 71됨을 의미합니다 .962
이것은 또한 대략 3 개의 값 과 같이 “문제적인”순서로 작동하며 그중 하나 는 반올림해야합니다.1/3
Value CumulValue CumulRounded PrevBaseline Need
--------- ---------- ------------ ------------ ----
0
33.333333 33.333333 33 0 33 ( 33 - 0)
33.333333 66.666666 67 33 34 ( 67 - 33)
33.333333 99.999999 100 67 33 (100 - 67)
---
100
답변
반올림의 목표는 가장 적은 양의 오류를 생성하는 것입니다. 단일 값을 반올림하는 경우 해당 프로세스는 간단하고 간단하며 대부분의 사람들이 쉽게 이해할 수 있습니다. 동시에 여러 숫자를 반올림하면 프로세스가 까다로워집니다. 오류가 어떻게 결합되는지, 즉 최소화해야하는 것을 정의해야합니다.
Varun Vohra 의 잘 알려진 답변 은 절대 오류의 합계를 최소화하며 구현이 매우 간단합니다. 그러나 처리하지 않는 경우가 있습니다. 반올림의 결과는 24.25, 23.25, 27.25, 25.25무엇입니까? 그중 하나는 내림 대신 반올림해야합니다. 목록에서 첫 번째 또는 마지막 항목을 임의로 선택합니다.
아마도 절대 오류 대신 상대 오류 를 사용하는 것이 좋습니다 . 23.25를 24로 올림하면 3.2 %, 27.25를 28로 올림하면 2.8 % 만 바꿉니다. 이제 확실한 승자가 있습니다.
이것을 더 조정할 수 있습니다. 한 가지 일반적인 기술은 각 오류 를 제곱 하여 큰 오류가 작은 오류보다 불균형 적으로 더 많이 계산되도록하는 것입니다. 또한 비선형 제수를 사용하여 상대 오차를 얻으십시오 .1 %의 오차가 99 %의 오차보다 99 배 더 중요하다는 것은 옳지 않은 것 같습니다. 아래 코드에서 나는 제곱근을 사용했습니다.
완전한 알고리즘은 다음과 같습니다.
- 모두 반올림 한 후 백분율을 합산하고 100에서 뺍니다. 이는 몇 퍼센트를 반올림해야하는지 알려줍니다.
- 반올림 할 때와 반올림 할 때마다 각각의 백분율에 대해 두 개의 오류 점수를 생성합니다. 둘의 차이점을 생각해보십시오.
- 위에서 생성 된 오차 차이를 정렬하십시오.
- 반올림해야하는 백분율 수는 정렬 된 목록에서 항목을 가져오고 반올림 된 백분율을 1 씩 증가시킵니다.
예를 들어 같은 오류 합계를 가진 조합이 둘 이상있을 수 있습니다 33.3333333, 33.3333333, 33.3333333. 이것은 피할 수 없으며 결과는 완전히 임의적입니다. 아래 코드는 왼쪽의 값을 반올림하는 것을 선호합니다.
파이썬에서 모든 것을 합치는 것은 다음과 같습니다.
def error_gen(actual, rounded):
divisor = sqrt(1.0 if actual < 1.0 else actual)
return abs(rounded - actual) ** 2 / divisor
def round_to_100(percents):
if not isclose(sum(percents), 100):
raise ValueError
n = len(percents)
rounded = [int(x) for x in percents]
up_count = 100 - sum(rounded)
errors = [(error_gen(percents[i], rounded[i] + 1) - error_gen(percents[i], rounded[i]), i) for i in range(n)]
rank = sorted(errors)
for i in range(up_count):
rounded[rank[i][1]] += 1
return rounded
>>> round_to_100([13.626332, 47.989636, 9.596008, 28.788024])
[14, 48, 9, 29]
>>> round_to_100([33.3333333, 33.3333333, 33.3333333])
[34, 33, 33]
>>> round_to_100([24.25, 23.25, 27.25, 25.25])
[24, 23, 28, 25]
>>> round_to_100([1.25, 2.25, 3.25, 4.25, 89.0])
[1, 2, 3, 4, 90]마지막 예에서 볼 수 있듯이이 알고리즘은 여전히 직관적이지 않은 결과를 제공 할 수 있습니다. 89.0에서는 반올림이 필요하지 않지만 목록의 값 중 하나를 반올림해야했습니다. 가장 작은 상대 오차는 훨씬 작은 대안이 아닌 큰 값을 반올림하여 발생합니다.
이 답변은 원래 모든 가능한 반올림 / 반올림 조합을 거치는 것을 옹호했지만 의견에서 지적했듯이 간단한 방법이 더 효과적입니다. 알고리즘과 코드는 단순화를 반영합니다.
답변
반올림 숫자를 합산하지 마십시오. 부정확 한 결과가 나타납니다. 항의 수와 분수 부분의 분포에 따라 총계가 크게 떨어질 수 있습니다.
반올림 된 숫자를 표시 하지만 실제 값을 합산 하십시오. 숫자를 표현하는 방법에 따라 실제 방법은 다를 수 있습니다. 그렇게하면
14 48 10 29 __ 100
어떤 방식 으로든 불일치가 발생합니다. 하나의 값을 잘못된 방식으로 “반올림”하지 않고 100을 더하는 숫자를 표시하는 방법은 없습니다 (최소 오류는 9.596에서 9로 변경됩니다)
편집하다
다음 중 하나를 선택해야합니다.
- 품목의 정확도
- 합계의 정확도 (반올림 된 값을 합한 경우)
- 반올림 항목과 반올림 합계 간의 일관성)
백분율 # 3을 다룰 때 대부분의 경우 가장 좋은 방법은 개별 항목이 총 100 개가 아닌 경우보다 총계가 101 % 일 때 더 명확하고 개별 항목을 정확하게 유지하기 때문입니다. 내 의견으로는 “라운딩”9.596 ~ 9가 정확하지 않습니다.
이것을 설명하기 위해 때로는 개별 값이 반올림되고 총 100 %가 아닐 수 있음을 설명하는 각주를 추가합니다. 반올림을 이해하는 사람은 해당 설명을 이해할 수 있어야합니다.
답변
C # 버전 반올림 도우미를 작성했으며 알고리즘은 Varun Vohra의 답변 과 동일 합니다. 도움이되기를 바랍니다.
public static List<decimal> GetPerfectRounding(List<decimal> original,
decimal forceSum, int decimals)
{
var rounded = original.Select(x => Math.Round(x, decimals)).ToList();
Debug.Assert(Math.Round(forceSum, decimals) == forceSum);
var delta = forceSum - rounded.Sum();
if (delta == 0) return rounded;
var deltaUnit = Convert.ToDecimal(Math.Pow(0.1, decimals)) * Math.Sign(delta);
List<int> applyDeltaSequence;
if (delta < 0)
{
applyDeltaSequence = original
.Zip(Enumerable.Range(0, int.MaxValue), (x, index) => new { x, index })
.OrderBy(a => original[a.index] - rounded[a.index])
.ThenByDescending(a => a.index)
.Select(a => a.index).ToList();
}
else
{
applyDeltaSequence = original
.Zip(Enumerable.Range(0, int.MaxValue), (x, index) => new { x, index })
.OrderByDescending(a => original[a.index] - rounded[a.index])
.Select(a => a.index).ToList();
}
Enumerable.Repeat(applyDeltaSequence, int.MaxValue)
.SelectMany(x => x)
.Take(Convert.ToInt32(delta/deltaUnit))
.ForEach(index => rounded[index] += deltaUnit);
return rounded;
}다음 단위 테스트를 통과합니다.
[TestMethod]
public void TestPerfectRounding()
{
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.333m, 3.334m, 3.333m}, 10, 2),
new List<decimal> {3.33m, 3.34m, 3.33m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.33m, 3.34m, 3.33m}, 10, 1),
new List<decimal> {3.3m, 3.4m, 3.3m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.333m, 3.334m, 3.333m}, 10, 1),
new List<decimal> {3.3m, 3.4m, 3.3m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 13.626332m, 47.989636m, 9.596008m, 28.788024m }, 100, 0),
new List<decimal> {14, 48, 9, 29});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 16.666m, 16.666m, 16.666m, 16.666m, 16.666m, 16.666m }, 100, 0),
new List<decimal> { 17, 17, 17, 17, 16, 16 });
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 33.333m, 33.333m, 33.333m }, 100, 0),
new List<decimal> { 34, 33, 33 });
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 33.3m, 33.3m, 33.3m, 0.1m }, 100, 0),
new List<decimal> { 34, 33, 33, 0 });
}답변
반올림으로 인한 오류를 추적 한 다음 누적 오류가 현재 숫자의 소수보다 큰 경우 결을 반올림 할 수 있습니다.
13.62 -> 14 (+.38)
47.98 -> 48 (+.02 (+.40 total))
9.59 -> 10 (+.41 (+.81 total))
28.78 -> 28 (round down because .81 > .78)
------------
100
이것이 일반적으로 작동하는지 확실하지 않지만 순서가 바뀌면 비슷하게 작동합니다.
28.78 -> 29 (+.22)
9.59 -> 9 (-.37; rounded down because .59 > .22)
47.98 -> 48 (-.35)
13.62 -> 14 (+.03)
------------
100
나는 이것이 고장날 수있는 엣지 케이스가 있다고 확신하지만, 기본적으로 입력 데이터를 수정하기 때문에 모든 접근 방식은 다소 임의적입니다.
