5 ms·
Right, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers). I would hate to have to
by kabdib 4y ago
Right, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers).
I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).
- dilap 4y agosimple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often. another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses. (well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.) just curious, do you think that solution would have worked for your situation too?
- kabdib 4y agoThat's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over. You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
- dilap 4y agoAh thanks, I didn't read closely enough the first time.
- samsquire 4y agoFor a simple and readable implementation of a Python btree see this: https://github.com/samsquire/btree https://github.com/samsquire/btree I tried to keep the implementation as simple as I could.