Algorithmic complexity & STL

  • Thread starter Generic Usenet Account
  • Start date
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
 
A

Artie Gold

[followups directed to news:comp.programming]
Generic said:
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
 
C

CBFalconer

Generic said:
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.

This is nonsense. The critical thing is 'what kind of accesses are
required'. The database design should reflect that. Think about
how you find all the Bs associated with an A value.
 
M

Mark P

Generic said:
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)

The time complexity of what? Clearly some sort of lookup, but you
haven't provided enough information to allow any meaningful analysis.
Tell us what it is you want to do with this data strucutre.

Mark
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Algorithmic vs design complexity 4
vector swap time complexity 32
Heapsort Complexity Analysis 5
time complexity 2
Help with array 4
Sorting an STL map 1
Competitive coding 1
Can't solve problems! please Help 0

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top