[erlang-bugs] Bug in gb_trees ? Integer key not found.

[Robert Virding]

Dict/orddict have a from_list/1 which takes a list of Key-Value tuples in any order. They also accept non-unique keys taking the value of the last key in the list.

Robert

----- "Matthias Lang" <matthias@REDACTED> wrote:

> On Monday, May 09, Ulf Wiger wrote:
> > 
> > On 9 May 2011, at 22:01, PAILLEAU Eric wrote:
> > 
> > >> T=gb_trees:from_orddict([{10,a1},{15,a2},{5,a3},{7,a4}]).
> > > {4,{5,a3,{15,a2,{10,a1,nil,nil},nil},{7,a4,nil,nil}}}
> > > 
> > >> gb_trees:lookup(10,T).
> > > none
> 
> > The argument is not an orddict.
> 
> The above was the important part of your mail, but this made me
> wonder:
> 
> > The reason for the function is speed, obviously, and verifying that
> > the list is in fact ordered would defeat the speed advantage.
> 
> Checking that the input is ordered should be cheap since you have to
> traverse the whole input anyway. Here's gb_trees:from_orddict:
> 
>   from_orddict(L) ->
>     S = length(L),
>     {S, balance_list(L, S)}.
> 
> replacing the length() call with one which also checks input ordering
> is easy, so I did that. I measured a 5% slowdown on long (1M)
> lists. I'd live with that, but maybe not everyone would.
> 
> I then took a look at "who uses gb_trees:from_orddict anyway?". In
> OTP, it's mostly the beam compiler itself. This code pops up a few
> times:
> 
>   gb_trees:from_orddict(lists:sort(L))
> 
> It feels like there's a function missing in gb_trees, one which
> inserts a
> list of tuples which aren't sorted (but do have unique keys).
> 
> Matt
> _______________________________________________
> erlang-bugs mailing list
> erlang-bugs@REDACTED
> http://erlang.org/mailman/listinfo/erlang-bugs