Maps:to_list/1 element order.

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Maps:to_list/1 element order.

Valentin Micic-6
Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

Types

Map = map()
Key = Value = term()


Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:


(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).  
[{1,"Last entered"},
 {42,value_three},
 {1337,"value two"},
 {"a",1}]



When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:


(x@MacBook-Pro)48> 
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
 {1,"Last entered"},
 {42,value_three},
 {"a",1}]


Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

Thanks in advance

V/

Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Jesper Louis Andersen-2
No, and it is subtle:

L1 = [{X, X} || X <- lists:seq(1,32)].
L1 == maps:to_list(maps:from_list(L1)).
true

L2 = [{X, X} || X <- lists:seq(1,33)].
L2 == maps:to_list(maps:from_list(L2)).
false

At 32+ elements, Maps change their representation order to a hash array mapped trie. These are not generally ordered, but provide very fast lookups. In practice you are O(1) bound with a couple of memory reads. In theory you are O(lg n) bound width a branch factor of 32.

If you need the order, you need to use a representation which maintains the order.

On Fri, Feb 28, 2020 at 10:45 AM Valentin Micic <[hidden email]> wrote:
Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

Types

Map = map()
Key = Value = term()


Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:


(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).  
[{1,"Last entered"},
 {42,value_three},
 {1337,"value two"},
 {"a",1}]



When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:


(x@MacBook-Pro)48> 
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
 {1,"Last entered"},
 {42,value_three},
 {"a",1}]


Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

Thanks in advance

V/



--
J.
Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Ulf Wiger-2
In reply to this post by Valentin Micic-6
This was discussed at length in a previous thread:

http://erlang.org/pipermail/erlang-questions/2017-October/093981.html

The short answer is "no", you can't rely on the order, and this should
perhaps be more clearly documented. In the future, it might be nice
with some 'canonical' option to e.g. term_to_binary/2, to ensure that
encoding is consistent. This would of course come at a cost.

BR,
Ulf W

Den fre 28 feb. 2020 kl 10:45 skrev Valentin Micic <[hidden email]>:

