71–78 of 78 posts
Earlier quoted context omitted.
Red-black trees use to make me anxious. I think the first time I grasped them was after watching Erik Demaine's lecture on the topic. For anyone interested it is this [1]; its still a very good reference on the topic! [1] https://videolectures.net/mit6046jf05_demaine_lec10/
RB trees still make me anxious which is why I use AA trees instead https://en.wikipedia.org/wiki/AA_tree
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
I would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set
Earlier quoted context omitted.
I mean it's kind of pedantic but yes hash maps do have guaranteed performance characteristics. They are not guaranteed to be O(1), but they will never be something like O(2^N) either. You can give guarantees about their performance if you can make guarantees about the distribution of the inputs and the properties of the hash used. In my own experience, most uses of hash maps are typically O(logn). A good rule of thum…
> A good rule of thumb is hash maps are preferable unless you need predictable worst case performance or your hash maps are directly exposed to the public. Also, obviously, features only one of them provides e.g. if you need range queries then a hash table is quite useless. Meanwhile if you need insertion ordering, that’s reasonably easy to do with a hashmap.
Yes, you can throw the nodes on an array in the heap to allow tail recursion, but at that point you're going to be losing to a map with all but the biggest datasets, and even then the copies really aren't desirable
That does not mean that b-trees are unequivocally better than binary search trees. There are some applications, like concurrency or persistence, where comparison count is not as important. For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time. The binary structure also makes it possible to…
> For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time. But this also assumes single-threaded computation. Increasingly, high-performance computers are SIMD-compute (aka: GPUs, and if not, at a minimum you're using AVX512 or ARM SVE). If you have 1024-threads per thread group (common maxi…
Earlier quoted context omitted.
May I ask why you regret it? It could be that my professors were simply not that good, so that I don't really understand this. I mostly groked the subjects by working through the books and exercises in them. The professors' lectures almost always went over some detail too quickly, so in a 3 hour lecture, I usually ended up following only the first hour or so. My question is maybe better put as: what quality or approa…
Having a class in databases from the person who was the DeWitt Clause in Oracle licenses. I had his class before (the aforementioned sophomore data structures and algorithms) and I knew he was a good lecturer. That wasn't a question. It was a "too much going on that semester and I wasn't able to do the assignments in a timely manner". Professor Landweber's class had a waiting list that I scoffed at as a college stude…
Earlier quoted context omitted.
I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data. If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger b…
Just because it was first discovered 15 years ago, does not mean it wasn't still a good idea. Keep on thinking. You never know what else you will come up with.
A lot of string comparisons use SIMD now. In C++ if you use std:string on GCCit has done it for years. I bet Rust and Python (in the compiled runtime) ate doing it too.
No sense leaving easy performance gains on the table.
B-Tree are a good fit if your values are small, but as the value size grows, they lose their advantage. Binary tree is a good default choice for sorted structure. Underappreciated structure: sorted arrays (but come with big caveats).
B-tree also enjoys a *massive* advantage when your access block size can hold many keys. With big data this will always win.
Earlier quoted context omitted.
I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data. If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger b…
Like the article, I'm only concerned with comparison counts, trying to explain why B-trees look like balanced BSTs, and why that gets tighter and tighter with increasing numbers of children per node. It's simply because the nodes themselves contain the equivalent of a balanced binary tree, in the form of a binary-searched array. In the ultimate case, we set the number of children to be large enough to contain all the…
So for practical sizes of M, as in a few cache lines, and sufficiently large datasets of size N a binary tree will eliminate 1/2 of data each node checked and a B tree with M set to 8 would skip 7/8ths of the data each node. When not descending nodes they are both in Log2(N) time, but when jumping nodes this hypothetical B-Tree is using Log8(N) time.
So yeah if the N and M are close then they are similar, but those aren't interesting cases. Datasets that small are fast to iterate even if unsorted, and large unwieldy values of M are silly and impractical. Once you have thousands or millions of items in N then the savings of eliminating downtree data from checked at all becomes real. Or put another way binary trees are always averaging Log2(N) amount of checks but B trees have some mix of Log2(N)+LogM(N) amount of checks which should be lower in most cases and so close in edge cases as to not matter.
But again, I state that counting comparisons is silly. On any modern hardware (past 20 years) load time dominates the comparison time and B-Trees will just have fewer loads, memory complexity is the "interesting" part of this problem unless you are a C64 or some zany future company with hyper fast RAM.