aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorBen Wilson <[email protected]>2016-02-08 21:43:15 -0500
committerBen Wilson <[email protected]>2016-02-09 11:06:08 -0500
commit38330fa8bfc5e2ea190923fa8f6434b8c5fbedad (patch)
treecff992907d928f87830613ea426fba42b635245f /lib
parenta03b7add86b92d0d7d2d744e5555314bedbc2197 (diff)
downloadotp-38330fa8bfc5e2ea190923fa8f6434b8c5fbedad.tar.gz
otp-38330fa8bfc5e2ea190923fa8f6434b8c5fbedad.tar.bz2
otp-38330fa8bfc5e2ea190923fa8f6434b8c5fbedad.zip
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.
Diffstat (limited to 'lib')
-rw-r--r--lib/stdlib/src/maps.erl14
1 files changed, 11 insertions, 3 deletions
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]).