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 <[email protected] > <javascript:>> 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 [email protected] <javascript:>. >> 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/d51c1797-72dd-4593-bbe4-db14b382d4ef%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
