diff options
author | Ben Wilson <[email protected]> | 2016-02-08 21:43:15 -0500 |
---|---|---|
committer | Ben Wilson <[email protected]> | 2016-02-09 11:06:08 -0500 |
commit | 38330fa8bfc5e2ea190923fa8f6434b8c5fbedad (patch) | |
tree | cff992907d928f87830613ea426fba42b635245f /lib/snmp | |
parent | a03b7add86b92d0d7d2d744e5555314bedbc2197 (diff) | |
download | otp-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/snmp')
0 files changed, 0 insertions, 0 deletions