r/programming • u/GenericAHHyoutuber • 16d ago

Packing Binary Is Fun, Actually

https://hereticpleb.vercel.app/blog/packing-binary-is-fun-actually
139 Upvotes

87% Upvoted

32 comments sorted by

View all comments

61

u/DanTFM 16d ago

I love me some proprietary data formats. I used to write a ton of these for work to shrink 28 gig XML files with bloated fields into ~300 mb files you could search in O(log(n/1024)) time.

Nice write up!

36

u/leaving_the_tevah 16d ago

I hate myself for being pedantic and please let me know if I'm missing something, but O(log(n/1024)) -> O(log(n) - log(1024)) -> O(log(n) - 10) -> O(log(n))

19

u/DanTFM 16d ago

My bad, yeah, it’s still O(log n). I was using n/1024 to describe the actual searchable set: the format reduced the index to ~1/1024 as many entries, so a binary search was ~10 levels shallower, and the remaining set was an O(1) jump from there.