[followups directed to news:comp.programming]

Generic Usenet Account wrote:

> 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

>
Your analysis is indeed correct; unfortunately, it may be meaningless.

Actually, that's a little harsh. The problem is that there are *very*

important questions -- or information -- you've left out. How large are

`m' and `n' likely to be? What is the cost of comparison or hashing for

these kinds of instances?

Only armed with that information can a determination be made.

HTH,

--ag

--

Artie Gold -- Austin, Texas

http://it-matters.blogspot.com (new post 12/5)

http://www.cafepress.com/goldsays