News for hackers. Stuff that matters.

rtheunissen

Re:Relaxed Radix Balanced Trees on Wednesday February 19, 2025 @03:57PM (#43107563)
I would love to add a good RRB implementation to the persistent benchmarks at [1] to get a state-of-the-art comparison between RRB and BST in a persistent context. Duration, of course, but also number of bytes copied etc.

https://rtheunissen.github.io/bst

Re:Ask HN: How did you learn Regex? on Thursday August 08, 2024 @04:18PM (#41195749)
Practice, the more you use them the easier they become. I never studied them but knew when to use them, then just tinkered and iterated until the pattern did what I needed it to. After a while you can mostly just write and read them without much tinkering.

Regex101 is an excellent tool.

Learning a lot here, thank you.
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 support randomized balancing and self-adjusting strategies like splay trees.

I am disappointed to still see frequent mention of red-black trees – I see no reason for red-black trees to ever be the best choice in practice, or in theory, or in school. LBST's (logarithmic binary search trees) [1] are generally simpler, more intuitive, and more efficient [2] than red-black trees. They also support positional access inherently, so the balancing information is useful (subtree size).

[1] https://www.semanticscholar.org/paper/A-New-Method-for-Balan... [2] https://rtheunissen.github.io/bst

Re:Is there an algorithm as beautiful as a poem? on Sunday June 16, 2024 @07:07PM (#40700853)
I love the various top-down binary search tree partition/split/join algorithms.

https://github.com/rtheunissen/bst/blob/main/trees%2Fbalance...

Zip trees are novel but their performance (and therefore also skip lists, since they are isomorphic) lacks behind other linked structures like Treaps and especially LBSTs. [1] I personally find skip lists to be overhyped binary search trees in disguise.

[1] https://rtheunissen.github.io/bst

Re:Go Run on Wednesday February 21, 2024 @07:48PM (#39461687)
Maybe it is because the simple way requires knowledge of packages, which are covered later perhaps, since many tutorials go straight to "go run helloworld.go"
Re:Show HN: Aviation Navigation Log on $20 Receipt Printer on Saturday August 19, 2023 @03:26PM (#37192215)
Might be a CMS of some kind because I doubt anyone would purposefully type out "alt text".
Re:Exploring the design space of binary search trees on Thursday August 17, 2023 @03:44PM (#37166935)
That was how I received your feedback. :)

My inclination towards lower abstraction in this project is entirely for the sake of reading and reference, to minimize the need for the reader to re-compose from various components split across files.

During development, abstraction helps because it makes prototyping faster and more consistent, but once everything is mostly "done", it can help the reader/student to maximize local reasoning.

Another comment mentioned they found it difficult to find the LBST implementation - this is exactly the sort of experience I hope to avoid.

Re:Exploring the design space of binary search trees on Thursday August 17, 2023 @01:56PM (#37165579)
Thank you for sharing this resource, I was not aware of it. I am happy to see the inclusion of LBSTs there too.

Re: binary symmetry, if I'm understanding correctly, another author that makes use of the symmetry is Ben Pfaff in libavl [1]. At the top of [2], which seems a bit misplaced now, I wrote:

>A choice was made to not unify the symmetric cases using the direction-based technique of Ben Pfaff and others because it makes the logic more difficult to follow even though there would be less code overall.

The choice of Go was to provide implementations that are both reliable to benchmark (though not as robust as C or Rust for example) but also easy to read. I would like to further reduce abstraction by decomposing common parts such that all the strategies are "one-file" references. This is then effectively the opposite of what the macro-based implementation achieves. Both have value, of course.

[1] https://adtinfo.org/libavl.html/BST-Node-Structure.html

[2] https://github.com/rtheunissen/bst/blob/main/trees/avl_botto...

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @10:01PM (#37156250)
I was inspired by Stick & Rudder, which is a very easy book to recommend to most people in this community. I'm sure I'll keep coming back to make adjustments, but the end result is what I hoped to achieve.

The Charter font was a particularly good find as part of the "transitional" system font stack. I'll definitely use it for other projects in the future.

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @09:55PM (#37156216)
Haha true, that's a good point. There's also WAVL and RAVL for weak AVL and relaxed AVL, but no equivalent acronyms for the red-black variants. RRB is the same as Relaxed Radix-Balanced! In my notes I found it easier to avoid acronyms, and then "logarithmic binary search tree" became ambiguous because "aren't they all logarithmic (in height and complexity)?" I found that grouping them as part of the weight-balanced class of trees is the most intuitive, and I wish the original paper did the same, but that's okay.

What I'll do for now is mention specifically that the literature refer to them as LBSTs, and I'll add an index to each tree in the repository to make them easier to navigate. Thanks again.

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @07:27PM (#37155231)
Part 2 defines that "a node is logarithmically weight-balanced if the binary log of the weights of its subtrees differ by no more than 1" and references Roura directly there. Roura uses the acronym LBST, which corresponds to the file trees/lbst.go in the repository. I hoped that this would be intuitive enough to follow.

They are definitely part of the class of weight-balanced trees, using the exact same algorithms as BB[a] trees, which are the classic weight-balanced trees.

When I started this project, it was unclear that the conclusion would advocate for them. In fact, I did not even know about them when I started. My intention was to focus on the exploration more than the conclusion. I'm in the process of writing another conclusion around relaxed balance as a concept, which could just as well be the title.

I appreciate this feedback very much. Perhaps the paper could mention specifically that Roura and Frias call the logarithmic binary search trees, abbreviated as LBST. The repository's README could also provide an index to each tree in the source.

For reference: the weight-balanced algorithms can be found in [1], [2] and [3]. The logarithmic weight-balance rules are defined in [4].

[1] https://github.com/rtheunissen/bst/blob/main/trees/wbst_bott...

[2] https://github.com/rtheunissen/bst/blob/main/trees/wbst_topd...

[3] https://github.com/rtheunissen/bst/blob/main/trees/wbst_rela...

[4] https://github.com/rtheunissen/bst/blob/main/trees/lbst.go

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @01:56PM (#37150957)
What if some future technology or material breakthrough provides a sort of self-adjusting liquid memory that provides true constant time access to any address? I'm not being entirely serious of course, as I dream about sequences across nodes on planets through other solar systems.

Focusing on fundamental algorithms in the abstract provides a fun playground to explore and learn and teach, before you learn about memory hierarchy when all your hopes and dreams of the ideal data structure fades away.

I don't think there is any time wasted exploring the fundamental. Who knows what technology might see renaissance in the future as hardware continues to change. Analog computers, binary search trees, who knows.

It's fun to dream and take a break from reality sometimes, digging deep into a simple concept with a rich design space and complex analysis.

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @05:45AM (#37144751)
This has now been fixed, thank you for reminding me.
Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @05:42AM (#37144729)
You are correct, they have not been covered yet. I've added a note in the "work in progress" section.

There are also LLRB trees that would be interesting to see compared within this framework. All the red-black trees are implemented as rank-balanced trees, so there is no concept of "color" exactly, but the authors do mention the left-leaning 2-3 rule and the left-leaning red-black rule -- I just haven't implemented those yet.

See Pg. 5 of https://citeseerx.ist.psu.edu/document?type=pdf&doi=52330eed...

Re:Exploring the design space of binary search trees on Wednesday August 16, 2023 @02:39AM (#37143545)
This is tragic! Supporting noscript was a primary design goal but I forgot to only enable the knuth/plass justification in print media. The math expressions I'm moving to build time now. So sorry.
Re:Exploring the design space of binary search trees on Tuesday August 15, 2023 @11:55PM (#37142687)
I believe yes, as illustrated in [1]. This idea only works in a static sense, because to insert a value suffers from the same linear movement of memory as dynamic arrays. B-trees are somewhere in-between because they support logarithmic insert/split/join and make better use of cache than BSTs, a well known fact.

I tried to focus specifically on BSTs in the context of online persistence and concurrency, where they are particularly effective at very large sizes. There is a section on the paper that mentions B-trees but I did not want to include a direct comparison as part of the scope. Take the best candidate from this set, and compare against a good B-tree implementation in whatever situation you might require them.

[1] https://algorithmica.org/en/eytzinger

Re:Exploring the design space of binary search trees on Tuesday August 15, 2023 @01:56AM (#37130697)
That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases by moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all.

Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer look. In a hypothetical future, our hardware might be so different and caches so large and advanced that the best practices of today might not apply all the same.

Binary search trees today are probably only viable for absolutely massive collections, and at that scale there is almost definitely a better, bespoke solution available. Exploring without necessarily thinking about the hardware, in the abstract, has been a fun sandbox to play in. The fact that we still teach them suggests that they provide value beyond practical application.

Thank you for your feedback, you are absolutely right. In most cases today, a B-tree would achieve better results in real use cases on real hardware.

Re:You can't stop the business, or why rewrites fail on Thursday July 20, 2023 @01:25AM (#36797139)
That is the organization.
Experiment with monitor brightness.

My phone is always on low brightness at night, but for some reason my monitor is always at 100% without question, which means light theme during the day (to match paper/pencil in front of me) and dark theme at night because it is otherwise too much light. Then one day, I tried a light theme at night at 50% monitor brightness and my eyes relaxed immediately. I realized that I have been squinting constantly to brace against the maximum brightness.

The usual advice is to instead increase ambient/room light but I have the room light set perfectly for writing and reading on paper.

I'll write some tests for this.
I moved to ULID because they are always lowercase and therefore case-insensitive.
Re:Exposing Floating Point on Monday June 26, 2023 @06:11PM (#36486575)
You can view the source on the page, it's all there.
Re:Never trust a programmer who says they know C++ on Monday June 05, 2023 @05:51AM (#36194275)
A very consistent codebase makes it possible to do things like this, using automatic refactoring and very smart find/replace, but such codebases are few and far between.

Older »