I am just curious: what is your use case? If you look in my luerl system, https://github.com/rvirding/luerl, you will see a module ttdict.erl which uses 2-3 trees. These are basically the same as red-black trees. Well, actually, rb trees are sort 2-3 trees but only using binary nodes. I have not done any serious speed comparison but my guess is they should be about as fast s rb trees. An easy way to handle the slowness of size would be to carry around an explicit size field. the 2-3 trees and rb trees have the same interface as dict.
For fun I also implemented aa trees and sets, which Arne Andersson trees. Data structures are fun. Robert P.S. I use 23-trees in luerl as maps are missing one very important function needed for implementing Lua and that is to be able to efficiently step through a tree. I need a 'first' function which returns the first key-value pair and then a 'next' which returns the next pair after a given key. Order is unimportant but I need guarantees that I will see all pairs. On Sunday, 28 May 2017 09:19:59 UTC+2, Ricky Han wrote: > > Hi José, > > I posted an update on the benchmark here [1]. > > [1] https://github.com/elixir-lang/elixir/issues/6161 > > Best, > Ricky > > On Wednesday, May 24, 2017 at 7:20:58 AM UTC-4, José Valim wrote: >> >> Thanks for the proposal Ricky Han! >> >> It is also worth mentioning the red black trees library from Robert >> Virding: https://github.com/rvirding/rb >> >> While having a library is already great for the ecosystem, we can >> consider this being added as part of Elixir given Elixir doesn't have an >> indexed data structure besides tuples (which are expensive to transform). >> >> However, there is a lot of work to do before we are able to fully >> evaluate it: >> >> 1. As you said, it needs documentation. You mention the 1990 look and >> feel from the Erlang libraries but they are at least *documented* >> >> 2. We need to validate the claims it is fast and space efficient. Have >> you benchmarked it against gb_trees and gb_sets and measured >> insertion/retrieval/deletion times as well as memory usage? For example, >> your implementation uses maps for nodes and using tuples will likely be >> much more efficient >> >> The core team has discussed adding indexed data structures multiple times >> in the past but we haven't found something that feels right. >> >> >> >> >> *José Valim* >> www.plataformatec.com.br >> Skype: jv.ptec >> Founder and Director of R&D >> >> On Wed, May 24, 2017 at 11:10 AM, Ricky Han <ricky...@gmail.com> wrote: >> >>> The most important data structure elixir is missing - *sorted, ordered >>> sets and maps*. Say what? Elixir only has non-ordered sets. The >>> default(recommended) map is HashMap whereas Haskell Data.Map is backed by >>> binary tree. JVM, stdlib, .NET are treemaps too. This is strange because >>> there is 0 penalty for functional language to use trees.(sidenode: Redis >>> uses skip lists which is bad for immutability). >>> >>> These are actually several solutions out there: >>> >>> :orddict, :ordset, :gb_sets, :gb_trees >>> >>> :orddict and :ordset are very bad as they are backed by lists and have >>> linear time complexity. >>> >>> :gb_sets and :gb_trees are performant because they are backed by AA >>> trees. However, annoyingly they don't track size of subtrees which means >>> can't be indexed unless converted to list(expensive). >>> >>> Here is why this would be better than all the existing solutions and >>> should be integrated into elixir stdlib. >>> >>> 1. Being able to index keys means we can it can replace Redis sorted set >>> completely. With ZRANK, ZRANGE abilities >>> 2. All the other languages have it >>> 3. Proves to be fast and space efficient >>> 4. First class citizen so no need to use inferior Erlang library with >>> limited functionalities and 1990s documentation >>> >>> I find sorted sets and maps very useful in other languages(especially >>> ruby). So like a good hacker I ported red black tree from Haskell[1] >>> Currently, both data structures are functional but documentations are few >>> and far between. >>> >>> [1] https://github.com/rickyhan/rbtree >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "elixir-lang-core" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to elixir-lang-co...@googlegroups.com. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/elixir-lang-core/5b22966b-3f82-4446-b494-ec06d892991c%40googlegroups.com >>> >>> <https://groups.google.com/d/msgid/elixir-lang-core/5b22966b-3f82-4446-b494-ec06d892991c%40googlegroups.com?utm_medium=email&utm_source=footer> >>> . >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- You received this message because you are subscribed to the Google Groups "elixir-lang-core" group. To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/5fc60283-ea2e-4c71-8c55-c75b6217d6ef%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
