Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Computing > Computer Information > Algorithmic complexity & STL

Reply
Thread Tools

Algorithmic complexity & STL

 
 
Generic Usenet Account
Guest
Posts: n/a
 
      04-11-2005
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

 
Reply With Quote
 
 
 
 
Artie Gold
Guest
Posts: n/a
 
      04-11-2005
[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
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      04-11-2005
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.


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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

 
Reply With Quote
 
Mark P
Guest
Posts: n/a
 
      04-11-2005
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)


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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algorithmic vs design complexity Vidar Hasfjord C++ 4 03-30-2011 02:11 AM
Algorithmic complexity & STL Generic Usenet Account C++ 3 04-11-2005 07:52 AM
Algorithmic complexity of len (list)? Roy Smith Python 8 07-06-2004 10:45 PM
Table with complexity of all STL structures, algorithms... Gawelek C++ 0 11-23-2003 06:35 PM
Algorithmic complexity of StringIO? Roy Smith Python 2 09-13-2003 04:31 PM



Advertisments