和・比較・ID・分散・百分率で float が漏れる場所を塞ぐ
한국어 원문으로 표시합니다.
목표
0.1 의 실제 값을 보고, 같은 수열의 합이 더하는 순서에 따라 달라지는 것을 재고, == 대신 무엇으로 비교할지 정합니다. 64비트 ID 가 자바스크립트의 double 에서 충돌하는 쌍을 세어 문자열로 보내는 함수를 만들고, 반올림 정책을 Decimal 로 못박고, 큰 오프셋 위의 분산을 Welford 로 구하고, 합이 100 인 백분율을 만든 뒤 전부를 대시보드 응답 하나로 모읍니다.
왜 중요한가
float 는 53비트로 가깝게 적는 약속이고, 서비스의 규칙은 대개 '정확히 같다' 와 '합이 맞다' 를 요구합니다. 그 둘이 부딪치는 자리는 예외를 내지 않아서, 재실행마다 몇 원씩 다른 합계나 브라우저에서만 틀리는 ID, 음수 분산처럼 늦게 발견됩니다. 무엇이 표현의 한계이고 무엇이 계약(반올림 위치·비교 허용 오차·전송 형식)인지 가르면 고칠 곳이 보입니다. 그래서 채점기는 여러분이 적은 숫자만 보지 않고, 여러분의 함수를 재료가 아닌 입력에 다시 돌려 기준 구현과 대조합니다.
재료
/opt/fixtures/svccs/float/ 아래에 있습니다. 읽기만 하세요. 한 줄에 값 하나인 .txt 는 float(줄) 또는 int(줄) 로 읽습니다.
series.txt 금액 흐름 3,010줄(float). 상쇄되는 큰 이체가 끼어 있다
pairs.csv a,b — 계산한 값과 기대한 값의 쌍(float 표기)
ids.txt 64비트 주문 ID(정수)
lines.csv line_id,amount — 소수 셋째 자리까지 있는 청구 금액(문자열 그대로 쓸 것)
samples.txt 에포크 밀리초로 찍힌 응답 시각(float)
shares.csv category,count — 결제 수단별 건수
records.csv id,amount,latency_ms,category — 대시보드 원본
params.json exact_values — 1단계에서 볼 소수 표기 목록
단계
/root/svccs/float/exact.json에values(params.json 의exact_values순서대로{"text": 표기, "exact": str(Decimal(float(표기))), "hex": float(표기).hex(), "is_exact": Decimal(float(표기)) == Decimal(표기)}의 목록)·sum_0_1_0_2(0.1 + 0.2의 float 값)·equals_0_3(0.1 + 0.2 == 0.3의 결과)을 적습니다./root/svccs/float/floatkit.py에sums(xs)를 만듭니다 —{"forward": 앞에서부터, "reverse": 뒤에서부터, "ascending": 값이 작은 것부터(sorted), "fsum": math.fsum}이고 앞의 셋은for루프의+=로 더합니다(내장 sum() 이 아님).series.txt로/root/svccs/float/sums.json에 그 네 값과n(줄 수)·distinct(네 값 가운데 서로 다른 개수)·builtin_sum(내장sum(xs))을 적습니다.- 같은 파일에
close(a, b)=math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-9)를 만듭니다.pairs.csv로/root/svccs/float/close.json에pairs·equal_exact(a == b인 쌍 수)·equal_close(close가 참인 쌍 수)·equal_rel_only(math.isclose(a, b, rel_tol=1e-9), abs_tol 없이 참인 쌍 수)를 적습니다. ids.txt로/root/svccs/float/ids.json에ids(개수)·unsafe_ids(절댓값이 2^53 − 1 보다 큰 수)·float_collision_pairs(float(id)가 같아지는 쌍의 수 — 같은 값 n개마다 n·(n−1)/2)·ids_in_collisions(그런 묶음에 든 ID 수)·largest_group(가장 큰 묶음의 크기)을 적습니다. 같은 파일에to_wire(ids)를 만들어 ID 를 모두 10진 문자열로 담은 JSON 배열 텍스트를 돌려주게 하고, 그 결과를/root/svccs/float/ids_wire.json에 씁니다.- 같은 파일에
half_up(text, places)를 만듭니다 — 10진 문자열 text 를 소수 places 자리로ROUND_HALF_UP(동점은 0 에서 먼 쪽) 반올림한 문자열입니다(Decimal(text).quantize(...), float 를 거치지 않음).lines.csv로/root/svccs/float/rounding.json에lines·sum_of_rounded_lines(줄마다 half_up(…, 2) 한 값의 합)·rounded_total(amount 를 Decimal 로 모두 더한 뒤 half_up(…, 2))·difference(앞의 것 − 뒤의 것)를 문자열로,lines_builtin_round_differs(round(float(amount), 2)와float(half_up(amount, 2))가 다른 줄 수)를 정수로 적습니다. - 같은 파일에
welford(xs)를 만듭니다 —{"n", "mean", "var"}(모분산, n 으로 나눔)이고 Welford 의 한 번 훑기 갱신으로 계산합니다.samples.txt로/root/svccs/float/variance.json에n·mean(참 평균)·var_naive(루프로 더한 Σx²/n − (Σx/n)²)·var_welford·var_exact(fractions.Fraction으로 계산한 모분산을 float 로)를 적습니다. - 같은 파일에
largest_remainder(counts, total)를 만듭니다 — 각 몫c·total/Σc의 정수 부분을 주고, 남는 몫을 소수 부분이 큰 순서(같으면 앞에 있는 항목 먼저)로 1씩 더한 정수 목록입니다(Σc 가 0 이면 모두 0).shares.csv로/root/svccs/float/percent.json에categories·naive(각각round(c·100/Σc))·naive_sum·largest_remainder(total=100)·largest_remainder_sum을 적습니다. - 같은 파일에
summarize(records)를 만들고records.csv로/root/svccs/float/dashboard.json을 씁니다. records 는 records.csv 한 줄 ={"id", "amount", "latency_ms", "category"}(값은 문자열일 수도 숫자일 수도 있음)입니다. 돌려줄 것:ids(각 id 의 10진 문자열, 입력 순서),total_amount(줄마다 half_up(amount, 2) 한 합의 문자열),latency_mean·latency_var(welford),categories(서로 다른 category 를 정렬한 목록),share_pct(categories 순서의 건수에 largest_remainder(…, 100)).
참고
- 채점기는
floatkit.py를 불러옵니다. 파일을 읽어 결과를 만드는 코드는 별도 스크립트나python3 - <<'PY'로 두세요. - JSON 은 float 를 되읽으면 같은 값이 나오는 표기(repr)로 씁니다. 채점기는 합과 쌍 수를 정확히 대조합니다.
- 자바스크립트가 어떻게 읽는지 직접 보고 싶으면
node -e 'console.log(JSON.parse("[1873000000000000001]")[0])'처럼 확인할 수 있습니다. 채점기는json.loads(text, parse_int=float)로 같은 일을 흉내 냅니다. - 흔한 실수:
==로 비교하기, 내장sum()을 '앞에서부터 더한 합' 이라 적기, ID 를 int 로 읽어 충돌 0 이라 보고하기,round()나Decimal(float(x))로 반올림 정책을 대신하기, 교과서 분산 식을 그대로 쓰기, 합이 99 인 백분율을 그대로 내보내기. - 산출물은 세션이 끝나면 사라집니다. 필요하면 따로 보관하세요.
0.1 의 실제 값을 본다
params.json 의 exact_values 마다 실제 저장 값·16진 표기·정확한지 여부를 /root/svccs/float/exact.json 의 values 에 적고, sum_0_1_0_2·equals_0_3 를 함께 적는다.
Decimal(0.1) 처럼 float 를 Decimal 로 바꾸면 이진 값이 손실 없이 십진으로 옮겨집니다. 문자열로 만든 Decimal("0.1") 과 같은지 보면 그 표기가 float 로 정확한지 알 수 있습니다. 분모가 2 의 거듭제곱인 소수만 정확합니다.
더하는 순서가 합을 바꾼다
/root/svccs/float/floatkit.py 에 sums(xs) 를 만들고, series.txt 로 /root/svccs/float/sums.json 에 forward·reverse·ascending·fsum·n·distinct·builtin_sum 을 적는다. 채점기는 변형 수열로 sums 를 부른다.
앞의 세 합은 for 루프의 += 로 더합니다. 파이썬 3.12 의 내장 sum() 은 float 합에 더 정확한 알고리즘을 써서 루프와 값이 다를 수 있습니다. 큰 값 ±10^15 옆에서 작은 금액의 아랫자리가 잘리는 것이 차이의 원인입니다.
== 대신 무엇으로 비교하나
floatkit.py 에 close(a, b) 를 만들고, pairs.csv 로 /root/svccs/float/close.json 에 pairs·equal_exact·equal_close·equal_rel_only 를 적는다. 채점기는 0 근처 쌍이 섞인 변형 쌍으로 close 를 부른다.
math.isclose 의 기본 abs_tol 은 0.0 이라, 0 과 비교하면 0 이 아닌 값은 늘 거짓입니다. 잔액이 0 이어야 하는 검사라면 abs_tol 을 함께 줍니다. equal_rel_only 는 일부러 abs_tol 을 빼고 셉니다.
64비트 ID 가 브라우저에서 겹친다
ids.txt 로 /root/svccs/float/ids.json 에 ids·unsafe_ids·float_collision_pairs·ids_in_collisions·largest_group 을 적고, floatkit.py 에 to_wire(ids) 를 만들어 그 결과를 /root/svccs/float/ids_wire.json 에 쓴다. 채점기는 to_wire 결과를 자바스크립트처럼 double 로 읽어 본다.
파이썬은 정수를 int 로 읽어서 아무 문제가 없어 보입니다. 받는 쪽처럼 float(id) 로 바꿔 같은 값끼리 묶어야 충돌이 보입니다. 2^60 근처에서 이웃한 double 의 간격은 256 입니다. 전송은 JSON 숫자가 아니라 문자열로 합니다.
반올림 정책을 Decimal 로 못박는다
floatkit.py 에 half_up(text, places) 를 만들고, lines.csv 로 /root/svccs/float/rounding.json 에 lines·sum_of_rounded_lines·rounded_total·difference·lines_builtin_round_differs 를 적는다. 채점기는 변형 금액과 여러 자릿수로 half_up 을 부른다.
Decimal("2.675") 는 정확히 2.675 이지만 Decimal(2.675) 는 2.67499… 입니다. 문자열에서 바로 만들어 quantize 하세요. round() 는 동점을 짝수 쪽으로 보내고, float 로 적을 수 없는 값은 동점조차 아닐 수 있습니다. 음수의 half-up 은 0 에서 먼 쪽입니다.
큰 오프셋 위의 분산
floatkit.py 에 welford(xs) 를 만들고, samples.txt 로 /root/svccs/float/variance.json 에 n·mean·var_naive·var_welford·var_exact 를 적는다. 채점기는 다른 오프셋의 변형 표본으로 welford 를 부른다.
Σx²/n 과 (Σx/n)² 은 1.79e12 의 제곱 근처인 두 큰 수라 뺄셈에서 유효 숫자가 거의 다 사라집니다. Welford 는 평균을 조금씩 옮기며 편차만 누적하므로 이 소거를 피합니다. var_exact 는 각 float 를 Fraction 으로 바꿔 계산합니다.
합이 100 인 백분율
floatkit.py 에 largest_remainder(counts, total) 를 만들고, shares.csv 로 /root/svccs/float/percent.json 에 categories·naive·naive_sum·largest_remainder·largest_remainder_sum 을 적는다. 채점기는 동점이 섞인 변형 건수로 largest_remainder 를 부른다.
몫을 float 로 계산하면 같은 나머지가 미세하게 달라져 동점 판정이 흔들립니다. fractions.Fraction 으로 몫을 만들면 정확합니다. 동점은 앞에 있는 항목 먼저입니다.
대시보드 응답 하나로 모은다
floatkit.py 에 summarize(records) 를 만들고, records.csv 로 /root/svccs/float/dashboard.json 을 쓴다. 채점기는 변형 레코드로 summarize 를 부르고, 결과를 자바스크립트처럼 double 로 읽어 ID 가 살아남는지 본다.
앞 단계의 half_up·welford·largest_remainder 를 그대로 씁니다. ID 는 문자열, 금액 합계는 Decimal 의 문자열입니다. latency 를 교과서 식으로 구하면 음수가 나올 수 있습니다.