By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,292 Members | 1,514 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,292 IT Pros & Developers. It's quick & easy.

cartesian product...

P: n/a
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();
};
};
Jul 23 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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.
};
};


Jul 23 '05 #2

P: n/a
"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cv*************@news.t-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
Jul 23 '05 #3

P: n/a
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.

Jul 23 '05 #4

P: n/a
--- 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

Jul 23 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.