cartesian product...

[deancoo]

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();
};
};

 

[Rolf Magnus]

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.

 

[deancoo]

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

 

[Rolf Magnus]

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.

 

[Matt Bitten]

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