[BGL] unordered_set<std::vector<edge_descriptor> >
Hi, I want to keep a set of paths, which are implemented as a vector of edge_descriptor. I don't care about the order. I just have to add paths and be able to know the number of different paths present in the set. So, I plan to use unordered_set but I'd like to know you opinion about a hash function, since AFAIK, unordered_set is like an hash_set? My main issue is to use as few memory as possible, because there will have a lot of paths in the set. Any idea? Thanks for your help. -- Johan
I want to keep a set of paths, which are implemented as a vector of edge_descriptor. I don't care about the order. I just have to add paths and be able to know the number of different paths present in the set.
So, I plan to use unordered_set but I'd like to know you opinion about a hash function, since AFAIK, unordered_set is like an hash_set?
My main issue is to use as few memory as possible, because there will have a lot of paths in the set. Any idea?
How many is a lot? Do you know the number before hand? If the order really doesn't matter and you don't need the associative properties of a hash table, I'd stick with a list. for forward_list (for less memory, but no reverse iteration). Andrew Sutton andrew.n.sutton@gmail.com
On Wed, Apr 29, 2009 at 6:58 PM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
I want to keep a set of paths, which are implemented as a vector of edge_descriptor. I don't care about the order. I just have to add paths and be able to know the number of different paths present in the set.
So, I plan to use unordered_set but I'd like to know you opinion about a hash function, since AFAIK, unordered_set is like an hash_set?
My main issue is to use as few memory as possible, because there will have a lot of paths in the set. Any idea?
How many is a lot? Do you know the number before hand?
At least 1e7 paths. And the path size (i.e, vector<edge_descriptor>.size()) is about 10 elements.
If the order really doesn't matter and you don't need the associative properties of a hash table, I'd stick with a list. for forward_list (for less memory, but no reverse iteration).
I do need the associative property. Basically, I will draw a lot of paths and I'd like to know the number of *different* paths I've drawn. -- Johan
My main issue is to use as few memory as possible, because there will have a lot of paths in the set. Any idea?
How many is a lot? Do you know the number before hand?
At least 1e7 paths. And the path size (i.e, vector<edge_descriptor>.size()) is about 10 elements.
If the order really doesn't matter and you don't need the associative properties of a hash table, I'd stick with a list. for forward_list (for less memory, but no reverse iteration).
I do need the associative property. Basically, I will draw a lot of paths and I'd like to know the number of *different* paths I've drawn.
That does seem like a fairly large number :) In that case unordered_map should work fine (it's basically the same as hash_map). you might want to pre-seed it with a large initial (prime) number of buckets to avoid a lot of rehashing. You can use the Boost.Functional/Hash library to create a hash function for paths. That library has some support for computing combined hash keys. There may even be an overload for vector, but I'm not sure. Andrew Sutton andrew.n.sutton@gmail.com
On Thu, Apr 30, 2009 at 1:48 PM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
My main issue is to use as few memory as possible, because there will have a lot of paths in the set. Any idea?
How many is a lot? Do you know the number before hand?
At least 1e7 paths. And the path size (i.e, vector<edge_descriptor>.size()) is about 10 elements.
If the order really doesn't matter and you don't need the associative properties of a hash table, I'd stick with a list. for forward_list (for less memory, but no reverse iteration).
I do need the associative property. Basically, I will draw a lot of paths and I'd like to know the number of *different* paths I've drawn.
That does seem like a fairly large number :) In that case unordered_map should work fine (it's basically the same as hash_map). you might want to
You mean unordered_set, don't you?
pre-seed it with a large initial (prime) number of buckets to avoid a lot of rehashing.
Hum... I don't know this specificity about hashing... I should read the documentation, but thanks for the information ;)
You can use the Boost.Functional/Hash library to create a hash function for paths. That library has some support for computing combined hash keys. There may even be an overload for vector, but I'm not sure.
Thanks. That's exactly what I'm looking for! Best, -- Johan
2009/4/30 Johan Oudinet <johan.oudinet@gmail.com>:
At least 1e7 paths. And the path size (i.e, vector<edge_descriptor>.size()) is about 10 elements.
If you're using the boost unordered containers, don't use boost 1.38, it has a bug which causes poor performance for very large amounts of elements. It isn't in earlier versions, and 1.39 will fix it. I hope that isn't a problem. Daniel
participants (7)
-
Andrew Sutton -
Daniel James -
Johan Oudinet