mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Andrew Schwartzmeyer <and...@schwartzmeyer.com>
Subject Re: Review Request 64496: Avoided unnecessary work in contains checks in hashset and hashmap.
Date Mon, 11 Dec 2017 18:04:37 GMT


> On Dec. 11, 2017, 10 a.m., Andrew Schwartzmeyer wrote:
> > Ship It!

Hm, I might take this back. The hypothesis:

> In order to count elements a complete traversal of
the container is required, while a contains check already has an
answer when the first element has been found.

While it sounds right, if you check [unordered_map::count](http://en.cppreference.com/w/cpp/container/unordered_map/count)
and [unordered_set::count](http://en.cppreference.com/w/cpp/container/unordered_set/count),
it does not work like this as these data structures may have at most one matching element.

> Returns the number of elements with key that compares equal to the specified argument
key, which is either 1 or 0 since this container does not allow duplicates. 

And the stated complexity is:

> Constant on average, worst case linear in the size of the container. 

Which is the same as [find](http://en.cppreference.com/w/cpp/container/unordered_map/count).


- Andrew


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/64496/#review193411
-----------------------------------------------------------


On Dec. 11, 2017, 5:31 a.m., Benjamin Bannier wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/64496/
> -----------------------------------------------------------
> 
> (Updated Dec. 11, 2017, 5:31 a.m.)
> 
> 
> Review request for mesos and Michael Park.
> 
> 
> Repository: mesos
> 
> 
> Description
> -------
> 
> In order to check whether a key or value was present in a 'hashset' or
> 'hashmap' we were checking whether the count for that entry was
> greater than zero. In order to count elements a complete traversal of
> the container is required, while a contains check already has an
> answer when the first element has been found.
> 
> This patch uses find in contains check for both hashset and hashmap to
> avoid the full traversal.
> 
> 
> Diffs
> -----
> 
>   3rdparty/stout/include/stout/hashmap.hpp 91085b8d8ad5d35c39c8cc95e3d4765d82d9a8db 
>   3rdparty/stout/include/stout/hashset.hpp 6af209c53185207b53396e7687e3bd7357e57bf1 
> 
> 
> Diff: https://reviews.apache.org/r/64496/diff/1/
> 
> 
> Testing
> -------
> 
> `make check`
> 
> 
> Thanks,
> 
> Benjamin Bannier
> 
>


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message