cartesian product...

Discussion in 'C++' started by deancoo, Feb 28, 2005.

  1. deancoo

    deancoo Guest

    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();
    };
    };
    deancoo, Feb 28, 2005
    #1
    1. Advertising

  2. deancoo

    Rolf Magnus Guest

    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.

    > };
    > };
    Rolf Magnus, Feb 28, 2005
    #2
    1. Advertising

  3. deancoo

    deancoo Guest

    "Rolf Magnus" <> wrote in message
    news:cvv0ie$9ne$03$-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
    deancoo, Feb 28, 2005
    #3
  4. deancoo

    Rolf Magnus Guest

    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.
    Rolf Magnus, Feb 28, 2005
    #4
  5. deancoo

    Matt Bitten Guest

    --- 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
    Matt Bitten, Feb 28, 2005
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Cartesian product

    , Feb 11, 2007, in forum: C++
    Replies:
    2
    Views:
    955
    Kai-Uwe Bux
    Feb 11, 2007
  2. Thorsten Kampe

    Cartesian Product of two lists (itertools)

    Thorsten Kampe, Jan 25, 2009, in forum: Python
    Replies:
    3
    Views:
    417
    Mark Wooding
    Jan 26, 2009
  3. Brad
    Replies:
    9
    Views:
    357
  4. walter a kehowski

    cartesian product

    walter a kehowski, Aug 7, 2005, in forum: Ruby
    Replies:
    26
    Views:
    317
    tony summerfelt
    Aug 10, 2005
  5. walter a kehowski

    cartesian product - next to last version

    walter a kehowski, Aug 11, 2005, in forum: Ruby
    Replies:
    11
    Views:
    210
    Brian Schröder
    Aug 13, 2005
Loading...

Share This Page