Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > cartesian product...

Reply
Thread Tools

cartesian product...

 
 
deancoo
Guest
Posts: n/a
 
      02-28-2005
I need to do a Cartesian product, which is inherently expensive. Turns out,
it's too expensive. I've dropped in that portion of my C++ code in hopes
that someone with greater expertise with STL containers and algorithms would
be able to see if there are any significant inefficiencies in what I've
done. Otherwise, I'm going to have to rethink my solution, which I really
would like to avoid. Thanks for any help.

d

// initialize iterators to vectors
bc_it_start = board_combinations.begin();
bc_it_end = board_combinations.end();
hcmb_it_start = tcart_combinations.begin();
hcmb_it_end = tcart_combinations.end();

for (hcmb_it=hcmb_it_start; hcmb_it!=hcmb_it_end; hcmb_it++) {

for (bc_it=bc_it_start; bc_it!=bc_it_end; bc_it++) {

// set iterators to containers within outside containers
cc_it_start = hcmb_it->mycarts.begin();
cc_it_end = hcmb_it->mycarts.end();
brd_it_start = bc_it->mycarts.begin();
brd_it_end = bc_it->mycarts.end();

copy(cc_it_start, cc_it_end,
back_inserter(current_combination.mycarts));
copy(brd_it_start, brd_it_end,
back_inserter(current_combination.mycarts));

cartesian_prod.push_back(current_combination);
current_combination.mycarts.clear();
};
};


 
Reply With Quote
 
 
 
 
Rolf Magnus
Guest
Posts: n/a
 
      02-28-2005
deancoo wrote:

> I need to do a Cartesian product, which is inherently expensive. Turns
> out, it's too expensive. I've dropped in that portion of my C++ code in
> hopes that someone with greater expertise with STL containers and
> algorithms would be able to see if there are any significant
> inefficiencies in what I've done. Otherwise, I'm going to have to rethink
> my solution, which I really would like to avoid. Thanks for any help.
>
> d
>
> // initialize iterators to vectors
> bc_it_start = board_combinations.begin();
> bc_it_end = board_combinations.end();
> hcmb_it_start = tcart_combinations.begin();
> hcmb_it_end = tcart_combinations.end();
>
> for (hcmb_it=hcmb_it_start; hcmb_it!=hcmb_it_end; hcmb_it++) {

++hcmb_it

Pre-increment might be slightly faster than post-increment, but at least,
it's never slower.

> for (bc_it=bc_it_start; bc_it!=bc_it_end; bc_it++) {
>
> // set iterators to containers within outside containers
> cc_it_start = hcmb_it->mycarts.begin();
> cc_it_end = hcmb_it->mycarts.end();
> brd_it_start = bc_it->mycarts.begin();
> brd_it_end = bc_it->mycarts.end();


Are we talking about vectors? Then I'd add:

current_combination.mycarts.reseve(hcmb_it->mycarts.size() +
bc_it->mycarts.size());

to avoid expensive reallocations.

> copy(cc_it_start, cc_it_end,
> back_inserter(current_combination.mycarts));
>
> copy(brd_it_start, brd_it_end,
> back_inserter(current_combination.mycarts));
>
> cartesian_prod.push_back(current_combination);
> current_combination.mycarts.clear();


Instead of the last two lines, I'd do:

cartesian_prod.push_back(std::vector());
swap(current_combinations, cartesian_prod.back();

Again assuming that we're talking about vectors.

> };
> };


 
Reply With Quote
 
 
 
 
deancoo
Guest
Posts: n/a
 
      02-28-2005
"Rolf Magnus" <(E-Mail Removed)> wrote in message
news:cvv0ie$9ne$03$(E-Mail Removed)-online.com...
>
> Are we talking about vectors? Then I'd add:
>
> current_combination.mycarts.reseve(hcmb_it->mycarts.size() +
> bc_it->mycarts.size());
>
> to avoid expensive reallocations.
>


The majority of the growth was in the cartesian_prod container (which is a
vector). Reserving space for it shaved off about 60% from the execution
time. Would implementing cartesian_prod as a list container eliminate the
need for reserving space? My understanding is that lists are singlely
linked lists, which do not require mass reallocation with growth.

d


 
Reply With Quote
 
Rolf Magnus
Guest
Posts: n/a
 
      02-28-2005
deancoo wrote:

>> Are we talking about vectors? Then I'd add:
>>
>> current_combination.mycarts.reseve(hcmb_it->mycarts.size() +
>> bc_it->mycarts.size());
>>
>> to avoid expensive reallocations.
>>

>
> The majority of the growth was in the cartesian_prod container (which is a
> vector). Reserving space for it shaved off about 60% from the execution
> time. Would implementing cartesian_prod as a list container eliminate the
> need for reserving space?


Yes, but a list has its own overhead. For each element, a new node needs to
be allocated dynamically. A vector with the needed space reserved needs
only one allocation.

> My understanding is that lists are singlely linked lists, which do not
> require mass reallocation with growth.


Actually, they are doubly linked. I think the fastest would be a vector with
reserve. If you don't know the size in advance or don't want to use
reserve, you could try a deque instead.

 
Reply With Quote
 
Matt Bitten
Guest
Posts: n/a
 
      02-28-2005
--- deancoo wrote:
> I need to do a Cartesian product, which is inherently expensive.


Question: Do you really need to do it? If you do, fine. But the
first question I would ask myself, if I were in your situation,
is whether the construction of a Cartesian product is really
necessary.

In particular, a C.P. is basically a way of flattening nested
loops into a single structure, which can then be iterated through
in a single loop. So sometimes the best solution is just to use
the nested loops.

-- Matt

 
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
Cartesian product zfareed@umd.umich.edu C++ 2 02-11-2007 10:34 PM
Programming challenge: wildcard exclusion in cartesian products wkehowski@cox.net Python 78 03-28-2006 05:32 PM
wildcard exclusion in cartesian products wkehowski@cox.net Python 3 03-27-2006 01:32 AM
Some thougts on cartesian products Christoph Zwerschke Python 44 01-25-2006 06:32 PM
tuples and cartesian coordinates Gerrit Holl Python 5 12-18-2003 03:55 AM



Advertisments