>
> Hi
>
> Even though documentation indicates that:
>
> to_list(Map) -> [{Key, Value}]
>
> Types
>
> Map = map()
> Key = Value = term()
>
>
> Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.
>
> It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
> I did some testing using a bit modified example offered in documentation:
>
>
> (x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> [{1,"Last entered"},
>  {42,value_three},
>  {1337,"value two"},
>  {"a",1}]
>
>
>
> When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:
>
>
> (x@MacBook-Pro)48>
> (x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> [{-1337,"value two"},
>  {1,"Last entered"},
>  {42,value_three},
>  {"a",1}]
>
>
> Could one relay on this always being the case?
> A I need this list to be sorted, I would hate to attempt sorting the already sorted list.
>
> Thanks in advance
>
> V/
>
Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Ulf Wiger-2
I should perhaps clarify that the cost of 'canonical' (in this case,
sorting) would of course still be lower than calling lists:sort/1 to
get what you need. Presumably, if you actually need the elements
ordered, there will always be a cost.

BR,
Ulf W

Den fre 28 feb. 2020 kl 10:58 skrev Ulf Wiger <[hidden email]>:

>
> This was discussed at length in a previous thread:
>
> http://erlang.org/pipermail/erlang-questions/2017-October/093981.html
>
> The short answer is "no", you can't rely on the order, and this should
> perhaps be more clearly documented. In the future, it might be nice
> with some 'canonical' option to e.g. term_to_binary/2, to ensure that
> encoding is consistent. This would of course come at a cost.
>
> BR,
> Ulf W
>
> Den fre 28 feb. 2020 kl 10:45 skrev Valentin Micic <[hidden email]>:
> >
> > Hi
> >
> > Even though documentation indicates that:
> >
> > to_list(Map) -> [{Key, Value}]
> >
> > Types
> >
> > Map = map()
> > Key = Value = term()
> >
> >
> > Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.
> >
> > It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
> > I did some testing using a bit modified example offered in documentation:
> >
> >
> > (x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> > [{1,"Last entered"},
> >  {42,value_three},
> >  {1337,"value two"},
> >  {"a",1}]
> >
> >
> >
> > When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:
> >
> >
> > (x@MacBook-Pro)48>
> > (x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> > [{-1337,"value two"},
> >  {1,"Last entered"},
> >  {42,value_three},
> >  {"a",1}]
> >
> >
> > Could one relay on this always being the case?
> > A I need this list to be sorted, I would hate to attempt sorting the already sorted list.
> >
> > Thanks in advance
> >
> > V/
> >
Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Valentin Micic-6
In reply to this post by Jesper Louis Andersen-2
Thanks, this clarifies it.
Much obliged.

V/

On 28 Feb 2020, at 11:56, Jesper Louis Andersen <[hidden email]> wrote:

No, and it is subtle:

L1 = [{X, X} || X <- lists:seq(1,32)].
L1 == maps:to_list(maps:from_list(L1)).
true

L2 = [{X, X} || X <- lists:seq(1,33)].
L2 == maps:to_list(maps:from_list(L2)).
false

At 32+ elements, Maps change their representation order to a hash array mapped trie. These are not generally ordered, but provide very fast lookups. In practice you are O(1) bound with a couple of memory reads. In theory you are O(lg n) bound width a branch factor of 32.

If you need the order, you need to use a representation which maintains the order.

On Fri, Feb 28, 2020 at 10:45 AM Valentin Micic <[hidden email]> wrote:
Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

Types

Map = map()
Key = Value = term()


Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:


(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).  
[{1,"Last entered"},
 {42,value_three},
 {1337,"value two"},
 {"a",1}]



When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:


(x@MacBook-Pro)48> 
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
 {1,"Last entered"},
 {42,value_three},
 {"a",1}]


Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

Thanks in advance

V/



--
J.

Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Valentin Micic-6
In reply to this post by Ulf Wiger-2
Thanks Ulf.

Indeed, there’s always a cost. However, one should not inflict more cost than actually necessary, hence my question.

As for my specific “problem”, well, there are easier (and probably more efficient) ways than to convert map to list, thus,  having a version of  <a href="maps:to_list/2" class="">map:to_list/2 with the second argument explicitly specifying, say, a sorting order, would probably have just a *marginal* utility value, even if it would be faster than calling map:to_list/1 followed by lists:sort/1. 

V/


On 28 Feb 2020, at 12:00, Ulf Wiger <[hidden email]> wrote:

I should perhaps clarify that the cost of 'canonical' (in this case,
sorting) would of course still be lower than calling lists:sort/1 to
get what you need. Presumably, if you actually need the elements
ordered, there will always be a cost.

BR,
Ulf W

Den fre 28 feb. 2020 kl 10:58 skrev Ulf Wiger <[hidden email]>:

This was discussed at length in a previous thread:

http://erlang.org/pipermail/erlang-questions/2017-October/093981.html

The short answer is "no", you can't rely on the order, and this should
perhaps be more clearly documented. In the future, it might be nice
with some 'canonical' option to e.g. term_to_binary/2, to ensure that
encoding is consistent. This would of course come at a cost.

BR,
Ulf W

Den fre 28 feb. 2020 kl 10:45 skrev Valentin Micic <[hidden email]>:

Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

Types

Map = map()
Key = Value = term()


Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:


(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{1,"Last entered"},
{42,value_three},
{1337,"value two"},
{"a",1}]



When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:


(x@MacBook-Pro)48>
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
{1,"Last entered"},
{42,value_three},
{"a",1}]


Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

Thanks in advance

V/


Reply | Threaded
Open this post in threaded view
|

Re: Maps:to_list/1 element order.

Valentin Micic-6
In reply to this post by Valentin Micic-6
Thanks.

On 28 Feb 2020, at 11:58, Łukasz Niemier <[hidden email]> wrote:

Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.

„Sorted” is special case of „arbitrary order”. Also this is only case in case of maps with less than 32 keys which are stored as 2 sorted tuples. Over that limit the map is stored as a hash map which will cause more „arbitrary ordering”.

--

Łukasz Niemier
[hidden email]