On modern hardware the min-max heap beats a binary heap(probablydance.com) |
On modern hardware the min-max heap beats a binary heap(probablydance.com) |
(Like how linear search wins for small N, or insertion sort helps with small subarrays in introsort: more steps, but each step is also a lot cheaper on modern hardware due to fewer branch mispredictions, better cache locality, or something else that better fits the hardware's strengths.)
(And before anybody gets pedantic: technically, this is the node's "outdegree" when the tree is represented as a directed graph. If it was an undirected graph, we would have to count the parent node as well.)
Things not taught in CS that you need to know on the job are legion. By far the most important of these is the use of invariants. Second might be the memory hierarchy, and cache semantics. Third might be use of bitmaps and bitwise operations.
So, it's nice to see a detailed analysis of the structure like this! Perhaps if it becomes more popular, I will find more places to use it.
You don't need C++20. Even C++98 had std::bitset<>::count(), which has a nice conversion from unsigned long, and which, when compiled for SSE3 or better (e.g. Core2), uses a POPCNT instruction. It is pretty simple to produce various other results, including countl_zero, from a popcount, with just a couple of additional bitwise ops.
Modern compilers are happy to keep a bitset<32> in the same register as an unsigned long, so the conversion takes exactly zero cycles. POPCNT takes three cycles, and the extra bitwise ops another couple.
So in that case I would use this data structure even if it weren't faster. I can't count the number of times I have had to mess with inserting negative priorities into a min heap to create a max heap! We should just have one data structure that does both.
(though taking this idea to the logical extreme means we should just use Order Statistic Tree for everything since it not only gives you log(n) min/max, but also log(n) find kth and get rank of x)
Very useful when you need it!
https://en.wikipedia.org/wiki/D-ary_heap
(Also I didn't know they were called d-heaps, thanks!)
That was waaay at odds with the mindset of the STL, which seemed to me and I think a lot of folks like the state-of-the-art of containers at the time: with the STL if you prepend/insert much you need to use a deque/linked list, you decide pointer vs. value each time you declare a type, and if you want to know about the constant factor on an insert in the middle of the list you probably already lost.
(Qt has/had some other fun pragmatic things, like copy-on-write types in a lot of places. I didn't really do nearly enough with it to discover the pitfalls, but was fun to read.)
So I think about that, about how there are likely some trees out there that could just as well be sorted arrays, about adaptive structures that change their behavior based on dynamically observing how they're used (one recently discussed here: http://blog.erlang.org/the-new-scalable-ets-ordered_set/), even about tricks in in JS string implementations and VMs. I don't have answers, but I sometimes wonder if we should be thinking more in terms of tools that may not be perfect on all axes but soften or eliminate performance cliffs we take for granted. Not that the zero-overhead fine-tuned types are going away, just that they aren't the only imaginable approach.
I wonder if we'll see progress in those sort of imperfect-but-resilient tools over time. I think the long-run trend is towards some form of programming being accessible to more people more easily (like how, as you note, folks do real work in Python now). That certainly fits with trying to make your tools resilient to "misuse"--or, better, properly supporting more patterns so they're not even misuse. No conclusions, just hand-waving, but I do wonder if anyone working in software construction tools will eventually more usefully wave their hands in that direction :P
It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!!
The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I still wonder why this design lost to the std::deque we have in STL today.
[1] http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-repor...
V8's Array does different things depending on whether the array is sparse or packed and what data types it contains.
The real problem is if you need min/max at the same time. Then you not only need a min heap and max heap, you also need to track what was already popped from either heap! This is because in python you can't delete an element if it's not at the root. So tracking "tombstones" will let you pop from one heap, then know to ignore it the next time it comes up in the other heap.
This is of course super complicated to maintain and I get it wrong all the time. Luckily only shows up in algo interview problems.
Taking 27 milliseconds just to start the interpreter.
Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?
Anyway, just neat that it's been taken further than I realized!
[1] https://infoscience.epfl.ch/record/213452/files/rrbvector.pd...
What they do with strings is kind of neat, because if you do a lot of concats in a row (potentially an O(n^2) series of operations done the naïve way), they defer actually concatenating all the data until you try to get a character out or such (the string is just a "ConsString" pointing to the source strings): https://gist.github.com/mraleph/3397008
It's also impressive how much dynamic instrumentation they can do. Beyond finding hot code and guessing types, they're even e.g. using it to guess which garbage will be long-lived (for "pretenuring" to avoid needing to copy it).
There's a limit to how much clever stuff you can do implicitly since you don't want to impose big costs for code that's doing everything right; something like QList isn't that adventurous but it's also clearly wrong when you want to compactly store a bunch of small structs in memory. And like the linked post on V8's thing notes, when you patch over a problem in one specific case the 'fix' can be fragile. Still, interesting area.
They are right that invariants will not be essential for your assignments, at least for the first couple of years, although they would save you from some dead ends.
You will be able to code some of your invariants as assertions, but as often not. The ones you can't are the ones you have to pay the most attention to.
If the system invariants get too complicated, or hard to express, the design is wrong--reliably. That is when they are most valuable. Millions of systems designed without invariants could have been right, but we're stuck with what we got, instead.
(setting the key function with "key=lambda x: -x" is really easy and works just like changing a comparator function in other languages so I dunno why you guys are talking about it)
BST supports log(n) min/max/inserts/removes (among other stuff).