From 38330fa8bfc5e2ea190923fa8f6434b8c5fbedad Mon Sep 17 00:00:00 2001 From: Ben Wilson Date: Mon, 8 Feb 2016 21:43:15 -0500 Subject: Improved maps:with/2 and maps:without/2 algorithm The current implementation is roughly O(N*M) where N is the number of items to be removed, and M is the number of items in the map. This does not include the cost of `maps:from_list` or `maps:to_list`. This leads to pretty horrifying execution times on large maps regardless of how many or few keys are to be removed. The new implementation is O(N) where N is the number of items to be removed. For each N there's the cost of removing a key from a map, and but in practice that turns out to be a vast improvement for all map sizes I tested The new maps:take/2 implementation similarly builds a list of keys and values by iterating only the list of desired keys, and then hands it off to maps:from_list. This turned out to be faster than N maps:put calls. --- lib/stdlib/src/maps.erl | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 3c798b7a04..43d10f4800 100644 --- a/lib/stdlib/src/maps.erl +++ b/lib/stdlib/src/maps.erl @@ -205,7 +205,7 @@ size(Val) -> K :: term(). without(Ks,M) when is_list(Ks), is_map(M) -> - maps:from_list([{K,V}||{K,V} <- maps:to_list(M), not lists:member(K, Ks)]); + lists:foldl(fun(K, M1) -> ?MODULE:remove(K, M1) end, M, Ks); without(Ks,M) -> erlang:error(error_type(M),[Ks,M]). @@ -216,8 +216,16 @@ without(Ks,M) -> Map2 :: map(), K :: term(). -with(Ks,M) when is_list(Ks), is_map(M) -> - maps:from_list([{K,V}||{K,V} <- maps:to_list(M), lists:member(K, Ks)]); +with(Ks,Map1) when is_list(Ks), is_map(Map1) -> + Fun = fun(K, List) -> + case ?MODULE:find(K, Map1) of + {ok, V} -> + [{K, V} | List]; + error -> + List + end + end, + ?MODULE:from_list(lists:foldl(Fun, [], Ks)); with(Ks,M) -> erlang:error(error_type(M),[Ks,M]). -- cgit v1.2.3