Warum Elixirs MapSet nach 32 Elementen ungeordnet ist?

Question

iex> MapSet.new(1..32) |> Enum.to_list 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 
23, 24, 25, 26, 27, 28, 29, 30, 31, 32] 

iex> MapSet.new(1..33) |> Enum.to_list 
[11, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 
22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12] 

Hier ist die implementation in Elixir 1,3

def new(enumerable) do 
    map = 
    enumerable 
    |> Enum.to_list 
    |> do_new([]) 

    %MapSet{map: map} 
end 

defp do_new([], acc) do 
    acc 
    |> :lists.reverse 
    |> :maps.from_list 
end 

defp do_new([item | rest], acc) do 
    do_new(rest, [{item, true} | acc]) 
end 

Auch wenn die Reihenfolge keine Rolle spielt in einem MapSet, aber immer noch fragen, warum ein MapSet nach 32 Elementen ungeordnete wird?

Answer 1

Dies ist nicht spezifisch für MapSet, aber das gleiche passiert mit normalen Map (MapSet verwendet Map unter der Haube):

iex(1)> for i <- Enum.shuffle(1..32), into: %{}, do: {i, i} 
%{1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5, 6 => 6, 7 => 7, 8 => 8, 9 => 9, 
    10 => 10, 11 => 11, 12 => 12, 13 => 13, 14 => 14, 15 => 15, 16 => 16, 
    17 => 17, 18 => 18, 19 => 19, 20 => 20, 21 => 21, 22 => 22, 23 => 23, 
    24 => 24, 25 => 25, 26 => 26, 27 => 27, 28 => 28, 29 => 29, 30 => 30, 
    31 => 31, 32 => 32} 
iex(2)> for i <- Enum.shuffle(1..33), into: %{}, do: {i, i} 
%{11 => 11, 26 => 26, 15 => 15, 20 => 20, 17 => 17, 25 => 25, 13 => 13, 8 => 8, 
    7 => 7, 1 => 1, 32 => 32, 3 => 3, 6 => 6, 2 => 2, 33 => 33, 10 => 10, 9 => 9, 
    19 => 19, 14 => 14, 5 => 5, 18 => 18, 31 => 31, 22 => 22, 29 => 29, 21 => 21, 
    27 => 27, 24 => 24, 30 => 30, 23 => 23, 28 => 28, 16 => 16, 4 => 4, 12 => 12} 

Dies liegt daran, (höchstwahrscheinlich als Optimierungs) Erlang speichert Karten der Größe bis MAP_SMALL_MAP_LIMIT als sorted by keyarray. Erst nachdem die Größe größer als MAP_SMALL_MAP_LIMIT ist, wechselt Erlang zum Speichern der Daten in einem Hash Array Mapped Trie like data structure. Im Nicht-Debug-Modus Erlang, MAP_SMALL_MAP_LIMIT ist defined to be 32, daher sollten alle Karten mit einer Länge von bis zu 32 in sortierter Reihenfolge gedruckt werden. Beachten Sie, dass dies ein Implementierungsdetail ist, soweit ich weiß, und Sie sollten sich nicht auf dieses Verhalten verlassen; Sie können den Wert der Konstante in der Zukunft ändern oder zu einem völlig anderen Algorithmus wechseln, wenn er leistungsfähiger ist.