2c:null 2d:["$","title",null,{"children":"BTrDB aggregating | Shaun Lebron | Observable"}] 32:T71b,genAggregates = { function aggregatePair(left, right, res) { left = left || { count: 0, mean: 0, // any number (ignored) min: Infinity, max: -Infinity, i: right.i - 1, entryI: right.entryI - 1, time: right.time - 2 ** res }; right = right || { count: 0, mean: 0, // any number (ignored) min: Infinity, max: -Infinity // i: left.i + 1, // don't need // entryI: left.entryI + 1, // don't need // time: left.time + 2 ** res, // don't need }; const count = left.count + right.count; const time = left.time; const i = left.i / 2; const entryI = left.entryI / 2; const min = Math.min(left.min, right.min); const max = Math.max(left.max, right.max); const mean = (left.mean * left.count + right.mean * right.count) / count; return { count, time, i, entryI, min, max, mean }; } function getPairs(points) { const result = []; for (let i = 0; i < points.length; i++) { const curr = points[i]; const next = points[i + 1]; const isCurrLeft = curr.i % 2 === 0; const isNextAdj = next && curr.i + 1 === next.i; let left, right; if (isCurrLeft && isNextAdj) { left = curr; right = next; i++; // skip next } else if (isCurrLeft) { left = curr; right = null; } else { left = null; right = curr; } result.push([left, right]); } return result; } function genAggregates(points, pointRes, targetRes) { const levels = []; for (let res = pointRes; res < targetRes; res++) { const pairs = getPairs(points); points = pairs.map(([a, b]) => aggregatePair(a, b, res)); levels.push(points); } return levels; } return genAggregates; }33:[] 30:{"id":"2cbdfd72fed81fba","slug":"btrdb-aggregating","title":"BTrDB aggregating","thumbnail":"982eeb88ddfeae54ad330caf590cce7fbc2aa84358a72ef34371eb7badd9dccd","access_level":"public","create_time":"$D2018-07-15T22:54:51.375Z","update_time":"$D2018-07-18T21:09:07.085Z","view_time":null,"first_public_time":"$D2018-07-16T05:00:55.940Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ed9847273198461c","login":"shaunlebron","name":"Shaun Lebron","avatar_url":"https://avatars-next.observableusercontent.com/681c504a781cacec69ea0df79eb5a6a890b26146edebc8d1ee3153812c528dc4","tier":"starter_2024","bio":""},"version":308,"publish_version":308,"role":null,"authored":false,"authors":[{"type":"individual","id":"22dcd5a87171b339","login":"shaunlebron","name":"Shaun Lebron","avatar_url":"https://avatars-next.observableusercontent.com/681c504a781cacec69ea0df79eb5a6a890b26146edebc8d1ee3153812c528dc4","tier":null,"bio":""}],"members":[{"type":"individual","id":"22dcd5a87171b339","login":"shaunlebron","name":"Shaun Lebron","avatar_url":"https://avatars-next.observableusercontent.com/681c504a781cacec69ea0df79eb5a6a890b26146edebc8d1ee3153812c528dc4","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"BTrDB aggregating","cells":[{"id":0,"value":"md`# BTrDB aggregating`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"// generate a full range of points n levels down from the top of the tree\nfunction genPoints(levelsFromTop, numTopPoints) {\n const aggRes = 56;\n const res = aggRes - levelsFromTop;\n const pw = 2 ** res;\n const topStartI = Math.max(-16, Math.floor(0 - numTopPoints / 2));\n const topEndI = topStartI + numTopPoints;\n const startI = topStartI * 2 ** levelsFromTop;\n const endI = topEndI * 2 ** levelsFromTop;\n const result = [];\n for (let i = startI; i < endI; i++) {\n const [min, max] = [Math.random(), Math.random()].sort((a, b) => a - b);\n const mean = (min + max) / 2;\n const gap = Math.random() < 0.3;\n const count = 1;\n if (!gap)\n result.push({\n i,\n entryI: i - startI,\n time: i * pw,\n min,\n max,\n mean,\n count\n });\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"levelsFromTop = 6","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"numTopPoints = 32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"res = 56 - levelsFromTop","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"aggRes = 56","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"points = genPoints(levelsFromTop, numTopPoints)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"aggregates = genAggregates(points, res, aggRes)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":274,"value":"snapshot = JSON.stringify({ points, aggregates, res, aggRes })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"levelPoints = [points, ...aggregates]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"sanityChecks = {\n const fail = html`

FAILED!

`;\n const pass = html`

PASSED!

`;\n for (let points of aggregates) {\n // make sure all the indexes are integers\n for (let p of points) {\n const valid = Number.isInteger(p.i) && Number.isInteger(p.entryI);\n if (!valid) return fail;\n }\n // make sure all the indexes/times strictly increase\n for (let i = 0; i < points.length - 1; i++) {\n const r = res + i + 1;\n const a = points[i];\n const b = points[i + 1];\n const valid = a.i < b.i && a.entryI < b.entryI && a.time < b.time;\n if (!valid) return fail;\n }\n }\n return pass;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"perfResults = {\n const n = 10;\n const t = {};\n const checkpoint = i => (t[i] = performance.now());\n\n checkpoint(0);\n let points = [];\n for (let i = 0; i < n; i++)\n points[i] = genPoints(levelsFromTop, numTopPoints);\n checkpoint(1);\n let aggs = [];\n for (let i = 0; i < n; i++) aggs[i] = genAggregates(points[i], res, aggRes);\n checkpoint(2);\n\n return {\n avgPointsTime: (t[1] - t[0]) / n,\n avgAggsTime: (t[2] - t[1]) / n,\n firstPoints: points[0],\n firstAggs: aggs[0]\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"viewof drawLevel = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"drawLevel","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"{\n const w = width;\n const h = 100;\n const ctx = DOM.context2d(w, h);\n const drawRes = res + drawLevel;\n const numPoints = numTopPoints * 2 ** (aggRes - drawRes);\n const pw = w / numPoints;\n const x = i => i * pw;\n const y = i => i * h;\n const drawPoints = levelPoints[drawLevel];\n const { canvas } = ctx;\n const present = {};\n for (const p of drawPoints) {\n present[p.entryI] = true;\n const minY = y(p.min);\n const maxY = y(p.max);\n const meanY = y(p.mean);\n const leftX = x(p.entryI);\n ctx.fillStyle = \"rgba(0,50,100,0.3)\";\n ctx.fillRect(leftX, minY, pw, maxY - minY);\n\n ctx.strokeStyle = \"rgb(0,50,100)\";\n ctx.beginPath(),\n ctx.moveTo(leftX, meanY),\n ctx.lineTo(leftX + pw, meanY),\n ctx.stroke();\n }\n // draw gaps\n for (let i = 0; i < numPoints; i++) {\n if (present[i]) continue;\n const leftX = x(i);\n ctx.fillStyle = \"rgba(255,0,0,0.3)\";\n ctx.fillRect(leftX, 0, pw, h);\n }\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"