G
Generic Usenet Account
Consider two entities A and B such that there is a 1:n association
between them. I mean that associated with each instance of A there are
up to n instances of B. Currently in our software we are using an STL
map in which instances of A are the key and each value is a set (STL
set) of instances of B.
There is some thought now that we should instead have a "transpose" of
this data structure. By this I mean that the key should be an instance
of B and the value should be a "singular" instance of A. I have
attempted some preliminary analysis, but I am not sure about the
results. Any independent insight would be appreciated.
Let us assume that we have m instances of A and m*n instances of B.
With our current implementation (key is an instance of A and the value
is an STL set of instances of B), the time complexity is O(log-m) *
O(log-n). With the new proposal (key is an instance of B and the value
is an instance of A), the time complexity is O(log-mn)
If we switch to hash_map instead of map (I know that hash_map is not
part of the STL standard, but it seems to be widely supported now), the
current implementation has a time complexity of O(1) * O(log-n) i.e.
O(log-n). The new proposal has a time complexity of O(1).
It seems that the new proposal has better time complexity in either
case, although with a hash_map the improvement in performance is more
dramatic. Is my analysis correct? Should we go ahead and change our
implementation?
Thanks,
Bhat
between them. I mean that associated with each instance of A there are
up to n instances of B. Currently in our software we are using an STL
map in which instances of A are the key and each value is a set (STL
set) of instances of B.
There is some thought now that we should instead have a "transpose" of
this data structure. By this I mean that the key should be an instance
of B and the value should be a "singular" instance of A. I have
attempted some preliminary analysis, but I am not sure about the
results. Any independent insight would be appreciated.
Let us assume that we have m instances of A and m*n instances of B.
With our current implementation (key is an instance of A and the value
is an STL set of instances of B), the time complexity is O(log-m) *
O(log-n). With the new proposal (key is an instance of B and the value
is an instance of A), the time complexity is O(log-mn)
If we switch to hash_map instead of map (I know that hash_map is not
part of the STL standard, but it seems to be widely supported now), the
current implementation has a time complexity of O(1) * O(log-n) i.e.
O(log-n). The new proposal has a time complexity of O(1).
It seems that the new proposal has better time complexity in either
case, although with a hash_map the improvement in performance is more
dramatic. Is my analysis correct? Should we go ahead and change our
implementation?
Thanks,
Bhat