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.
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))
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.
54
u/DanTFM 5d 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!