datadog / sketches-js Goto Github PK
View Code? Open in Web Editor NEWTypeScript implementation of the distributed quantile sketch algorithm DDSketch
License: Other
TypeScript implementation of the distributed quantile sketch algorithm DDSketch
License: Other
I noticed that I couldn't compile a TypeScript project which depended on sketch-js, because it couldn't find interfaces exported by the proto:
node_modules/@datadog/sketches-js/dist/ddsketch/mapping/CubicallyInterpolatedMapping.d.ts:2:10 - error TS2305: Module '"../proto/compiled"' has no exported member 'IndexMapping'.
Looking in the node_modules of my project, I noticed that @datadog/sketches-js/dist/ddsketch/proto/compiled.d.ts
contained only the lines:
export = $root;
declare var $root: $protobuf.Root;
import $protobuf = require("protobufjs/minimal");
...instead of the rich types you provide in that file in this git repo.
This looks similar to an issue in another project, which I found when googling the error message I was seeing:
https://github.com/cryptowatch/cw-sdk-node/issues/31
The problem is that tsc, when generating declarations, overrides the existing compiled.d.ts
file in its zeal to declare types for compiled.js
.
When I simply paste the real file into my node_modules, I'm able to successfully build my dependent project.
I looked for ways to avoid generating declarations for only one file, but couldn't find an option like that in tsc
.
I believe this should be resolvable by appending a copy to the build
script in package.json
:
"build": "yarn clean; tsc -p tsconfig.build.json; cp src/ddsketch/proto/compiled.d.ts dist/ddsketch/proto/compiled.d.ts",
Say you have a range of negative numbers, -10 -> -1. You add the lower half of the range to one sketch, and the upper half of the range to another sketch. If you add these sketches together ("Sketch AB"), it will produce different getValueAtQuantile()
results than the same code in Python or the same data from both halves added to a single sketch ("Sketch C") in TypeScript. This only happens with negative numbers: for positive ranges the values match. Full snippets for the ts-node and python interpreters is below, but here are how the results differ for a single sketch reading all the data versus a merge of two sketches with half the data:
q0.01 c: -10.07470 ab: -10.07470
q0.25 c: -7.92497 ab: -7.92497
q0.50 c: -5.98951 ab: -5.98951
q0.75 c: -4.01484 ab: 0.00000
q0.99 c: -1.99366 ab: 0.00000
Whereas in Python the same test returns:
q0.01 c: -10.07470 ab: -10.07470
q0.25 c: -7.92497 ab: -7.92497
q0.50 c: -5.98951 ab: -5.98951
q0.75 c: -4.01484 ab: -4.01484
q0.99 c: -1.99366 ab: -1.99366
To reproduce in ts-node:
import { DDSketch } from '@datadog/sketches-js'
// test data
const posA = [1, 2, 3, 4, 5]
const posB = [6, 7, 8, 9, 10]
// these two will each get half the positive data
const ddsPosA = new DDSketch()
const ddsPosB = new DDSketch()
// and then merge into this one
const ddsPosAB = new DDSketch()
// whereas this one reads all the positive data sequentially
const ddsPosC = new DDSketch()
posA.forEach(s => {
ddsPosA.accept(s)
ddsPosC.accept(s)
})
posB.forEach(s => {
ddsPosB.accept(s)
ddsPosC.accept(s)
})
ddsPosAB._copy(ddsPosA)
ddsPosAB.merge(ddsPosB)
// we'll repeat this for negative numbers
const negA = [-10, -9, -8, -7, -6]
const negB = [-5, -4, -3, -2, -1]
const ddsNegA = new DDSketch()
const ddsNegB = new DDSketch()
const ddsNegAB = new DDSketch()
const ddsNegC = new DDSketch()
negA.forEach(s => {
ddsNegA.accept(s)
ddsNegC.accept(s)
})
negB.forEach(s => {
ddsNegB.accept(s)
ddsNegC.accept(s)
})
ddsNegAB._copy(ddsNegA)
ddsNegAB.merge(ddsNegB)
// the percentiles should be the same
// for the sequential c sketches
// and the merged ab sketches
const qs = [0.01, 0.25, 0.50, 0.75, 0.99]
qs.forEach(q => {
console.log(`pq: ${q.toFixed(2)}\tc: ${ddsPosC.getValueAtQuantile(q).toFixed(5)}\tab: ${ddsPosAB.getValueAtQuantile(q).toFixed(5)}`)
})
qs.forEach(q => {
console.log(`nq: ${q.toFixed(2)}\tc: ${ddsNegC.getValueAtQuantile(q).toFixed(5)}\tab: ${ddsNegAB.getValueAtQuantile(q).toFixed(5)}`)
})
To see what I believe are "correct" results in the python implementation:
from ddsketch import DDSketch
# test data
pos_a = [1, 2, 3, 4, 5]
pos_b = [6, 7, 8, 9, 10]
# these two will each get half the positive data
dds_pos_a = DDSketch()
dds_pos_b = DDSketch()
# and then merge into this one
dds_pos_ab = DDSketch()
# whereas this one reads all the positive data seqquentially
dds_pos_c = DDSketch()
for s in pos_a:
dds_pos_a.add(s)
dds_pos_c.add(s)
for s in pos_b:
dds_pos_b.add(s)
dds_pos_c.add(s)
dds_pos_ab._copy(dds_pos_a)
dds_pos_ab.merge(dds_pos_b)
# we'll repeat this for negative numbers
neg_a = [-10, -9, -8, -7, -6]
neg_b = [-5, -4, -3, -2, -1]
dds_neg_a = DDSketch()
dds_neg_b = DDSketch()
dds_neg_c = DDSketch()
dds_neg_ab = DDSketch()
for s in neg_a:
dds_neg_a.add(s)
dds_neg_c.add(s)
for s in neg_b:
dds_neg_b.add(s)
dds_neg_c.add(s)
dds_neg_ab._copy(dds_neg_a)
dds_neg_ab.merge(dds_neg_b)
# the percentiles should be the same
# for the sequential c sketches
# and the merged ab sketches
qs = [0.01, 0.25, 0.50, 0.75, 0.99]
for q in qs:
print("pq: {:.2f}\tc: {:.5f}\tab: {:.5f}".format(q, dds_pos_c.get_quantile_value(q), dds_pos_ab.get_quantile_value(q)))
for q in qs:
print("nq: {:.2f}\tc: {:.5f}\tab: {:.5f}".format(q, dds_neg_c.get_quantile_value(q), dds_neg_ab.get_quantile_value(q)))
I've tried comparing the TypeScript vs Python implementations looking for differences that could explain this behavior, but nothing jumped out at me. It does look like the sumOfRange()
utility function in the store is used in _adjust()
and merge()
in situations where the equivalent Python code might be an exclusive range while sumOfRange()
is inclusive, but when I tried overriding to add a -1
to the end index for those calls, it didn't seem to change anything.
If anyone has any ideas what the problem might be, I'd be happy to look further and keep testing.
protobufjs is in devDependencies
:
Line 44 in 222854e
But it's required here:
So it should be a regular dependency.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.