Earlier quoted context omitted.
It's the number of children each node can have
Maybe they're asking why the letter "d". That is, why "d-ary" instead of "n-ary" or "k-ary".
Yes, that was my intent. Why the choice of the letter "d".
On modern hardware the min-max heap beats a binary heap
31–40 of 44 posts
Re: On modern hardware the min-max heap beats a binary heap
#32Wow. This is a very good analysis on a fundamental algorithm. Haven’t seen a high quality analysis like this for a good while.
Re: On modern hardware the min-max heap beats a binary heap
#33I've been using the author's flat_hash_map (https://github.com/skarupke/flat_hash_map) for several years now and have been really impressed. I've yet to find a single bug, it's nearly as fast as folly's hash maps (for my use case anyway) but far easier to integrate than folly.
Re: On modern hardware the min-max heap beats a binary heap
#34> "...C++20 finally added a way of accessing this instruction, using std::countl_zero. I don’t have C++20 though so I had to do it the old platform specific ways ..."
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 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.
Re: On modern hardware the min-max heap beats a binary heap
#35Like folks mentioned there, I wonder if a higher-fanout heap (people asked about 4-ary) might also do well in practice. Looking at Wikipedia ( https://en.wikipedia.org/wiki/D-ary_heap ), it looks like maybe so -- the growth in number of comparisons isn't that bad, and it mentions 4-ary heaps working well specifically. (Like how linear search wins for small N, or insertion sort helps with small subarrays in introsort:…
I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?
There are only two important things taught in CS that most people don't seem to pick up on the job. The most important is order notation. The second is the relation between grammars and state machines. Both are worth as much attention as you can afford for a week.
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.
Re: On modern hardware the min-max heap beats a binary heap
#36Earlier quoted context omitted.
So, kind of a non sequitur, but I occasionally think about Qt's QList . When introduced, it was odd for reserving space at the beginning as well as the end, so you had constant-time inserts/removals at the beginning. That and storing pointers for any T larger than a pointer also reduced the constant factor on insertion/deletions from the middle. Since it was always stored as a list of pointer-sized items, some code c…
Along the lines of adaptive structures that change depending on how they're used, I thought this article about how JavaScript arrays work in V8 was interesting: https://ryanpeden.com/how-do-javascript-arrays-work-under-th... V8's Array does different things depending on whether the array is sparse or packed and what data types it contains.
Yeah--JS seems to allow enough weird stuff with arrays that fast paths for when things aren't weird seem inevitable. I admit when I clicked I still found V8 had more implementations than I expected, haha.
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.
Re: On modern hardware the min-max heap beats a binary heap
#37Like folks mentioned there, I wonder if a higher-fanout heap (people asked about 4-ary) might also do well in practice. Looking at Wikipedia ( https://en.wikipedia.org/wiki/D-ary_heap ), it looks like maybe so -- the growth in number of comparisons isn't that bad, and it mentions 4-ary heaps working well specifically. (Like how linear search wins for small N, or insertion sort helps with small subarrays in introsort:…
For very large heaps, I have had speedups of about 3x due to better cache locality with B-heaps.
Re: On modern hardware the min-max heap beats a binary heap
#38Earlier quoted context omitted.
Not in python! But I guess using negatives is the same as using different key (which is what python uses instead of comparators). 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 po…
Sounds like python is not batteries included compared to other languages in this regard!
Do any languages give you min/max at the same time with their standard library data structures?
(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)
Re: On modern hardware the min-max heap beats a binary heap
#39Earlier quoted context omitted.
I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?
There are only two important things taught in CS that most people don't seem to pick up on the job. The most important is order notation. The second is the relation between grammars and state machines. Both are worth as much attention as you can afford for a week. 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 memor…
I'm learning about invariants in a relatively introductory cs course and I've been told they end up being relatively useless in actual practice. When have you found them useful?
Re: On modern hardware the min-max heap beats a binary heap
#40In certain domains, the trend has been to give up constant factors in order to increase programmer productivity (e.g., python pays a 10x slowdown but is batteries included). 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 d…
So, kind of a non sequitur, but I occasionally think about Qt's QList . When introduced, it was odd for reserving space at the beginning as well as the end, so you had constant-time inserts/removals at the beginning. That and storing pointers for any T larger than a pointer also reduced the constant factor on insertion/deletions from the middle. Since it was always stored as a list of pointer-sized items, some code c…
If you haven't already seen it, you'd probably really enjoy Chandler Carruth's "Efficiency with Algorithms, Performance with Data Structures" talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs