Software engineer and visualization enthusiast. Lives in Cambridge, Massachusetts, with no dogs.
Unlisted
Edited
May 24, 2023
N = 20_000 // universe size
1
function estimate(N, n) {
// compute stats about the EF representation for n elements from universe size N
const info = stats(N, n);
// compute the size and number of the high bit blocks
const blockSize = 2 ** info.loBits;
const numBlocks = Math.ceil(N / blockSize);
// generate a random sequence with approximately n values in [0, N)
const values = generateValues(N, n);
// group them by high bit block and count the number of elements
const lengthPerBlock = d3.rollup(
values,
(g) => g.length,
(d) => d >>> info.loBits
);
// compute the expected number of elements accessed for linear search
const linear =
d3.sum(lengthPerBlock.values(), (k) => (k + 1) / 2) / numBlocks;
// compute the expected number of elements accessed for log (binary) search
const log =
d3.sum(lengthPerBlock.values(), (k) => Math.log2(k) + 1 / (k + 1)) /
numBlocks;
return {
values,
linear,
log,
lengthPerBlock,
info,
numBlocks,
blockSize,
info
};
}
values = est.values
r = d3.range(N / 100, N + 1, N / 100)
linear = est.linear
log = est.log
data = r.map((n) => estimate(N, n))
info = est.info
est = (regenerate, estimate(N, n))
sim = {
// count the number of elements probed for random arrays of length 2**power
let count = 0;
let iters = 10_000;
let power = 4;
const xs = new Array(2 ** power);
for (let i = 0; i < iters; i++) {
// randomize the array
for (let j = 0; j < xs.length; j++) xs[j] = Math.random();
// search for a random element and accumulate the number of accesses
binarySearchAfterAccess(
(i) => (count++, xs[i]),
Math.random(),
0,
xs.length
);
}
// return the number of accesses per binary search
return count / iters;
}
nReal = values.length
percent = d3.format(".2%")
bpeFormat = d3.format(".2f")
comma = d3.format(",.2f")
icomma = d3.format(",")
lengthPerBlock = est.lengthPerBlock
blockLengthDistribution = {
const m = d3.rollup(
est.lengthPerBlock.values(),
(g) => g.length,
(d) => d
);
m.set(0, est.numBlocks - est.lengthPerBlock.size);
return m;
}
blockSize = est.blockSize
numBlocks = est.numBlocks
generateValues = (N, n) => {
let sample = new Uint32Array(2 * N);
let prob = n / N;
let count = 0;
for (let i = 0; i < N; i++) if (Math.random() < prob) sample[count++] = i;
return sample.slice(0, count);
}
stats(1e6, 1e4)
10000 / 2 ** 14
import { stats } from "70f2503017f350a5"
import { Plot } from "@observablehq/plot-0-6-7"
import { binarySearchAfterAccess } from "@yurivish/bitvectors-with-runs-3"
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.
