Software engineer and visualization enthusiast. Lives in Cambridge, Massachusetts, with no dogs.
Unlisted
Edited
Oct 3, 2023
function binomial(n, k) {
let C = [1];
for (let i = 0; i < k; ++i) {
C[i + 1] = (C[i] * (n - i)) / (i + 1);
}
return C[k];
}
Plot.dot([[10, 20]], { symbol: "star", fill: "#000" }).plot()
// place n objects into k bins
// (theorem 2: https://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29#Theorem_two)
numSortedMultisets = (n, k) => binomial(n + k - 1, k - 1)
viewof u = Inputs.range([0, 100], { label: "Universe", step: 1, value: 30 })
viewof n = Inputs.range([1, 150], {
label: "Number of elements",
step: 1,
value: 30
})
numEFSequences(n, u)
log2(binomial(u + n, n)) / n
(u + n) / n
log2((u + n) / n)
log2((u + n) / n)
optimalNumBitsPerElement = Math.log2(numEFSequences(n, u)) / n
efBitsPerElement = (n + numHi + lo) / n
numEFSequences = (n, u) => numSortedMultisets(n, u + 1)
numEFSequences(2, 2)
lo = Math.max(0, Math.floor(Math.log2(u / n)))
// number of bits represented explicitly in the top part
hi = Math.ceil(Math.log2(u)) - lo
numHi = u >>> lo
sz = 2 ** 6
vals = d3.range(1, sz + 1)
data = d3.cross(vals, vals, totalBits)
ceil = Math.ceil
log2 = Math.log2
// bpe = (n, u, lowBits) => (n + (u >>> lowBits) + n * lowBits) / n
bpe = (n, u, lowBits) => 1 + lowBits + (u >>> lowBits) / n
totalBits = (n, u) => {
console.assert(n > 0 && u > 0);
const nBits = Math.ceil(Math.log2(n));
const uBits = Math.ceil(Math.log2(u));
// Math.max(0, uBits - nBits);
const loBitsPerElement = Math.max(0, Math.floor(Math.log2(u / n)));
const hiBitsPerElement = uBits - loBitsPerElement;
return {
u,
n,
nBits,
uBits,
loBitsPerElement,
hiBitsPerElement,
bpe: bpe(n, u, loBitsPerElement),
bits: Math.round(n * bpe(n, u, loBitsPerElement))
};
}
// todo: is Math.floor(Math.log2(u / n)) the same as floor of int divide u/n?
Math.max(0, Math.floor(Math.log2(u / n)))
lobs = Math.floor(Math.log2(Math.max(1, Math.floor(u / n))))
bpe(n, u, lobs)
d3
.cross(vals, vals, (u, n) => [
u,
n,
Math.max(0, Math.floor(Math.log2(u / n))) !==
Math.max(0, Math.floor(Math.log2(Math.floor(u / n))))
])
.filter((d) => d[2])
Plot.plot({
marks: [
Plot.cell(data, {
x: "u",
y: "n",
fill: (d) => {
// return d.u < d.n || d.n > d.u >>> d.candidate;
let r = d3.range(0, d.uBits + 1);
let i = d3.minIndex(r, (lo) => bpe(d.n, d.u, lo));
const best = bpe(d.n, d.u, r[i]);
const baseline = d.bpe;
return baseline - best > 1e-3;
},
title: JSON.stringify,
inset: 0.25
})
],
aspectRatio: 1,
padding: 0,
y: {
ticks: d3.range(sz + 1).map((d) => 2 ** d),
label: "Number of elements",
reverse: true
},
x: { ticks: d3.range(sz + 1).map((d) => 2 ** d), label: "Universe size" },
color: { scheme: "blues", reverse: true, legend: true }
})
data[0]
data.filter((d) => !d.loBitsPerElement)
data[1000]
Plot.plot({
marks: [
Plot.cell(data, {
x: "u",
y: "n",
fill: "bpe",
// fill: (d) => (d.bpe - d.loBitsPerElement) / 2,
fill: (d) => {
let claim = 2 + Math.max(0, Math.log2(d.u / d.n));
let actual = d.bpe;
return actual - claim;
},
title: (d) => {
let claim = 2 + Math.max(0, Math.log2(d.u / d.n));
let actual = d.bpe;
return JSON.stringify({ claim, actual });
},
// // title: (d) => (d.bpe - d.loBitsPerElement) / 2,
// title: (d) => JSON.stringify(d),
// fill: (d) => d.bpe || 10,
inset: -0.25
// title: (d) =>
// `${d.n} elements from the universe [0, ${d.u}] take ${
// d.bits
// } bits to encode (${fmt(d.bpe)} bits per element)`
})
],
width,
height: 600,
padding: 0,
y: {
ticks: d3.range(sz + 1).map((d) => 2 ** d),
label: "Number of elements",
reverse: true
},
x: { ticks: d3.range(sz + 1).map((d) => 2 ** d), label: "Universe size" },
color: {
type: "diverging",
xscheme: "reds",
legend: true,
label: "Bits per element"
}
})
Plot.plot({
marks: [
Plot.cell(data, {
x: "u",
y: "n",
fill: (d) => d.bpe * d.n, //"bpe",
title: (d) => d.bpe * d.n, //"bpe",
inset: -0.25
})
],
width,
height: 600,
padding: 0,
y: {
ticks: d3.range(sz + 1).map((d) => 2 ** d),
label: "Number of elements",
reverse: true
},
x: { ticks: d3.range(sz + 1).map((d) => 2 ** d), label: "Universe size" },
color: {
scheme: "reds",
legend: true,
label: "Bits per element"
}
})
fmt = d3.format("0.2f")
findLastSet(1)
findLastSet = (x) => 1 + Math.floor(Math.log2(x)) // for x > 0
import { Plot } from "@mkfreeman/plot-tooltip"
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
