{"id":489508,"date":"2026-08-03T08:05:08","date_gmt":"2026-08-03T08:05:08","guid":{"rendered":"https:\/\/savepearlharbor.com\/?p=489508"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=489508","title":{"rendered":"99-\u0439 \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044c \u0437\u0430 20 \u043c\u0441: T-Digest \u0438 \u043c\u0430\u0433\u0438\u044f \u0441\u0436\u0430\u0442\u044b\u0445 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439"},"content":{"rendered":"<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c, \u0447\u0442\u043e \u0432\u044b \u0438\u043c\u0435\u0435\u0442\u0435 \u0441\u0435\u0440\u0432\u0435\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442 100.000 RPS. \u0412\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0430 \u0434\u0430\u0448\u0431\u043e\u0440\u0434\u0435 99-\u0439 \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044c \u0437\u0430\u0434\u0435\u0440\u0436\u043a\u0438 \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0432\u044b\u0448\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0442\u043e\u043b\u044c\u043a\u043e 1% \u0441\u0430\u043c\u044b\u0445 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u0415\u0441\u043b\u0438 \u0432\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u0435 \u0432\u0441\u0435 100 000 \u0447\u0438\u0441\u0435\u043b \u0437\u0430 \u0441\u0435\u043a\u0443\u043d\u0434\u0443, \u0447\u0435\u0440\u0435\u0437 \u0447\u0430\u0441 \u044d\u0442\u043e 360 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0447\u0438\u0441\u0435\u043b. \u0427\u0435\u0440\u0435\u0437 \u0434\u0435\u043d\u044c \u2014 8.6 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u043e\u0432. \u041a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0445\u0440\u0430\u043d\u0438\u0442\u044c, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0432\u044b\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c? \u041d\u0435\u0440\u0435\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0433\u043e \u0438 \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0437\u0430\u0442\u0440\u0430\u0442\u043d\u043e.<\/p>\n<p>\u041d\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c T-Digest. \u0412\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u043e\u043d \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u0438\u0445 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u0410 \u0432\u0441\u0435 \u0434\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f (\u0442\u0430\u043c, \u0433\u0434\u0435 \u043d\u0430\u0448\u0438 \u0445\u0432\u043e\u0441\u0442\u044b) \u043e\u043d \u0434\u0435\u043b\u0430\u0435\u0442 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u043c\u0438 \u0438 \u0442\u043e\u0447\u043d\u044b\u043c\u0438, \u0430 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0438 \u00ab\u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438\u00bb. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0434\u043b\u044f 100 000 \u0442\u043e\u0447\u0435\u043a \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e ~100 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0432\u043c\u0435\u0441\u0442\u043e 100 000 \u0447\u0438\u0441\u0435\u043b. \u042d\u0442\u043e \u0432 \u0441\u043e\u0442\u043d\u0438 \u0440\u0430\u0437 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438. \u0418 \u043f\u0440\u0438\u0442\u043e\u043c \u0447\u0442\u043e \u043e\u0448\u0438\u0431\u043a\u0430 \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 95-\u0433\u043e \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u0441\u0435\u0433\u043e 0.001\u20130.06% (\u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 \u0441\u0436\u0430\u0442\u0438\u044f).<\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0440\u0430\u0437\u0431\u0435\u0440\u0443 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043f\u043e\u0447\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a\u043e\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u043c\u0430\u043b\u043e\u0437\u0430\u0442\u0440\u0430\u0442\u043d\u044b\u0439, \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0433\u0440\u0430\u0444\u0438\u043a\u0438 \u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u043a\u0430\u0436\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 C.<\/p>\n<hr\/>\n<p>\u041f\u0435\u0440\u0435\u0434 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0445\u043e\u0447\u0435\u0442\u0441\u044f \u043f\u043e\u0432\u0435\u0434\u0430\u0442\u044c, \u0447\u0442\u043e \u0437\u0430 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438, \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u0438, \u043a\u0430\u043a\u0438\u0435 \u0435\u0441\u0442\u044c \u043d\u0430\u0438\u0432\u043d\u044b\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u0430.<\/p>\n<p>q-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043d\u0438\u0436\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043b\u0435\u0436\u0438\u0442 q-\u0434\u043e\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041c\u0435\u0434\u0438\u0430\u043d\u0430 \u2014 \u044d\u0442\u043e 0.5-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. 95-\u0439 \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044c \u2014 0.95-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. 99-\u0439 \u2014 0.99-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. \u0412 \u043c\u043e\u043d\u0438\u0442\u043e\u0440\u0438\u043d\u0433\u0435 \u0432\u0430\u0436\u043d\u044b \u0438\u043c\u0435\u043d\u043d\u043e \u0445\u0432\u043e\u0441\u0442\u044b: p99 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0441 1% \u0441\u0430\u043c\u044b\u0445 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u0415\u0441\u043b\u0438 p99 \u0440\u0430\u0441\u0442\u0451\u0442 \u2014 \u0443 \u0432\u0430\u0441 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043c\u0435\u0434\u0438\u0430\u043d\u0430 \u0432 \u043d\u043e\u0440\u043c\u0435.<\/p>\n<p>\u041a\u0430\u043a \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c? \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431: \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0432\u0437\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u0434 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c q\u00d7N. \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0431\u0435\u0437 \u043f\u0440\u043e\u0431\u043b\u0435\u043c, \u043d\u043e \u043f\u0430\u043c\u044f\u0442\u044c \u0432 \u0438\u0442\u043e\u0433\u0435 O(N), \u0438 \u043f\u0440\u0438 100k RPS \u0437\u0430 \u0447\u0430\u0441 \u043d\u0430\u0431\u0435\u0433\u0430\u0435\u0442 360 \u043c\u043b\u043d \u0447\u0438\u0441\u0435\u043b. \u0410 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0446\u0435\u043b\u044b\u0445 O(N log N) \u043d\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443.<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0441\u044d\u043c\u043f\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u2014 \u0431\u0440\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u043e\u0442\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041f\u0430\u043c\u044f\u0442\u0438 \u043c\u0435\u043d\u044c\u0448\u0435, \u043d\u043e \u0432\u044b\u0431\u0440\u043e\u0441\u044b (\u0442\u0435 \u0441\u0430\u043c\u044b\u0435 \u0440\u0435\u0434\u043a\u0438\u0435 1%) \u0441 \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u0430 \u0432\u044b\u0431\u0440\u043e\u0441\u044b \u2014 \u044d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c.<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u0443\u044e \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0443: \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e\u0432\u0443\u044e \u043e\u0441\u044c \u043d\u0430 \u0440\u0430\u0432\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b, \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u044f. \u041d\u043e \u0435\u0441\u043b\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u0441\u043a\u043e\u0448\u0435\u043d\u044b (\u0430 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043d\u0438 \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0441\u043a\u043e\u0448\u0435\u043d\u044b), \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b \u0432 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 \u043b\u0438\u0431\u043e \u043f\u0443\u0441\u0442\u044b\u0435, \u043b\u0438\u0431\u043e \u043e\u0433\u0440\u043e\u043c\u043d\u044b\u0435, \u0438 \u0432 \u0438\u0442\u043e\u0433\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043f\u0430\u0434\u0430\u0435\u0442.<\/p>\n<p>\u0410 T-Digest \u0440\u0435\u0448\u0430\u0435\u0442 \u044d\u0442\u0443 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u2014 \u043e\u043d \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432\u0441\u0435 \u0434\u0430\u043d\u043d\u044b\u0435, \u043d\u0435 \u0442\u0435\u0440\u044f\u0435\u0442 \u0432\u044b\u0431\u0440\u043e\u0441\u044b \u0438 \u0434\u0430\u0451\u0442 \u0432\u044b\u0441\u043e\u043a\u0443\u044e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0432 \u0445\u0432\u043e\u0441\u0442\u0430\u0445.<\/p>\n<h3>\u276f \u0421\u0443\u0442\u044c T-Digest<\/h3>\n<p>T-Digest \u0431\u044b\u043b \u0441\u043e\u0437\u0434\u0430\u043d \u0422\u0435\u0434\u043e\u043c \u0414\u0430\u043d\u0442\u0438\u043d\u0433\u043e\u043c \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 2010-\u0445 \u0433\u043e\u0434\u043e\u0432, \u0430 \u0432 2019 \u0433\u043e\u0434\u0443 \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e \u0441 \u041e\u0442\u043c\u0430\u0440\u043e\u043c \u042d\u0440\u0442\u043b\u043e\u043c \u0432\u044b\u0448\u043b\u0430 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u043e \u043d\u0438\u0445 \u0431\u044b\u043b\u0438 Q-Digest, GK01, \u043d\u043e \u043e\u043d\u0438 \u0434\u0430\u0432\u0430\u043b\u0438 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u0443\u044e \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0443\u044e \u043e\u0448\u0438\u0431\u043a\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439. \u0414\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043e\u0448\u0438\u0431\u043a\u0430 \u00ab\u0432\u0441\u0435\u0433\u043e\u00bb 1% \u2014 \u0434\u043b\u044f \u043c\u0435\u0434\u0438\u0430\u043d\u044b \u044d\u0442\u043e \u00b11%, \u0438 \u0434\u043b\u044f 99-\u0433\u043e \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044f \u0442\u043e\u0436\u0435 \u00b11%. \u041d\u043e \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043d\u0430\u043c \u0432\u0430\u0436\u043d\u0435\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445, \u0433\u0434\u0435 1% \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043a\u0440\u0438\u0442\u0438\u0447\u043d\u044b\u043c.<\/p>\n<p>\u0414\u0430\u043d\u0442\u0438\u043d\u0433 \u0438 \u042d\u0440\u0442\u043b \u043f\u043e\u0448\u043b\u0438 \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b. \u041e\u043d\u0438 \u0440\u0435\u0448\u0438\u043b\u0438, \u0447\u0442\u043e \u043e\u0448\u0438\u0431\u043a\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438: \u0447\u0435\u043c \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u0440\u0430\u044f\u043c, \u0442\u0435\u043c \u0442\u043e\u0447\u043d\u0435\u0435. \u041c\u0435\u0434\u0438\u0430\u043d\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441 \u043e\u0448\u0438\u0431\u043a\u043e\u0439 5%, \u0430 p99 \u2014 \u0441 \u043e\u0448\u0438\u0431\u043a\u043e\u0439 0.1%.<\/p>\n<p>\u0421\u0430\u043c \u043a\u043e\u043d\u0446\u0435\u043f\u0442 \u043d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0443\u0436 \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u0439: \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u041a\u0430\u0436\u0434\u044b\u0439 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0445\u0440\u0430\u043d\u0438\u0442 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 (mean) \u0438 \u0432\u0435\u0441 (weight) \u2014 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0447\u0438\u0441\u0435\u043b \u0432 \u043d\u0435\u0433\u043e \u043f\u043e\u043f\u0430\u043b\u043e.<\/p>\n<p>\u041d\u043e \u043a\u0430\u043a \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c? \u0415\u0441\u043b\u0438 \u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u0435 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043f\u043e \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 \u043e\u0441\u0438 \u2014 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0443.<\/p>\n<p>\u0412 \u0438\u0442\u043e\u0433\u0435 T-Digest \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u043d\u0435 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e, \u0430 \u043f\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u0418 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0442\u043e\u0433\u043e, \u0433\u0434\u0435 \u043e\u043d \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f: \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435, \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u0435. \u041a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0436\u0430\u0434\u043d\u044b\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u043e\u043c \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0435\u043d \u043b\u0438\u043c\u0438\u0442 \u0432\u0435\u0441\u0430. \u0414\u043b\u044f \u043a\u0440\u0430\u0451\u0432 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0442\u0430\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u0447\u043d\u044b\u043c\u0438. \u0414\u043b\u044f \u0446\u0435\u043d\u0442\u0440\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0431\u043e\u043b\u044c\u0448\u043e\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0442\u0430\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u0436\u0438\u0440\u043d\u044b\u0435 \u0438 \u043d\u0435\u0442\u043e\u0447\u043d\u044b\u0435.<\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c, \u0432\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, T-Digest \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u0438\u0445 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u042d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u043e\u043b\u0435\u0439: \u0441\u0440\u0435\u0434\u043d\u0435\u0435 (mean) \u043a\u0430\u043a \u0446\u0435\u043d\u0442\u0440 \u043c\u0430\u0441\u0441 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u0438 \u0432\u0435\u0441 (weight) \u2014 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u044d\u0442\u043e\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0435.<\/p>\n<p>p99 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0443 \u043d\u0430 \u043a\u0440\u0430\u044e, p50 \u2014 \u043f\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0443 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/p>\n<blockquote>\n<p>\u041a\u0441\u0442\u0430\u0442\u0438, \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c T-Digest \u043d\u0435 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d: \u043f\u0440\u0438 \u0440\u0430\u0437\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043f\u043e\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f. \u041c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c, \u043d\u043e \u044d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0443\u0431\u0438\u0442\u044c \u0430\u0434\u0430\u043f\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c \u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c.<\/p>\n<\/blockquote>\n<p>\u0414\u0430\u043b\u044c\u0448\u0435 \u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443: \u043a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 scale function \u0438 \u043a\u0430\u043a \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0434\u0435\u043b\u044c\u0442\u0430 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<h2>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 T-Digest: scale function, size bound \u0438 \u0441\u043b\u0438\u044f\u043d\u0438\u0435<\/h2>\n<p>\u041a\u043e\u0433\u0434\u0430 \u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0430\u043b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u0441 T-Digest, \u043c\u0435\u043d\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u043b\u043e \u0442\u043e, \u043a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0448\u0430\u0435\u0442, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0445\u043d\u0443\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434, \u043a\u0430\u043a \u0432\u044b\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b \u0434\u043b\u044f \u0445\u0432\u043e\u0441\u0442\u043e\u0432 \u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0434\u043b\u044f \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b.<\/p>\n<p>\u0412\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0434\u0435\u043b\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e\u0432\u0443\u044e \u043e\u0441\u044c \u043d\u0430 \u0440\u0430\u0432\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b, T-Digest \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 <strong>scale function<\/strong> \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c $ q $ \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 $ k $. \u0421\u0430\u043c\u0430\u044f \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0438\u0437 \u0441\u0442\u0430\u0442\u044c\u0438:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"k_0(q) = \\frac{\\delta}{2} \\cdot q\" alt=\"k_0(q) = \\frac{\\delta}{2} \\cdot q\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/cf\/cf4\/cf4ee4d2a1a62e0a4145fff05a43b845.svg\" width=\"102\" height=\"38\" data-width=\"12.786\" data-height=\"4.704\" data-vertical-align=\"-1.786\" style=\"width: 12.786ex; height: 4.704ex; vertical-align: -1.786ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/cf\/cf4\/cf4ee4d2a1a62e0a4145fff05a43b845.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/cf\/cf4\/cf4ee4d2a1a62e0a4145fff05a43b845.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u042d\u0442\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0448\u043a\u0430\u043b\u0430. \u041e\u043d\u0430 \u0434\u0430\u0451\u0442 \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u0435 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u0430\u044f \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0430. \u0418\u043d\u0442\u0435\u0440\u0435\u0441 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"k_1(q) = \\frac{\\delta}{2\\pi} \\cdot \\arcsin(2q - 1)\" alt=\"k_1(q) = \\frac{\\delta}{2\\pi} \\cdot \\arcsin(2q - 1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/36\/363\/363d7118a63fc6148c0f0773c08de9e9.svg\" width=\"213\" height=\"38\" data-width=\"26.665\" data-height=\"4.729\" data-vertical-align=\"-1.799\" style=\"width: 26.665ex; height: 4.729ex; vertical-align: -1.799ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/36\/363\/363d7118a63fc6148c0f0773c08de9e9.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/36\/363\/363d7118a63fc6148c0f0773c08de9e9.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u041f\u0440\u0438 $ q = 0.5 $ (\u043c\u0435\u0434\u0438\u0430\u043d\u0430) \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441 \u043e\u0442 \u043d\u0443\u043b\u044f \u0434\u0430\u0451\u0442 \u043d\u043e\u043b\u044c. \u041f\u0440\u0438 $ q = 0 $ \u2014 <img decoding=\"async\" class=\"formula inline\" source=\"-\\delta\/4\" alt=\"-\\delta\/4\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/386\/386f07f7d5ad95046cb767e729a15c14.svg\" width=\"40\" height=\"18\" data-width=\"5.027\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 5.027ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/386\/386f07f7d5ad95046cb767e729a15c14.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/386\/386f07f7d5ad95046cb767e729a15c14.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u041f\u0440\u0438 $ q = 1 $ \u2014 <img decoding=\"async\" class=\"formula inline\" source=\"\\delta\/4\" alt=\"\\delta\/4\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a9\/a95\/a95202bfca6f459c31f13ba0acac9d64.svg\" width=\"26\" height=\"18\" data-width=\"3.267\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 3.267ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a9\/a95\/a95202bfca6f459c31f13ba0acac9d64.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a9\/a95\/a95202bfca6f459c31f13ba0acac9d64.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u0413\u0440\u0430\u0444\u0438\u043a \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u043f\u043e\u0447\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442: \u0435\u0441\u043b\u0438 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043b\u0438\u043d\u0438\u0438 \u043d\u0430 \u0440\u0430\u0432\u043d\u043e\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e \u043e\u0441\u0438 $ k $, \u0442\u043e \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 (\u0433\u0434\u0435 $ q $ \u0431\u043b\u0438\u0437\u043a\u043e \u043a 0 \u0438\u043b\u0438 1) \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0435\u043a\u0446\u0438\u0438 \u043d\u0430 \u043e\u0441\u044c $ q $ \u0431\u0443\u0434\u0443\u0442 \u0433\u0443\u0449\u0435. \u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u2014 \u0433\u043b\u0430\u0432\u043d\u043e\u0435. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0435\u0433\u043e <strong>\u043b\u0435\u0432\u044b\u0439<\/strong> \u0438 <strong>\u043f\u0440\u0430\u0432\u044b\u0439<\/strong> \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u043d\u0433\u0438. \u041f\u0443\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0441 \u0432\u0435\u0441\u043e\u043c <img decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/f1\/f12\/f1290186a5d0b1ceab27f4e77c0c5d68.svg\" width=\"13\" height=\"12\" data-width=\"1.62\" data-height=\"1.027\" data-vertical-align=\"-0.025\" style=\"width: 1.62ex; height: 1.027ex; vertical-align: -0.025ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/f1\/f12\/f1290186a5d0b1ceab27f4e77c0c5d68.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/f1\/f12\/f1290186a5d0b1ceab27f4e77c0c5d68.svg 781w\" loading=\"lazy\" decode=\"async\"\/>, \u0430 \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u044b\u0439 \u0432\u0435\u0441 \u0432\u0441\u0435\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u043d\u0435\u0433\u043e \u0440\u0430\u0432\u043d\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"W_{\\text{left}}\" alt=\"W_{\\text{left}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2b\/2bd\/2bdb6f531fb0fdf331f754a32a6a2f60.svg\" width=\"37\" height=\"18\" data-width=\"4.59\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 4.59ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2b\/2bd\/2bdb6f531fb0fdf331f754a32a6a2f60.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2b\/2bd\/2bdb6f531fb0fdf331f754a32a6a2f60.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u2014 <img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7b\/7b8\/7b8b965ad4bca0e41ab51de7b31363a1.svg\" width=\"12\" height=\"12\" data-width=\"1.357\" data-height=\"1.025\" data-vertical-align=\"-0.025\" style=\"width: 1.357ex; height: 1.025ex; vertical-align: -0.025ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7b\/7b8\/7b8b965ad4bca0e41ab51de7b31363a1.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7b\/7b8\/7b8b965ad4bca0e41ab51de7b31363a1.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u0422\u043e\u0433\u0434\u0430:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"q_{\\text{left}} = \\frac{W_{\\text{left}}}{n}\" alt=\"q_{\\text{left}} = \\frac{W_{\\text{left}}}{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/84\/849\/84931cc778338a087e74a3a2501805d1.svg\" width=\"97\" height=\"37\" data-width=\"12.067\" data-height=\"4.652\" data-vertical-align=\"-1.76\" style=\"width: 12.067ex; height: 4.652ex; vertical-align: -1.76ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/84\/849\/84931cc778338a087e74a3a2501805d1.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/84\/849\/84931cc778338a087e74a3a2501805d1.svg 781w\" loading=\"lazy\" decode=\"async\"\/><img decoding=\"async\" class=\"formula\" source=\"q_{\\text{right}} = \\frac{W_{\\text{left}} + w}{n}\" alt=\"q_{\\text{right}} = \\frac{W_{\\text{left}} + w}{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/38a\/38ad1e1cbd98590c0e8fd8f754c6ec62.svg\" width=\"141\" height=\"37\" data-width=\"17.569\" data-height=\"4.652\" data-vertical-align=\"-1.76\" style=\"width: 17.569ex; height: 4.652ex; vertical-align: -1.76ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/38a\/38ad1e1cbd98590c0e8fd8f754c6ec62.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/38\/38a\/38ad1e1cbd98590c0e8fd8f754c6ec62.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0410 \u0446\u0435\u043d\u0442\u0440 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 (\u0435\u0433\u043e \u043c\u0435\u0434\u0438\u0430\u043d\u0430) \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0442\u043e\u0447\u043a\u0435:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"q_{\\text{center}} = \\frac{W_{\\text{left}} + w\/2}{n}\" alt=\"q_{\\text{center}} = \\frac{W_{\\text{left}} + w\/2}{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/81\/812\/81296b18b7893f91c0ec6a1f6707fa22.svg\" width=\"166\" height=\"39\" data-width=\"20.718\" data-height=\"4.88\" data-vertical-align=\"-1.874\" style=\"width: 20.718ex; height: 4.88ex; vertical-align: -1.874ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/81\/812\/81296b18b7893f91c0ec6a1f6707fa22.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/81\/812\/81296b18b7893f91c0ec6a1f6707fa22.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 scale function:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"k_1(q_{\\text{right}}) - k_1(q_{\\text{left}}) \\leq 1\" alt=\"k_1(q_{\\text{right}}) - k_1(q_{\\text{left}}) \\leq 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a3\/a32\/a323d42542e092720f8cfd8b7e74809f.svg\" width=\"182\" height=\"19\" data-width=\"22.811\" data-height=\"2.366\" data-vertical-align=\"-0.617\" style=\"width: 22.811ex; height: 2.366ex; vertical-align: -0.617ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a3\/a32\/a323d42542e092720f8cfd8b7e74809f.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a3\/a32\/a323d42542e092720f8cfd8b7e74809f.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u00ab\u0440\u0430\u0437\u043c\u0435\u0440\u00bb \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0432 \u0448\u043a\u0430\u043b\u0435 $ k $ \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0442\u044c 1. \u0414\u043b\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0448\u043a\u0430\u043b\u044b $ k_0 $ \u044d\u0442\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\text{weight} \\leq \\frac{4\\delta}{q(1-q)}\" alt=\"\\text{weight} \\leq \\frac{4\\delta}{q(1-q)}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/75\/758\/75863b7042b9959887a772bea976b071.svg\" width=\"146\" height=\"43\" data-width=\"18.287\" data-height=\"5.324\" data-vertical-align=\"-2.096\" style=\"width: 18.287ex; height: 5.324ex; vertical-align: -2.096ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/75\/758\/75863b7042b9959887a772bea976b071.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/75\/758\/75863b7042b9959887a772bea976b071.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0414\u043b\u044f \u0448\u043a\u0430\u043b\u044b \u0441 \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441\u043e\u043c $ k_1 $ \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u0440\u0443\u0433\u043e\u0435, \u043d\u043e \u0438\u0434\u0435\u044f \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0442\u043e\u0439 \u0436\u0435: \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.<\/p>\n<p>\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c: <img decoding=\"async\" class=\"formula inline\" source=\"q(1-q)\" alt=\"q(1-q)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5f\/5ff\/5ff03088fedb417b85bf545c7306c228.svg\" width=\"62\" height=\"18\" data-width=\"7.739\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 7.739ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5f\/5ff\/5ff03088fedb417b85bf545c7306c228.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5f\/5ff\/5ff03088fedb417b85bf545c7306c228.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u041d\u0430 \u043a\u0440\u0430\u044f\u0445, \u0433\u0434\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"q = 0.01\" alt=\"q = 0.01\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/fc\/fc5\/fc53581eefb990aa24f90d03e1661094.svg\" width=\"65\" height=\"16\" data-width=\"8.08\" data-height=\"1.946\" data-vertical-align=\"-0.439\" style=\"width: 8.08ex; height: 1.946ex; vertical-align: -0.439ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/fc\/fc5\/fc53581eefb990aa24f90d03e1661094.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/fc\/fc5\/fc53581eefb990aa24f90d03e1661094.svg 781w\" loading=\"lazy\" decode=\"async\"\/>, \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u0440\u0430\u0432\u0435\u043d <img decoding=\"async\" class=\"formula inline\" source=\"0.0099\" alt=\"0.0099\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/e3\/e38\/e384f849702180fea3eedf19099d18ba.svg\" width=\"50\" height=\"12\" data-width=\"6.285\" data-height=\"1.557\" data-vertical-align=\"-0.05\" style=\"width: 6.285ex; height: 1.557ex; vertical-align: -0.05ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/e3\/e38\/e384f849702180fea3eedf19099d18ba.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/e3\/e38\/e384f849702180fea3eedf19099d18ba.svg 781w\" loading=\"lazy\" decode=\"async\"\/>, \u0438 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u043c \u2014 \u043e\u043a\u043e\u043b\u043e <img decoding=\"async\" class=\"formula inline\" source=\"400\\delta\" alt=\"400\\delta\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a2\/a29\/a29e483a3c43935f6c108b6ab615f88c.svg\" width=\"35\" height=\"18\" data-width=\"4.398\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 4.398ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a2\/a29\/a29e483a3c43935f6c108b6ab615f88c.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a2\/a29\/a29e483a3c43935f6c108b6ab615f88c.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u0410 \u0432\u043e\u0442 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435, \u0433\u0434\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"q = 0.5\" alt=\"q = 0.5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/1f\/1f0\/1f0f8978131216643ef79307a5cf0731.svg\" width=\"56\" height=\"16\" data-width=\"6.949\" data-height=\"1.946\" data-vertical-align=\"-0.439\" style=\"width: 6.949ex; height: 1.946ex; vertical-align: -0.439ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/1f\/1f0\/1f0f8978131216643ef79307a5cf0731.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/1f\/1f0\/1f0f8978131216643ef79307a5cf0731.svg 781w\" loading=\"lazy\" decode=\"async\"\/>, \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u0435\u043d (<img decoding=\"async\" class=\"formula inline\" source=\"0.25\" alt=\"0.25\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/70\/70d\/70da82175ec8a195a3d8b0fa8f69681d.svg\" width=\"32\" height=\"12\" data-width=\"4.023\" data-height=\"1.557\" data-vertical-align=\"-0.05\" style=\"width: 4.023ex; height: 1.557ex; vertical-align: -0.05ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/70\/70d\/70da82175ec8a195a3d8b0fa8f69681d.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/70\/70d\/70da82175ec8a195a3d8b0fa8f69681d.svg 781w\" loading=\"lazy\" decode=\"async\"\/>), \u0438 \u0432\u0435\u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d <img decoding=\"async\" class=\"formula inline\" source=\"16\\delta\" alt=\"16\\delta\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/86\/86a\/86aa4090ef2c8a295a321786cb97d6c8.svg\" width=\"26\" height=\"18\" data-width=\"3.267\" data-height=\"2.262\" data-vertical-align=\"-0.566\" style=\"width: 3.267ex; height: 2.262ex; vertical-align: -0.566ex\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/86\/86a\/86aa4090ef2c8a295a321786cb97d6c8.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/86\/86a\/86aa4090ef2c8a295a321786cb97d6c8.svg 781w\" loading=\"lazy\" decode=\"async\"\/>. \u0412 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <strong>\u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0435 \u0441\u0436\u0430\u0442\u0438\u0435<\/strong>: \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u2014 \u0432\u044b\u0441\u043e\u043a\u0430\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430 \u0441\u0447\u0451\u0442 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432, \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u043d\u0438\u0437\u043a\u0430\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430 \u0441\u0447\u0451\u0442 \u0431\u043e\u043b\u044c\u0448\u0438\u0445.<\/p>\n<p>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 $ \\delta $ (\u0434\u0435\u043b\u044c\u0442\u0430) \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c\u0438 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 $ \\delta $, \u0442\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0438 \u0442\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043e\u0437\u0434\u0430\u0442\u044c. \u041f\u0440\u0438 $ \\delta = 100 $ \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u043e\u043a\u043e\u043b\u043e 50\u2013100. \u041f\u0440\u0438 $ \\delta = 1000 $ \u2014 \u043e\u043a\u043e\u043b\u043e 500\u20131000. \u041f\u0430\u043c\u044f\u0442\u044c \u0440\u0430\u0441\u0442\u0451\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0441 $ \\delta $, \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043a\u0430\u043a $ 1\/\\sqrt{\\delta} $.<\/p>\n<p>\u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 T-Digest \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0435 \u0441 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438, \u0430 \u0432 \u043f\u043e\u0442\u043e\u043a\u0435. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <strong>\u0431\u0443\u0444\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/strong>:<\/p>\n<ol>\n<li>\n<p>\u041d\u043e\u0432\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0432 \u0431\u0443\u0444\u0435\u0440.<\/p>\n<\/li>\n<li>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0431\u0443\u0444\u0435\u0440 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f (\u0438\u043b\u0438 \u043f\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0443), \u0432\u0441\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b (\u0441\u0442\u0430\u0440\u044b\u0435 + \u043d\u043e\u0432\u044b\u0435 \u0438\u0437 \u0431\u0443\u0444\u0435\u0440\u0430) \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u043f\u043e \u0441\u0440\u0435\u0434\u043d\u0435\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e.<\/p>\n<\/li>\n<li>\n<p>\u0414\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u0436\u0430\u0434\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e: \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u043c \u043b\u0438\u043c\u0438\u0442 \u0432\u0435\u0441\u0430, \u0437\u0430\u0442\u0435\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439.<\/p>\n<\/li>\n<\/ol>\n<p>\u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <strong>buffer-and-merge<\/strong>. \u0415\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 $ O(n \\log n) $ \u043d\u0430 \u043e\u0434\u0438\u043d \u043c\u0451\u0440\u0436, \u043d\u043e \u043c\u0435\u0440\u0436\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0440\u0435\u0434\u043a\u043e (\u043a\u0430\u0436\u0434\u044b\u0435 $ \\delta $ \u0442\u043e\u0447\u0435\u043a). \u0410\u043c\u043e\u0440\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u2014 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e.<\/p>\n<p>\u0412\u0430\u0436\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c: T-Digest \u043d\u0435 \u0434\u0430\u0451\u0442 \u0441\u0442\u0440\u043e\u0433\u0438\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0439 \u043e\u0448\u0438\u0431\u043a\u0438. \u041a\u0430\u043a \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043e \u0432 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u0438 Apache Datasketches (\u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c \u0430\u043d\u0430\u043b\u0438\u0437 \u043e\u0442\u0442\u0443\u0434\u0430 \u043d\u0438\u0436\u0435), \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <strong>\u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439<\/strong>, \u0438 \u0435\u0433\u043e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0430 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439 \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u043d\u043e, \u043d\u043e \u0434\u043b\u044f pathological cases (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0437\u043a\u0438\u043c\u0438 \u0441\u043a\u0430\u0447\u043a\u0430\u043c\u0438) \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0448\u0435.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u043e\u0433\u0434\u0430 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u044f\u0441\u043d\u0430, \u043f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 C.<\/p>\n<h3>\u276f \u042d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u0438 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f<\/h3>\n<p>\u0412 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u0438 <a href=\"https:\/\/datasketches.apache.org\/docs\/tdigest\/tdigest.html\">Apache Datasketches<\/a> \u043f\u0440\u044f\u043c\u043e \u0433\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e T-Digest \u2014 \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0423 \u043d\u0435\u0433\u043e \u043d\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u043e\u0448\u0438\u0431\u043a\u0438, \u0438 \u0435\u0433\u043e \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>\u0418\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 <strong>\u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 (bias)<\/strong>:<\/p>\n<ul>\n<li>\n<p>T-Digest <strong>\u0437\u0430\u043d\u0438\u0436\u0430\u0435\u0442<\/strong> \u043d\u0438\u0437\u043a\u0438\u0435 \u0440\u0430\u043d\u0433\u0438 (\u043c\u0430\u043b\u044b\u0435 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438);<\/p>\n<\/li>\n<li>\n<p>T-Digest <strong>\u0437\u0430\u0432\u044b\u0448\u0430\u0435\u0442<\/strong> \u0432\u044b\u0441\u043e\u043a\u0438\u0435 \u0440\u0430\u043d\u0433\u0438 (\u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438).<\/p>\n<\/li>\n<\/ul>\n<p>\u042d\u0444\u0444\u0435\u043a\u0442 \u0443\u0441\u0438\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u043e\u0431\u044a\u0451\u043c\u0430 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u043e\u0442 \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043e\u0448\u0438\u0431\u043a\u0430 \u0440\u0430\u043d\u0433\u0430 \u0434\u043b\u044f \u0440\u0430\u0437\u043d\u044b\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 (2\u00d710\u00b9\u2070, 2\u00d710\u00b9\u2075, 2\u00d710\u00b2\u2070, 2\u00d710\u00b2\u2075):<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/96\/c7\/00\/96c700d30009a8f31714434890e8e481.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/96\/c7\/00\/96c700d30009a8f31714434890e8e481.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/96\/c7\/00\/96c700d30009a8f31714434890e8e481.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/16\/fa\/81\/16fa812ae42f96fe4179d82dad7eab7a.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/16\/fa\/81\/16fa812ae42f96fe4179d82dad7eab7a.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/16\/fa\/81\/16fa812ae42f96fe4179d82dad7eab7a.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/51\/5e\/b5\/515eb583d8123902a6c21c51130e3d38.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/51\/5e\/b5\/515eb583d8123902a6c21c51130e3d38.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/51\/5e\/b5\/515eb583d8123902a6c21c51130e3d38.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/5c\/fe\/fd\/5cfefdd6bba6009e72fa05eb92d3271e.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/5c\/fe\/fd\/5cfefdd6bba6009e72fa05eb92d3271e.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/5c\/fe\/fd\/5cfefdd6bba6009e72fa05eb92d3271e.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u041d\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0430\u0445 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0442\u0451\u0442 \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043d\u043e \u0432 \u0440\u0430\u0439\u043e\u043d\u0435 \u044d\u043a\u0441\u0442\u0440\u0435\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439 (q \u2248 0 \u0438\u043b\u0438 q \u2248 1) \u043e\u0448\u0438\u0431\u043a\u0430 \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043c\u0430\u043b\u043e\u0439.<\/p>\n<p>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u0440\u0430\u043d\u0433\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043f\u043e\u0442\u043e\u043a\u0430:<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/4f\/d5\/90\/4fd5902d16be3d076f64d7865e8b0317.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/4f\/d5\/90\/4fd5902d16be3d076f64d7865e8b0317.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/4f\/d5\/90\/4fd5902d16be3d076f64d7865e8b0317.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u041f\u0440\u0438 \u043c\u0430\u043b\u044b\u0445 \u043e\u0431\u044a\u0451\u043c\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 (\u0434\u043e 10\u2074) \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u043c\u0435\u0442\u043d\u043e\u0439, \u043d\u043e \u043f\u043e\u0441\u043b\u0435 10\u2075 \u043e\u043d\u0430 \u0441\u0442\u0430\u0431\u0438\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0438 \u043d\u0435 \u0440\u0430\u0441\u0442\u0451\u0442. \u042d\u0442\u043e \u043e\u0431\u044a\u044f\u0441\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043d\u0443\u0436\u043d\u043e \u00ab\u043d\u0430\u0441\u0442\u0440\u043e\u0438\u0442\u044c\u0441\u044f\u00bb \u2014 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432.<\/p>\n<p>\u0421\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 T-Digest \u0441 REQ-\u0441\u043a\u0435\u0442\u0447\u0435\u043c (\u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u043b\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439 \u0438\u0437 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 Datasketches, <a href=\"https:\/\/datasketches.apache.org\/docs\/REQ\/ReqSketch.html\">\u0441\u0441\u044b\u043b\u043a\u0430<\/a>):<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/b5\/7d\/d9\/b57dd9a30987a3691c126c672fb7b402.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/b5\/7d\/d9\/b57dd9a30987a3691c126c672fb7b402.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/b5\/7d\/d9\/b57dd9a30987a3691c126c672fb7b402.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/79\/02\/24\/790224a536cf23b407eacfb610e0fafb.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/79\/02\/24\/790224a536cf23b407eacfb610e0fafb.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/79\/02\/24\/790224a536cf23b407eacfb610e0fafb.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/aa\/0c\/6e\/aa0c6e436e2ed716c1dbf6ed9a33cbd0.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/aa\/0c\/6e\/aa0c6e436e2ed716c1dbf6ed9a33cbd0.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/aa\/0c\/6e\/aa0c6e436e2ed716c1dbf6ed9a33cbd0.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/bf\/c9\/d0\/bfc9d0313ddd8ad2b11bac5bbadf7719.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/bf\/c9\/d0\/bfc9d0313ddd8ad2b11bac5bbadf7719.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/bf\/c9\/d0\/bfc9d0313ddd8ad2b11bac5bbadf7719.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>REQ-\u0441\u043a\u0435\u0442\u0447 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442: \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u043d\u0438\u0437\u043a\u0438\u0445 \u0438\u043b\u0438 \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u0440\u0430\u043d\u0433\u0430\u0445 (HRA \u2014 High Rank Accuracy). T-Digest \u0434\u0430\u0451\u0442 \u0445\u043e\u0440\u043e\u0448\u0443\u044e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u043e\u0431\u043e\u0438\u0445 \u043a\u043e\u043d\u0446\u0430\u0445 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e, \u043d\u043e, \u0443\u0432\u044b, \u0436\u0435\u0440\u0442\u0432\u0443\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0432 \u0446\u0435\u043d\u0442\u0440\u0435. \u041d\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0430\u0445 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e T-Digest \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 REQ \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u043d\u0433\u0430, \u043d\u043e \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<h2>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 C<\/h2>\n<p>\u042f \u0432\u0437\u044f\u043b \u0437\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e <a href=\"https:\/\/github.com\/ajwerner\/tdigestc\">ajwerner\/tdigestc<\/a>. \u041e\u043d\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u043d\u0430 \u0447\u0438\u0441\u0442\u043e\u043c C, \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u044e \u0432\u043d\u0443\u0442\u0440\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c.<\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0435\u0433\u043e \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u0435\u043d \u043f\u043e <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\">\u044d\u0442\u043e\u0439 \u0441\u0441\u044b\u043b\u043a\u0435<\/a>, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430 \u0432 \u0444\u0430\u0439\u043b\u0430\u0445 <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\/blob\/main\/src\/tdigest.c\">src\/tdigest.c<\/a>, <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\/blob\/main\/src\/tdigest.h\">src\/tdigest.h<\/a> \u0438 <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\/blob\/main\/src\/tests.c\">src\/tests.c<\/a>.<\/p>\n<pre><code class=\"cpp\">typedef struct node {    double mean;    double count;} node_t;struct td_histogram {    double compression;    int cap;    int merged_nodes;    int unmerged_nodes;    double merged_count;    double unmerged_count;    node_t nodes[0];};<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:87px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0423 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0434\u0432\u0430 \u043f\u043e\u043b\u044f: \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (<code>mean<\/code>) \u0438 \u0432\u0435\u0441 (<code>count<\/code>). \u0413\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0443\u0444\u0435\u0440\u0435: \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u00ab\u0441\u043b\u0438\u0442\u044b\u0435\u00bb (<code>merged_nodes<\/code>), \u0437\u0430\u0442\u0435\u043c \u00ab\u0431\u0443\u0444\u0435\u0440\u043d\u044b\u0435\u00bb (<code>unmerged_nodes<\/code>). \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u0431\u0435\u0437 \u043f\u0435\u0440\u0435\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041f\u043e\u043b\u0435 <code>nodes[0]<\/code> \u2014 \u0433\u0438\u0431\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 (flexible array member), \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u0435\u0433\u043e \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0437\u0443 \u0432 <code>td_new<\/code>.<\/p>\n<h3>\u276f \u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/h3>\n<p><strong>\u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435:<\/strong><\/p>\n<pre><code class=\"cpp\">td_histogram_t* td_new(double compression) {    size_t memsize = td_required_buf_size(compression);    return td_init(compression, memsize, (char*)(malloc(memsize)));}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0401\u043c\u043a\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a <code>6 * compression + 10<\/code>. \u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 6 \u0432\u0437\u044f\u0442 \u0441 \u0437\u0430\u043f\u0430\u0441\u043e\u043c \u2014 \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u043e, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 <code>compression<\/code>.<\/p>\n<p><strong>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0442\u043e\u0447\u043a\u0438:<\/strong><\/p>\n<pre><code class=\"cpp\">void td_add(td_histogram_t* h, double mean, double count) {    if (should_merge(h)) {        merge(h);    }    h-&gt;nodes[next_node(h)] = (node_t){.mean = mean, .count = count};    h-&gt;unmerged_nodes++;    h-&gt;unmerged_count += count;}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0422\u043e\u0447\u043a\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u0432 \u0431\u0443\u0444\u0435\u0440. \u041a\u043e\u0433\u0434\u0430 <code>merged_nodes + unmerged_nodes == cap<\/code>, \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <code>merge()<\/code>.<\/p>\n<p><strong>\u0421\u043b\u0438\u044f\u043d\u0438\u0435 (\u044f\u0434\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430):<\/strong><\/p>\n<pre><code class=\"cpp\">static void merge(td_histogram_t* h) {    if (h-&gt;unmerged_nodes == 0) return;    int N = h-&gt;merged_nodes + h-&gt;unmerged_nodes;    qsort(h-&gt;nodes, N, sizeof(node_t), &amp;compare_nodes);    double total_count = h-&gt;merged_count + h-&gt;unmerged_count;    double denom = 2 * M_PI * total_count * log(total_count);    double normalizer = h-&gt;compression \/ denom;    int cur = 0;    double count_so_far = 0;    for (int i = 1; i &lt; N; i++) {        double proposed_count = h-&gt;nodes[cur].count + h-&gt;nodes[i].count;        double z = proposed_count * normalizer;        double q0 = count_so_far \/ total_count;        double q2 = (count_so_far + proposed_count) \/ total_count;        bool should_add = (z &lt;= (q0 * (1 - q0))) &amp;&amp; (z &lt;= (q2 * (1 - q2)));        if (should_add) {            h-&gt;nodes[cur].count += h-&gt;nodes[i].count;            double delta = h-&gt;nodes[i].mean - h-&gt;nodes[cur].mean;            double weighted_delta = (delta * h-&gt;nodes[i].count) \/ h-&gt;nodes[cur].count;            h-&gt;nodes[cur].mean += weighted_delta;        } else {            count_so_far += h-&gt;nodes[cur].count;            cur++;            h-&gt;nodes[cur] = h-&gt;nodes[i];        }    }    h-&gt;merged_nodes = cur + 1;    h-&gt;merged_count = total_count;    h-&gt;unmerged_nodes = 0;    h-&gt;unmerged_count = 0;}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0417\u0434\u0435\u0441\u044c \u0432\u0438\u0434\u043d\u043e \u0447\u0442\u043e \u0432\u0441\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b (\u0438 \u0441\u0442\u0430\u0440\u044b\u0435, \u0438 \u043d\u043e\u0432\u044b\u0435 \u0438\u0437 \u0431\u0443\u0444\u0435\u0440\u0430) \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u043f\u043e <code>mean<\/code>. \u0417\u0430\u0442\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0430\u0442\u043e\u0440 (\u043e\u043d \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u044d\u0442\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441\u0430, \u043d\u043e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0432 99% \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u0438 \u043d\u0430\u0448 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442) <code>normalizer = compression \/ (2\u03c0 \u00b7 total_count \u00b7 log(total_count))<\/code>. \u0417\u0430\u0442\u0435\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0432\u044b\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f  <code>z = proposed_count \u00b7 normalizer<\/code>, \u0438 \u0435\u0441\u043b\u0438 \u043e\u043d \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 <code>q0(1-q0)<\/code> \u0438 <code>q2(1-q2)<\/code>, \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u044e\u0442\u0441\u044f. \u041d\u0443 \u0438 \u043f\u0440\u0438 \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u043d\u0438\u0438 \u0432\u0435\u0441 \u0441\u0443\u043c\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u0435.<\/p>\n<p>\u0412 \u043a\u043e\u0434\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0430\u0442\u043e\u0440 \u0441 <code>log(total_count)<\/code> \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 scale function \u0441 \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441\u043e\u043c. \u0410\u0440\u043a\u0441\u0438\u043d\u0443\u0441 \u0442\u043e\u0447\u043d\u0435\u0435 \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445, \u043d\u043e \u0447\u0443\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0438 \u043c\u0435\u043d\u0435\u0435 \u0442\u043e\u0447\u0435\u043d \u0432 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u043c. \u0414\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0445\u0432\u0430\u0442\u0438\u0442 \u0441 \u0433\u043e\u043b\u043e\u0432\u043e\u0439.<\/p>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441 arcsin<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0415\u0441\u043b\u0438 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0435\u0435, \u043c\u043e\u0436\u0435\u0442\u0435 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e merge \u043d\u0430 \u044d\u0442\u0443:<\/p>\n<pre><code class=\"cpp\">static void merge(td_histogram_t* h) {    if (h-&gt;unmerged_nodes == 0) {        return;    }    int N = h-&gt;merged_nodes + h-&gt;unmerged_nodes;    qsort((void*)(h-&gt;nodes), N, sizeof(node_t), &amp;compare_nodes);    double total_count = h-&gt;merged_count + h-&gt;unmerged_count;    int cur = 0;    double count_so_far = 0;    for (int i = 1; i &lt; N; i++) {        double proposed_count = h-&gt;nodes[cur].count + h-&gt;nodes[i].count;        double q_left = count_so_far \/ total_count;        double q_right = (count_so_far + proposed_count) \/ total_count;        double k_left = (h-&gt;compression \/ (2 * M_PI)) * asin(2 * q_left - 1);        double k_right = (h-&gt;compression \/ (2 * M_PI)) * asin(2 * q_right - 1);        bool should_add = (k_right - k_left) &lt;= 1.0;        if (should_add) {            h-&gt;nodes[cur].count += h-&gt;nodes[i].count;            double delta = h-&gt;nodes[i].mean - h-&gt;nodes[cur].mean;            double weighted_delta = (delta * h-&gt;nodes[i].count) \/ h-&gt;nodes[cur].count;            h-&gt;nodes[cur].mean += weighted_delta;        } else {            count_so_far += h-&gt;nodes[cur].count;            cur++;            h-&gt;nodes[cur] = h-&gt;nodes[i];        }    }    h-&gt;merged_nodes = cur + 1;    h-&gt;merged_count = total_count;    h-&gt;unmerged_nodes = 0;    h-&gt;unmerged_count = 0;}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041d\u0430 \u043c\u043e\u0435\u0439 \u043c\u0430\u0448\u0438\u043d\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0430\u043a\u0438\u0435:<\/p>\n<pre><code class=\"bash\"> $ .\/tdigest 200 123 100000 0.95 10iteration,delta,n_points,quantile,exact_quantile,td_quantile,error_percent,n_centroids,add_time_ms1,200,100000,0.950000,13.281110,13.280132,0.007366,117,202,200,100000,0.950000,13.267992,13.271599,0.027183,119,203,200,100000,0.950000,13.287434,13.288471,0.007805,117,194,200,100000,0.950000,13.301317,13.301405,0.000663,117,195,200,100000,0.950000,13.284268,13.286617,0.017681,118,196,200,100000,0.950000,13.275179,13.277275,0.015786,115,197,200,100000,0.950000,13.290458,13.288705,0.013186,116,198,200,100000,0.950000,13.255895,13.255401,0.003722,114,209,200,100000,0.950000,13.308071,13.309063,0.007458,116,1910,200,100000,0.950000,13.280319,13.281976,0.012479,118,20 $ .\/tdigest testit took 0.234611 or 0.000000 per0.000000: 0.0010710.010000: 0.9960550.100000: 9.9656490.200000: 19.9858390.300000: 29.9871030.400000: 40.0245850.500000: 50.0522440.600000: 60.0613190.700000: 70.0609070.800000: 80.0298070.900000: 89.9924590.990000: 99.0014471.000000: 99.999165Tests run: 5ALL TESTS PASSED<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0432\u0437\u044f\u043b \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u0443\u044e \u0432\u0435\u0440\u0441\u0438\u044e. \u042d\u0442\u0430\u043b\u043e\u043d\u043d\u0430\u044f \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f, \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0430 \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 &#8212; arcsin \u0432\u0435\u0440\u0441\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u0430 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043b\u0443\u0447\u0448\u0443\u044e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 (0.011% vs 0.017%), \u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u0442 \u043d\u0430 ~15% \u0431\u043e\u043b\u044c\u0448\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 ~8% \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435. \u041d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 arcsin-\u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0442\u043e\u0447\u043d\u0435\u0435, \u043d\u043e \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0430.<\/p>\n<\/div>\n<\/details>\n<p><strong>\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044f:<\/strong><\/p>\n<pre><code class=\"cpp\">double td_value_at(td_histogram_t* h, double q) {    merge(h);    double goal = q * h-&gt;merged_count;    double k = 0;    int i = 0;    node_t* n = NULL;    for (i = 0; i &lt; h-&gt;merged_nodes; i++) {        n = &amp;h-&gt;nodes[i];        if (k + n-&gt;count &gt; goal) break;        k += n-&gt;count;    }    \/\/ \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430\u043c\u0438    double delta_k = goal - k - (n-&gt;count \/ 2);    if (is_very_small(delta_k)) return n-&gt;mean;    \/\/ ... \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u0438\u043d\u0443\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 <code>merge()<\/code> \u2014 \u0432\u0441\u0435 \u0431\u0443\u0444\u0435\u0440\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b. \u0417\u0430\u0442\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430. \u0415\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u0440\u043e\u0432\u043d\u043e \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u2014 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0435\u0433\u043e <code>mean<\/code>. \u0418\u043d\u0430\u0447\u0435 \u2014 \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430\u043c\u0438.<\/p>\n<p><strong>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432:<\/strong><\/p>\n<pre><code class=\"cpp\">int td_centroid_count(td_histogram_t* h) {    merge(h);    return h-&gt;merged_nodes;}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u0434\u043b\u044f \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u043e\u0432. \u041f\u0440\u0438\u043d\u0443\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043b\u0438\u0432\u0430\u0435\u0442 \u0431\u0443\u0444\u0435\u0440 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432.<\/p>\n<h2>\u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u0438 \u0433\u0440\u0430\u0444\u0438\u043a\u0438<\/h2>\n<p>\u042f \u043f\u0440\u043e\u0433\u043d\u0430\u043b \u0448\u0435\u0441\u0442\u044c \u0441\u0435\u0440\u0438\u0439 \u0442\u0435\u0441\u0442\u043e\u0432 \u043d\u0430 \u0441\u0432\u043e\u0451\u043c \u0440\u0430\u0431\u043e\u0447\u0435\u043c \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0435 (Ryzen 7 5825U, 16 \u0413\u0411 \u041e\u0417\u0423). \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043b \u043e\u0431\u0432\u044f\u0437\u043a\u0443 <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\/blob\/main\/src\/main.c\">main.c<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u0434\u0430\u0451\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u0432 CSV-\u0444\u043e\u0440\u043c\u0430\u0442\u0435. \u041e\u043d\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b: \u0434\u0435\u043b\u044c\u0442\u0443, \u0441\u0438\u0434, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a, \u043d\u0443\u0436\u043d\u044b\u0439 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439.<\/p>\n<p>\u041a\u0441\u0442\u0430\u0442\u0438, \u0442\u0430\u043a\u0436\u0435 \u0435\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 \u2014 test, \u0442\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f:<\/p>\n<pre><code>it took 0.214939 or 0.000000 per0.000000: 0.0000660.010000: 0.9954850.100000: 9.9935480.200000: 19.9245440.300000: 29.9077340.400000: 39.9244460.500000: 49.9450360.600000: 59.9638270.700000: 69.9949600.800000: 80.0318040.900000: 89.9871730.990000: 99.0024071.000000: 99.999976Tests run: 5ALL TESTS PASSED<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0410 \u0432\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e \u0432\u0445\u043e\u0434\u043d\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c:<\/p>\n<pre><code>.\/tdigest 200 123 100000 0.95 10iteration,delta,n_points,quantile,exact_quantile,td_quantile,error_percent,n_centroids,add_time_ms1,200,100000,0.950000,13.281110,13.278724,0.017967,106,172,200,100000,0.950000,13.267992,13.268716,0.005454,103,173,200,100000,0.950000,13.287434,13.286071,0.010256,104,174,200,100000,0.950000,13.301317,13.301515,0.001489,102,185,200,100000,0.950000,13.284268,13.289138,0.036659,101,176,200,100000,0.950000,13.275179,13.277912,0.020580,102,177,200,100000,0.950000,13.290458,13.285319,0.038662,101,188,200,100000,0.950000,13.255895,13.258903,0.022696,104,179,200,100000,0.950000,13.308071,13.309755,0.012658,100,1710,200,100000,0.950000,13.280319,13.276395,0.029541,101,18<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043b <a href=\"https:\/\/github.com\/alexeev-prog\/tdigest-algorithm\/blob\/main\/plotbuild.py\">Python-\u0441\u043a\u0440\u0438\u043f\u0442<\/a>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0447\u0438\u0442\u0430\u0435\u0442 \u0432\u044b\u0432\u043e\u0434 \u0438 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442 \u0433\u0440\u0430\u0444\u0438\u043a\u0438. \u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u2014 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0441 \u03bc=10, \u03c3=2, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u0435 [0, 100]. \u041a\u0430\u0436\u0434\u044b\u0439 \u0442\u0435\u0441\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u043b\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437.<\/p>\n<h3>\u276f 1. \u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u043e\u0442 \u03b4 (compression factor)<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>n_points=100000, quantile=0.99, \u03b4 \u2208 [10, 20, 50, 100, 200, 500, 1000]<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u043e\u0448\u0438\u0431\u043a\u0430 \u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u03b4. \u041f\u0440\u0438 \u03b4=10 \u043e\u0448\u0438\u0431\u043a\u0430 ~0.8%, \u043f\u0440\u0438 \u03b4=1000 \u2014 ~0.01%. \u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u0430\u044f.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/1a\/fa\/14\/1afa14322072e9297dfd3852247e4a71.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/1a\/fa\/14\/1afa14322072e9297dfd3852247e4a71.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/1a\/fa\/14\/1afa14322072e9297dfd3852247e4a71.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f 2. \u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>\u03b4=100, quantile=0.99, n \u2208 [1000, 5000, 10000, 50000, 100000, 500000, 1000000]<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u043e\u0448\u0438\u0431\u043a\u0430 \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u0430 (~0.02\u20130.04%) \u043d\u0430 \u0432\u0441\u0451\u043c \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435. T-Digest \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0438 \u043d\u0430 1000, \u0438 \u043d\u0430 1 000 000 \u0442\u043e\u0447\u0435\u043a.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/96\/e1\/47\/96e147334588e4e39daa816ceb48d5ed.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/96\/e1\/47\/96e147334588e4e39daa816ceb48d5ed.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/96\/e1\/47\/96e147334588e4e39daa816ceb48d5ed.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f 3. \u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u044b\u0431\u043e\u0440\u043a\u0438<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>\u03b4=100, quantile=0.99, n \u2208 [1000, 5000, 10000, 50000, 100000, 500000, 1000000]<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u043e\u0447\u0442\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e: 1000 \u0442\u043e\u0447\u0435\u043a \u2014 2 \u043c\u0441, 100 000 \u2014 16 \u043c\u0441, 1 000 000 \u2014 ~150 \u043c\u0441. \u041d\u0430 100k \u0442\u043e\u0447\u0435\u043a \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 8\u201318 \u043c\u0441.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/86\/24\/16\/862416a119e676fa7008c6a15a44f927.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/86\/24\/16\/862416a119e676fa7008c6a15a44f927.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/86\/24\/16\/862416a119e676fa7008c6a15a44f927.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f 4. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 vs \u03b4<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>n_points=100000, \u03b4 \u2208 [10, 20, 50, 100, 200, 500, 1000]<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0440\u0430\u0432\u043d\u043e \u03b4\/2 \u043f\u0440\u0438 \u043c\u0430\u043b\u044b\u0445 \u03b4 \u0438 \u03b4 \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445. \u0414\u043b\u044f \u03b4=200 \u2014 ~100 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/a5\/3d\/d0\/a53dd0737c2163d062d0ee6542a0a88d.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/a5\/3d\/d0\/a53dd0737c2163d062d0ee6542a0a88d.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/a5\/3d\/d0\/a53dd0737c2163d062d0ee6542a0a88d.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f 5. \u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u043e\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044f<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>\u03b4=100, n_points=100000, q \u2208 [0.5, 0.9, 0.95, 0.99, 0.999, 0.9999]<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430 \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 (0.001% \u0434\u043b\u044f p9999) \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 (0.08% \u0434\u043b\u044f \u043c\u0435\u0434\u0438\u0430\u043d\u044b). \u0418\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0438 \u0437\u0430\u0434\u0443\u043c\u0430\u043d\u043e.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/b6\/b5\/97\/b6b597e572c256d44292afe6d5d76072.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/b6\/b5\/97\/b6b597e572c256d44292afe6d5d76072.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/b6\/b5\/97\/b6b597e572c256d44292afe6d5d76072.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f 6. \u0420\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u0448\u0438\u0431\u043a\u0438 (30 \u0437\u0430\u043f\u0443\u0441\u043a\u043e\u0432)<\/h3>\n<p><strong>\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:<\/strong> <code>\u03b4=100, n_points=100000, quantile=0.99, 30 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439<\/code><\/p>\n<p><strong>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/strong> \u0441\u0440\u0435\u0434\u043d\u044f\u044f \u043e\u0448\u0438\u0431\u043a\u0430 ~0.03%, \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u043e\u0435 \u043e\u0442\u043a\u043b\u043e\u043d\u0435\u043d\u0438\u0435 ~0.005%. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0442\u0430\u0431\u0438\u043b\u0435\u043d.<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/21\/3b\/84\/213b8468043743a5c21e61b625245fde.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/21\/3b\/84\/213b8468043743a5c21e61b625245fde.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/21\/3b\/84\/213b8468043743a5c21e61b625245fde.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<h3>\u276f \u0418\u0442\u043e\u0433\u043e\u0432\u044b\u0435 \u0446\u0438\u0444\u0440\u044b<\/h3>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<th>\n<p align=\"left\">\u041c\u0435\u0442\u0440\u0438\u043a\u0430<\/p>\n<\/th>\n<th>\n<p align=\"left\">\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/p>\n<\/th>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041e\u0448\u0438\u0431\u043a\u0430 p95 \u043f\u0440\u0438 \u03b4=200<\/p>\n<\/td>\n<td>\n<p align=\"left\">0.001\u20130.02%<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041e\u0448\u0438\u0431\u043a\u0430 p99 \u043f\u0440\u0438 \u03b4=100<\/p>\n<\/td>\n<td>\n<p align=\"left\">0.01\u20130.08%<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0412\u0440\u0435\u043c\u044f \u043d\u0430 100k \u0442\u043e\u0447\u0435\u043a<\/p>\n<\/td>\n<td>\n<p align=\"left\">8\u201318 \u043c\u0441<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0427\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043f\u0440\u0438 \u03b4=100<\/p>\n<\/td>\n<td>\n<p align=\"left\">~50\u201380<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u0421\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u0442\u043e\u0447\u043d\u044b\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u043e, \u0447\u0442\u043e T-Digest \u0434\u0430\u0451\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b, \u043d\u0435\u043e\u0442\u043b\u0438\u0447\u0438\u043c\u044b\u0435 \u043e\u0442 \u043f\u043e\u043b\u043d\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u043e\u043d\u0438\u0442\u043e\u0440\u0438\u043d\u0433\u0430, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432 \u0441\u043e\u0442\u043d\u0438 \u0440\u0430\u0437 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438.<\/p>\n<details class=\"spoiler\">\n<summary>\u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 arcsin-\u0432\u0435\u0440\u0441\u0438\u0438<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0413\u0440\u0430\u0444\u0438\u043a\u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u043e\u0432 arcsin-\u0432\u0435\u0440\u0441\u0438\u0438 \u043c\u043e\u0436\u0435\u0442\u0435 \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u043d\u0438\u0436\u0435:<\/p>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/02\/20\/6c\/02206c892b68e88b2ff3f9e364deae79.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/02\/20\/6c\/02206c892b68e88b2ff3f9e364deae79.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/02\/20\/6c\/02206c892b68e88b2ff3f9e364deae79.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/3f\/51\/bd\/3f51bd21e595371174b0dd319846817d.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/3f\/51\/bd\/3f51bd21e595371174b0dd319846817d.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/3f\/51\/bd\/3f51bd21e595371174b0dd319846817d.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/f4\/eb\/75\/f4eb75337b063c78fa9f72e31492aa13.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/f4\/eb\/75\/f4eb75337b063c78fa9f72e31492aa13.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/f4\/eb\/75\/f4eb75337b063c78fa9f72e31492aa13.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/c1\/4e\/d3\/c14ed3ce2a30c82593dcf9f3fc03038e.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/c1\/4e\/d3\/c14ed3ce2a30c82593dcf9f3fc03038e.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/c1\/4e\/d3\/c14ed3ce2a30c82593dcf9f3fc03038e.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/18\/3f\/5d\/183f5d61cdf9bc55747069be9887ec17.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/18\/3f\/5d\/183f5d61cdf9bc55747069be9887ec17.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/18\/3f\/5d\/183f5d61cdf9bc55747069be9887ec17.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/5f\/85\/37\/5f8537db891c3e6525e3bfe014561040.png\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/webt\/5f\/85\/37\/5f8537db891c3e6525e3bfe014561040.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/webt\/5f\/85\/37\/5f8537db891c3e6525e3bfe014561040.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<\/div>\n<\/details>\n<h2>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>T-Digest \u2014 \u043a\u0440\u0430\u0439\u043d\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043c\u043d\u0435 \u043e\u043d \u0441\u0440\u0430\u0437\u0443 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0441\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0435\u0433\u043e \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f \u043f\u043e\u043d\u044f\u0442\u043d\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0435\u0441\u0442\u044c \u0440\u0435\u0430\u043b\u044c\u043d\u0430\u044f \u043d\u0443\u0436\u0434\u0430, \u0442\u043e\u0442 \u0436\u0435 \u043f\u043e\u0434\u0441\u0447\u0435\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439. \u041a\u0441\u0442\u0430\u0442\u0438, \u0435\u0441\u043b\u0438 \u0432\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430 \u0442\u0435\u043c\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/1055544\/\">\u0441\u0442\u0430\u0442\u044c\u044e \u043e \u0444\u0438\u043b\u044c\u0442\u0440\u0435 \u0411\u043b\u0443\u043c\u0430<\/a> \u0438\u043b\u0438 <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/1046345\/\">\u0441\u0442\u0430\u0442\u044c\u044e \u043e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 HyperLogLog<\/a>.<\/p>\n<h3>\u276f \u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438:<\/h3>\n<ul>\n<li>\n<p><a href=\"https:\/\/datasketches.apache.org\/docs\/tdigest\/tdigest.html\">apache datasketches \/ t-digest overview<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/github.com\/ajwerner\/tdigestc\">github \/ ajwerner\/tdigestc<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/arxiv.org\/pdf\/1902.04023\">arxiv \/ Computing Extremely Accurate Quantiles Using t-Digests<\/a><\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S2665963820300403\">sciencedirect \/ The t-digest: Efficient estimates of distributions<\/a><\/p>\n<\/li>\n<\/ul>\n<hr\/>\n<blockquote>\n<p><a href=\"https:\/\/t.me\/timewebru\"><strong>\u041d\u043e\u0432\u043e\u0441\u0442\u0438, \u043e\u0431\u0437\u043e\u0440\u044b \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u043e\u0432 \u0438 \u043a\u043e\u043d\u043a\u0443\u0440\u0441\u044b \u043e\u0442 \u043a\u043e\u043c\u0430\u043d\u0434\u044b Timeweb.Cloud \u2014 \u0432 \u043d\u0430\u0448\u0435\u043c Telegram-\u043a\u0430\u043d\u0430\u043b\u0435<\/strong><\/a> <strong>\u21a9<\/strong><\/p>\n<\/blockquote>\n<figure class=\"\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/12d\/733\/7a5\/12d7337a57ad0fb623c0c1f2d1a4043b.jpg\" sizes=\"(max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/12d\/733\/7a5\/12d7337a57ad0fb623c0c1f2d1a4043b.jpg 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/12d\/733\/7a5\/12d7337a57ad0fb623c0c1f2d1a4043b.jpg 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<\/div>\n<p>\u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/1065882\/\">https:\/\/habr.com\/ru\/articles\/1065882\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c, \u0447\u0442\u043e \u0432\u044b \u0438\u043c\u0435\u0435\u0442\u0435 \u0441\u0435\u0440\u0432\u0435\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442 100.000 RPS. \u0412\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0430 \u0434\u0430\u0448\u0431\u043e\u0440\u0434\u0435 99-\u0439 \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044c \u0437\u0430\u0434\u0435\u0440\u0436\u043a\u0438 \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0432\u044b\u0448\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0442\u043e\u043b\u044c\u043a\u043e 1% \u0441\u0430\u043c\u044b\u0445 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u0415\u0441\u043b\u0438 \u0432\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u0435 \u0432\u0441\u0435 100 000 \u0447\u0438\u0441\u0435\u043b \u0437\u0430 \u0441\u0435\u043a\u0443\u043d\u0434\u0443, \u0447\u0435\u0440\u0435\u0437 \u0447\u0430\u0441 \u044d\u0442\u043e 360 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0447\u0438\u0441\u0435\u043b. \u0427\u0435\u0440\u0435\u0437 \u0434\u0435\u043d\u044c \u2014 8.6 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u043e\u0432. \u041a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0445\u0440\u0430\u043d\u0438\u0442\u044c, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u0432\u044b\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c? \u041d\u0435\u0440\u0435\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0433\u043e \u0438 \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0437\u0430\u0442\u0440\u0430\u0442\u043d\u043e.\u041d\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c T-Digest. \u0412\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u043e\u043d \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u0438\u0445 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u0410 \u0432\u0441\u0435 \u0434\u0435\u043b\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f (\u0442\u0430\u043c, \u0433\u0434\u0435 \u043d\u0430\u0448\u0438 \u0445\u0432\u043e\u0441\u0442\u044b) \u043e\u043d \u0434\u0435\u043b\u0430\u0435\u0442 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u043c\u0438 \u0438 \u0442\u043e\u0447\u043d\u044b\u043c\u0438, \u0430 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0438 \u00ab\u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438\u00bb. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0434\u043b\u044f 100 000 \u0442\u043e\u0447\u0435\u043a \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e ~100 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0432\u043c\u0435\u0441\u0442\u043e 100 000 \u0447\u0438\u0441\u0435\u043b. \u042d\u0442\u043e \u0432 \u0441\u043e\u0442\u043d\u0438 \u0440\u0430\u0437 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438. \u0418 \u043f\u0440\u0438\u0442\u043e\u043c \u0447\u0442\u043e \u043e\u0448\u0438\u0431\u043a\u0430 \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 95-\u0433\u043e \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u0441\u0435\u0433\u043e 0.001\u20130.06% (\u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 \u0441\u0436\u0430\u0442\u0438\u044f).\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0440\u0430\u0437\u0431\u0435\u0440\u0443 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043f\u043e\u0447\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a\u043e\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u043c\u0430\u043b\u043e\u0437\u0430\u0442\u0440\u0430\u0442\u043d\u044b\u0439, \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0433\u0440\u0430\u0444\u0438\u043a\u0438 \u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u043a\u0430\u0436\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 C.\u041f\u0435\u0440\u0435\u0434 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0445\u043e\u0447\u0435\u0442\u0441\u044f \u043f\u043e\u0432\u0435\u0434\u0430\u0442\u044c, \u0447\u0442\u043e \u0437\u0430 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438, \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u0438, \u043a\u0430\u043a\u0438\u0435 \u0435\u0441\u0442\u044c \u043d\u0430\u0438\u0432\u043d\u044b\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u0430.q-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043d\u0438\u0436\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043b\u0435\u0436\u0438\u0442 q-\u0434\u043e\u043b\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041c\u0435\u0434\u0438\u0430\u043d\u0430 \u2014 \u044d\u0442\u043e 0.5-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. 95-\u0439 \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044c \u2014 0.95-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. 99-\u0439 \u2014 0.99-\u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c. \u0412 \u043c\u043e\u043d\u0438\u0442\u043e\u0440\u0438\u043d\u0433\u0435 \u0432\u0430\u0436\u043d\u044b \u0438\u043c\u0435\u043d\u043d\u043e \u0445\u0432\u043e\u0441\u0442\u044b: p99 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0441 1% \u0441\u0430\u043c\u044b\u0445 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u0415\u0441\u043b\u0438 p99 \u0440\u0430\u0441\u0442\u0451\u0442 \u2014 \u0443 \u0432\u0430\u0441 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043c\u0435\u0434\u0438\u0430\u043d\u0430 \u0432 \u043d\u043e\u0440\u043c\u0435.\u041a\u0430\u043a \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c? \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431: \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0432\u0437\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u0434 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c q\u00d7N. \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0431\u0435\u0437 \u043f\u0440\u043e\u0431\u043b\u0435\u043c, \u043d\u043e \u043f\u0430\u043c\u044f\u0442\u044c \u0432 \u0438\u0442\u043e\u0433\u0435 O(N), \u0438 \u043f\u0440\u0438 100k RPS \u0437\u0430 \u0447\u0430\u0441 \u043d\u0430\u0431\u0435\u0433\u0430\u0435\u0442 360 \u043c\u043b\u043d \u0447\u0438\u0441\u0435\u043b. \u0410 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0446\u0435\u043b\u044b\u0445 O(N log N) \u043d\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443.\u041c\u043e\u0436\u043d\u043e \u0441\u044d\u043c\u043f\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u2014 \u0431\u0440\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u043e\u0442\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041f\u0430\u043c\u044f\u0442\u0438 \u043c\u0435\u043d\u044c\u0448\u0435, \u043d\u043e \u0432\u044b\u0431\u0440\u043e\u0441\u044b (\u0442\u0435 \u0441\u0430\u043c\u044b\u0435 \u0440\u0435\u0434\u043a\u0438\u0435 1%) \u0441 \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u0430 \u0432\u044b\u0431\u0440\u043e\u0441\u044b \u2014 \u044d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u0438\u0449\u0435\u043c.\u041c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u0443\u044e \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0443: \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e\u0432\u0443\u044e \u043e\u0441\u044c \u043d\u0430 \u0440\u0430\u0432\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b, \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u044f. \u041d\u043e \u0435\u0441\u043b\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u0441\u043a\u043e\u0448\u0435\u043d\u044b (\u0430 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043d\u0438 \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0441\u043a\u043e\u0448\u0435\u043d\u044b), \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b \u0432 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 \u043b\u0438\u0431\u043e \u043f\u0443\u0441\u0442\u044b\u0435, \u043b\u0438\u0431\u043e \u043e\u0433\u0440\u043e\u043c\u043d\u044b\u0435, \u0438 \u0432 \u0438\u0442\u043e\u0433\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043f\u0430\u0434\u0430\u0435\u0442.\u0410 T-Digest \u0440\u0435\u0448\u0430\u0435\u0442 \u044d\u0442\u0443 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u2014 \u043e\u043d \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432\u0441\u0435 \u0434\u0430\u043d\u043d\u044b\u0435, \u043d\u0435 \u0442\u0435\u0440\u044f\u0435\u0442 \u0432\u044b\u0431\u0440\u043e\u0441\u044b \u0438 \u0434\u0430\u0451\u0442 \u0432\u044b\u0441\u043e\u043a\u0443\u044e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0432 \u0445\u0432\u043e\u0441\u0442\u0430\u0445.\u276f \u0421\u0443\u0442\u044c T-DigestT-Digest \u0431\u044b\u043b \u0441\u043e\u0437\u0434\u0430\u043d \u0422\u0435\u0434\u043e\u043c \u0414\u0430\u043d\u0442\u0438\u043d\u0433\u043e\u043c \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 2010-\u0445 \u0433\u043e\u0434\u043e\u0432, \u0430 \u0432 2019 \u0433\u043e\u0434\u0443 \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e \u0441 \u041e\u0442\u043c\u0430\u0440\u043e\u043c \u042d\u0440\u0442\u043b\u043e\u043c \u0432\u044b\u0448\u043b\u0430 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u043e \u043d\u0438\u0445 \u0431\u044b\u043b\u0438 Q-Digest, GK01, \u043d\u043e \u043e\u043d\u0438 \u0434\u0430\u0432\u0430\u043b\u0438 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u0443\u044e \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0443\u044e \u043e\u0448\u0438\u0431\u043a\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439. \u0414\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043e\u0448\u0438\u0431\u043a\u0430 \u00ab\u0432\u0441\u0435\u0433\u043e\u00bb 1% \u2014 \u0434\u043b\u044f \u043c\u0435\u0434\u0438\u0430\u043d\u044b \u044d\u0442\u043e \u00b11%, \u0438 \u0434\u043b\u044f 99-\u0433\u043e \u043f\u0435\u0440\u0446\u0435\u043d\u0442\u0438\u043b\u044f \u0442\u043e\u0436\u0435 \u00b11%. \u041d\u043e \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043d\u0430\u043c \u0432\u0430\u0436\u043d\u0435\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445, \u0433\u0434\u0435 1% \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043a\u0440\u0438\u0442\u0438\u0447\u043d\u044b\u043c.\u0414\u0430\u043d\u0442\u0438\u043d\u0433 \u0438 \u042d\u0440\u0442\u043b \u043f\u043e\u0448\u043b\u0438 \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b. \u041e\u043d\u0438 \u0440\u0435\u0448\u0438\u043b\u0438, \u0447\u0442\u043e \u043e\u0448\u0438\u0431\u043a\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0437\u0430\u0432\u0438\u0441\u0435\u0442\u044c \u043e\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438: \u0447\u0435\u043c \u0431\u043b\u0438\u0436\u0435 \u043a \u043a\u0440\u0430\u044f\u043c, \u0442\u0435\u043c \u0442\u043e\u0447\u043d\u0435\u0435. \u041c\u0435\u0434\u0438\u0430\u043d\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441 \u043e\u0448\u0438\u0431\u043a\u043e\u0439 5%, \u0430 p99 \u2014 \u0441 \u043e\u0448\u0438\u0431\u043a\u043e\u0439 0.1%.\u0421\u0430\u043c \u043a\u043e\u043d\u0446\u0435\u043f\u0442 \u043d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0443\u0436 \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u0439: \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u043c \u0447\u0438\u0441\u043b\u0430 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u041a\u0430\u0436\u0434\u044b\u0439 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0445\u0440\u0430\u043d\u0438\u0442 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 (mean) \u0438 \u0432\u0435\u0441 (weight) \u2014 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0447\u0438\u0441\u0435\u043b \u0432 \u043d\u0435\u0433\u043e \u043f\u043e\u043f\u0430\u043b\u043e.\u041d\u043e \u043a\u0430\u043a \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c? \u0415\u0441\u043b\u0438 \u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u0435 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043f\u043e \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 \u043e\u0441\u0438 \u2014 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0443.\u0412 \u0438\u0442\u043e\u0433\u0435 T-Digest \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u043d\u0435 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e, \u0430 \u043f\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u0418 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0442\u043e\u0433\u043e, \u0433\u0434\u0435 \u043e\u043d \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f: \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435, \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u0431\u043e\u043b\u044c\u0448\u0438\u0435. \u041a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0436\u0430\u0434\u043d\u044b\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u043e\u043c \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0435\u043d \u043b\u0438\u043c\u0438\u0442 \u0432\u0435\u0441\u0430. \u0414\u043b\u044f \u043a\u0440\u0430\u0451\u0432 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0442\u0430\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u0442\u043e\u0447\u043d\u044b\u043c\u0438. \u0414\u043b\u044f \u0446\u0435\u043d\u0442\u0440\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0431\u043e\u043b\u044c\u0448\u043e\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0442\u0430\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u0436\u0438\u0440\u043d\u044b\u0435 \u0438 \u043d\u0435\u0442\u043e\u0447\u043d\u044b\u0435.\u0422\u043e \u0435\u0441\u0442\u044c, \u0432\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, T-Digest \u0433\u0440\u0443\u043f\u043f\u0438\u0440\u0443\u0435\u0442 \u0438\u0445 \u0432 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b. \u042d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u043e\u043b\u0435\u0439: \u0441\u0440\u0435\u0434\u043d\u0435\u0435 (mean) \u043a\u0430\u043a \u0446\u0435\u043d\u0442\u0440 \u043c\u0430\u0441\u0441 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u0438 \u0432\u0435\u0441 (weight) \u2014 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u044d\u0442\u043e\u043c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0435.p99 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0443 \u043d\u0430 \u043a\u0440\u0430\u044e, p50 \u2014 \u043f\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c\u0443 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0443 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\u041a\u0441\u0442\u0430\u0442\u0438, \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c T-Digest \u043d\u0435 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d: \u043f\u0440\u0438 \u0440\u0430\u0437\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043f\u043e\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f. \u041c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c, \u043d\u043e \u044d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0443\u0431\u0438\u0442\u044c \u0430\u0434\u0430\u043f\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c \u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c.\u0414\u0430\u043b\u044c\u0448\u0435 \u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443: \u043a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 scale function \u0438 \u043a\u0430\u043a \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u0434\u0435\u043b\u044c\u0442\u0430 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e.\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 T-Digest: scale function, size bound \u0438 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u041a\u043e\u0433\u0434\u0430 \u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0430\u043b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u0441 T-Digest, \u043c\u0435\u043d\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u043b\u043e \u0442\u043e, \u043a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0448\u0430\u0435\u0442, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0445\u043d\u0443\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434, \u043a\u0430\u043a \u0432\u044b\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b \u0434\u043b\u044f \u0445\u0432\u043e\u0441\u0442\u043e\u0432 \u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0434\u043b\u044f \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u044b.\u0412\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0434\u0435\u043b\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e\u0432\u0443\u044e \u043e\u0441\u044c \u043d\u0430 \u0440\u0430\u0432\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b, T-Digest \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 scale function \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c $ q $ \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 $ k $. \u0421\u0430\u043c\u0430\u044f \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0438\u0437 \u0441\u0442\u0430\u0442\u044c\u0438:\u042d\u0442\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0448\u043a\u0430\u043b\u0430. \u041e\u043d\u0430 \u0434\u0430\u0451\u0442 \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u0435 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b \u2014 \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u0430\u044f \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0430. \u0418\u043d\u0442\u0435\u0440\u0435\u0441 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438:\u041f\u0440\u0438 $ q = 0.5 $ (\u043c\u0435\u0434\u0438\u0430\u043d\u0430) \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441 \u043e\u0442 \u043d\u0443\u043b\u044f \u0434\u0430\u0451\u0442 \u043d\u043e\u043b\u044c. \u041f\u0440\u0438 $ q = 0 $ \u2014 . \u041f\u0440\u0438 $ q = 1 $ \u2014 . \u0413\u0440\u0430\u0444\u0438\u043a \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u043f\u043e\u0447\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442: \u0435\u0441\u043b\u0438 \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043b\u0438\u043d\u0438\u0438 \u043d\u0430 \u0440\u0430\u0432\u043d\u043e\u043c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e \u043e\u0441\u0438 $ k $, \u0442\u043e \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 (\u0433\u0434\u0435 $ q $ \u0431\u043b\u0438\u0437\u043a\u043e \u043a 0 \u0438\u043b\u0438 1) \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0435\u043a\u0446\u0438\u0438 \u043d\u0430 \u043e\u0441\u044c $ q $ \u0431\u0443\u0434\u0443\u0442 \u0433\u0443\u0449\u0435. \u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u044b.\u0422\u0435\u043f\u0435\u0440\u044c \u2014 \u0433\u043b\u0430\u0432\u043d\u043e\u0435. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0435\u0433\u043e \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u043d\u0433\u0438. \u041f\u0443\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434 \u0441 \u0432\u0435\u0441\u043e\u043c , \u0430 \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u044b\u0439 \u0432\u0435\u0441 \u0432\u0441\u0435\u0445 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u043d\u0435\u0433\u043e \u0440\u0430\u0432\u043d\u0430 . \u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u2014 . \u0422\u043e\u0433\u0434\u0430:\u0410 \u0446\u0435\u043d\u0442\u0440 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 (\u0435\u0433\u043e \u043c\u0435\u0434\u0438\u0430\u043d\u0430) \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0442\u043e\u0447\u043a\u0435:\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 scale function:\u0422\u043e \u0435\u0441\u0442\u044c \u00ab\u0440\u0430\u0437\u043c\u0435\u0440\u00bb \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0432 \u0448\u043a\u0430\u043b\u0435 $ k $ \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0442\u044c 1. \u0414\u043b\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0448\u043a\u0430\u043b\u044b $ k_0 $ \u044d\u0442\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435:\u0414\u043b\u044f \u0448\u043a\u0430\u043b\u044b \u0441 \u0430\u0440\u043a\u0441\u0438\u043d\u0443\u0441\u043e\u043c $ k_1 $ \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u0440\u0443\u0433\u043e\u0435, \u043d\u043e \u0438\u0434\u0435\u044f \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0442\u043e\u0439 \u0436\u0435: \u043d\u0430 \u0445\u0432\u043e\u0441\u0442\u0430\u0445 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0446\u0435\u043d\u0442\u0440\u0435.\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c: . \u041d\u0430 \u043a\u0440\u0430\u044f\u0445, \u0433\u0434\u0435 , \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u0440\u0430\u0432\u0435\u043d , \u0438 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u043c \u2014 \u043e\u043a\u043e\u043b\u043e . \u0410 \u0432\u043e\u0442 \u0432 \u0446\u0435\u043d\u0442\u0440\u0435, \u0433\u0434\u0435 , \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u0435\u043d (), \u0438 \u0432\u0435\u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d . \u0412 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0435 \u0441\u0436\u0430\u0442\u0438\u0435: \u043d\u0430 \u043a\u0440\u0430\u044f\u0445 \u2014 \u0432\u044b\u0441\u043e\u043a\u0430\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430 \u0441\u0447\u0451\u0442 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u043e\u0432, \u0432 \u0446\u0435\u043d\u0442\u0440\u0435 \u2014 \u043d\u0438\u0437\u043a\u0430\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430 \u0441\u0447\u0451\u0442 \u0431\u043e\u043b\u044c\u0448\u0438\u0445.\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 $ \\delta $ (\u0434\u0435\u043b\u044c\u0442\u0430) \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c\u0438 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432. \u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 $ \\delta $, \u0442\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u0432\u0435\u0441 \u0438 \u0442\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043e\u0437\u0434\u0430\u0442\u044c. \u041f\u0440\u0438 $ \\delta = 100 $ \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u043e\u043a\u043e\u043b\u043e 50\u2013100. \u041f\u0440\u0438 $ \\delta = 1000 $ \u2014 \u043e\u043a\u043e\u043b\u043e 500\u20131000. \u041f\u0430\u043c\u044f\u0442\u044c \u0440\u0430\u0441\u0442\u0451\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0441 $ \\delta $, \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043a\u0430\u043a $ 1\/\\sqrt{\\delta} $.\u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 T-Digest \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0435 \u0441 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438, \u0430 \u0432 \u043f\u043e\u0442\u043e\u043a\u0435. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0431\u0443\u0444\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f:\u041d\u043e\u0432\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0432 \u0431\u0443\u0444\u0435\u0440.\u041a\u043e\u0433\u0434\u0430 \u0431\u0443\u0444\u0435\u0440 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f (\u0438\u043b\u0438 \u043f\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0443), \u0432\u0441\u0435 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b (\u0441\u0442\u0430\u0440\u044b\u0435 + \u043d\u043e\u0432\u044b\u0435 \u0438\u0437 \u0431\u0443\u0444\u0435\u0440\u0430) \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u043f\u043e \u0441\u0440\u0435\u0434\u043d\u0435\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e.\u0414\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u0436\u0430\u0434\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e: \u0441\u043a\u043b\u0435\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u044b, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u043c \u043b\u0438\u043c\u0438\u0442 \u0432\u0435\u0441\u0430, \u0437\u0430\u0442\u0435\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439.\u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f buffer-and-merge. \u0415\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 $ O(n \\log n) $ \u043d\u0430 \u043e\u0434\u0438\u043d \u043c\u0451\u0440\u0436, \u043d\u043e \u043c\u0435\u0440\u0436\u0438 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0440\u0435\u0434\u043a\u043e (\u043a\u0430\u0436\u0434\u044b\u0435 $ \\delta $ \u0442\u043e\u0447\u0435\u043a). \u0410\u043c\u043e\u0440\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u2014 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e.\u0412\u0430\u0436\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c: T-Digest \u043d\u0435 \u0434\u0430\u0451\u0442 \u0441\u0442\u0440\u043e\u0433\u0438\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0439 \u043e\u0448\u0438\u0431\u043a\u0438. \u041a\u0430\u043a \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043e \u0432 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u0438 Apache Datasketches (\u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c \u0430\u043d\u0430\u043b\u0438\u0437 \u043e\u0442\u0442\u0443\u0434\u0430 \u043d\u0438\u0436\u0435), \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439, \u0438 \u0435\u0433\u043e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0430 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439 \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u043d\u043e, \u043d\u043e \u0434\u043b\u044f pathological cases (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u0430\u043d\u043d\u044b\u0435 \u0441 \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0437\u043a\u0438\u043c\u0438 \u0441\u043a\u0430\u0447\u043a\u0430\u043c\u0438) \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0448\u0435.\u0422\u0435\u043f\u0435\u0440\u044c, \u043a\u043e\u0433\u0434\u0430 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430 \u044f\u0441\u043d\u0430, \u043f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 C.\u276f \u042d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u0438 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f\u0412 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u0438 Apache Datasketches \u043f\u0440\u044f\u043c\u043e \u0433\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e T-Digest \u2014 \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0423 \u043d\u0435\u0433\u043e \u043d\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u043e\u0448\u0438\u0431\u043a\u0438, \u0438 \u0435\u0433\u043e \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.\u0418\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 (bias):T-Digest \u0437\u0430\u043d\u0438\u0436\u0430\u0435\u0442 \u043d\u0438\u0437\u043a\u0438\u0435 \u0440\u0430\u043d\u0433\u0438 (\u043c\u0430\u043b\u044b\u0435 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438);T-Digest \u0437\u0430\u0432\u044b\u0448\u0430\u0435\u0442 \u0432\u044b\u0441\u043e\u043a\u0438\u0435 \u0440\u0430\u043d\u0433\u0438 (\u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0438).\u042d\u0444\u0444\u0435\u043a\u0442 \u0443\u0441\u0438\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u043e\u0431\u044a\u0451\u043c\u0430 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u043e\u0442 \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043e\u0448\u0438\u0431\u043a\u0430 \u0440\u0430\u043d\u0433\u0430 \u0434\u043b\u044f \u0440\u0430\u0437\u043d\u044b\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 (2\u00d710\u00b9\u2070, 2\u00d710\u00b9\u2075, 2\u00d710\u00b2\u2070, 2\u00d710\u00b2\u2075):\u041d\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0430\u0445 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u0442\u0451\u0442 \u0441 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a, \u043d\u043e \u0432 \u0440\u0430\u0439\u043e\u043d\u0435 \u044d\u043a\u0441\u0442\u0440\u0435\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439 (q \u2248 0 \u0438\u043b\u0438 q \u2248 1) \u043e\u0448\u0438\u0431\u043a\u0430 \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043c\u0430\u043b\u043e\u0439.\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u0440\u0430\u043d\u0433\u0430 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043f\u043e\u0442\u043e\u043a\u0430:\u041f\u0440\u0438 \u043c\u0430\u043b\u044b\u0445 \u043e\u0431\u044a\u0451\u043c\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 (\u0434\u043e 10\u2074) \u043e\u0448\u0438\u0431\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u043c\u0435\u0442\u043d\u043e\u0439, \u043d\u043e \u043f\u043e\u0441\u043b\u0435 10\u2075 \u043e\u043d\u0430 \u0441\u0442\u0430\u0431\u0438\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0438 \u043d\u0435 \u0440\u0430\u0441\u0442\u0451\u0442. \u042d\u0442\u043e \u043e\u0431\u044a\u044f\u0441\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043d\u0443\u0436\u043d\u043e \u00ab\u043d\u0430\u0441\u0442\u0440\u043e\u0438\u0442\u044c\u0441\u044f\u00bb \u2014 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432.\u0421\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 T-Digest \u0441 REQ-\u0441\u043a\u0435\u0442\u0447\u0435\u043c (\u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u043b\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u043b\u0435\u0439 \u0438\u0437 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 Datasketches, \u0441\u0441\u044b\u043b\u043a\u0430):REQ-\u0441\u043a\u0435\u0442\u0447 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442: \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u043d\u0438\u0437\u043a\u0438\u0445 \u0438\u043b\u0438 \u0432\u044b\u0441\u043e\u043a\u0438\u0445 \u0440\u0430\u043d\u0433\u0430\u0445 (HRA \u2014 High Rank Accuracy). T-Digest \u0434\u0430\u0451\u0442 \u0445\u043e\u0440\u043e\u0448\u0443\u044e \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u043e\u0431\u043e\u0438\u0445 \u043a\u043e\u043d\u0446\u0430\u0445 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e, \u043d\u043e, \u0443\u0432\u044b, \u0436\u0435\u0440\u0442\u0432\u0443\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0432 \u0446\u0435\u043d\u0442\u0440\u0435. \u041d\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0430\u0445 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e T-Digest \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 REQ \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u043d\u0433\u0430, \u043d\u043e \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0441\u0442\u0438.\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 C\u042f \u0432\u0437\u044f\u043b \u0437\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e ajwerner\/tdigestc. \u041e\u043d\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u043d\u0430 \u0447\u0438\u0441\u0442\u043e\u043c C, \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0430\u043b\u043b\u043e\u043a\u0430\u0446\u0438\u044e \u0432\u043d\u0443\u0442\u0440\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c.\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0435\u0433\u043e \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u0435\u043d \u043f\u043e \u044d\u0442\u043e\u0439 \u0441\u0441\u044b\u043b\u043a\u0435, \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430 \u0432 \u0444\u0430\u0439\u043b\u0430\u0445 src\/tdigest.c, src\/tdigest.h \u0438 src\/tests.c.typedef struct node {    double mean;    double count;} node_t;struct td_histogram {    double compression;    int cap;    int merged_nodes;    int unmerged_nodes;    double merged_count;    double unmerged_count;    node_t nodes[0];};\u0423 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u0430 \u0434\u0432\u0430 \u043f\u043e\u043b\u044f: \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (mean) \u0438 \u0432\u0435\u0441 (count). \u0413\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0443\u0444\u0435\u0440\u0435: \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u00ab\u0441\u043b\u0438\u0442\u044b\u0435\u00bb (merged_nodes), \u0437\u0430\u0442\u0435\u043c \u00ab\u0431\u0443\u0444\u0435\u0440\u043d\u044b\u0435\u00bb (unmerged_nodes). \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u0431\u0435\u0437 \u043f\u0435\u0440\u0435\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041f\u043e\u043b\u0435 nodes[0] \u2014 \u0433\u0438\u0431\u043a\u0438\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 (flexible array member), \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u0435\u0433\u043e \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0437\u0443 \u0432 td_new.\u276f \u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438\u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435:td_histogram_t* td_new(double compression) {    size_t memsize = td_required_buf_size(compression);    return td_init(compression, memsize, (char*)(malloc(memsize)));}\u0401\u043c\u043a\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a 6 * compression + 10. \u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 6 \u0432\u0437\u044f\u0442 \u0441 \u0437\u0430\u043f\u0430\u0441\u043e\u043c \u2014 \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u043e, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u0446\u0435\u043d\u0442\u0440\u043e\u0438\u0434\u043e\u0432 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 compression.\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0442\u043e\u0447\u043a\u0438:void&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-489508","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/489508","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=489508"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/489508\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=489508"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=489508"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=489508"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}