Ragged array whose rows are of varying size

Discussion in 'C++' started by er, Jul 4, 2008.

  1. er

    er Guest

    Hi All,

    I have an array

    x00,x01,x02,...,x0K0
    x10,x11,x12,...,x1K1
    ..
    ..
    ..
    xm0,xm1,xm2,...,xmKm

    m is *fixed*,
    each of K0, K1,...,Km is occasionally changed i.e. each row is
    "resized" *occasionally*
    each row is modified *often* by the transform algorithm

    does std::vector<vector<some type> > seem fine? or is any reason to
    prefer
    std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    standpoint?

    Thanks.
    er, Jul 4, 2008
    #1
    1. Advertising

  2. er

    Puppet_Sock Guest

    On Jul 4, 2:25 pm, er <> wrote:
    > Hi All,
    >
    > I have an array
    >
    > x00,x01,x02,...,x0K0
    > x10,x11,x12,...,x1K1
    > .
    > .
    > .
    > xm0,xm1,xm2,...,xmKm
    >
    > m is *fixed*,
    > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > "resized" *occasionally*
    > each row is modified *often* by the transform algorithm
    >
    > does  std::vector<vector<some type> > seem fine? or is any reason to
    > prefer
    > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > standpoint?


    It is not really possible to tell from "an efficiency
    standpoint" which will be superior. It will depend on
    many details of such things as object size, how often
    they get moved, how often you index in, how difficult
    it is to make copies, how your compiler and library
    version arrange things, how your platform arranges
    memory and handles paging and on and on.

    The usual correct answer when efficiency is an issue
    (or any resource) is to work up a test case that is as
    similar to your production environment and cases as
    you can manage. Work it up with both possible ways of
    doing things. And get out your stopwatch and do some
    tests. If it is other resources, try it both ways and
    see how those other resources are used.

    If the difference winds up being unimportant, then do
    it whichever way makes program complexity easier to
    manage.
    Socks
    Puppet_Sock, Jul 4, 2008
    #2
    1. Advertising

  3. er

    er Guest

    On Jul 4, 2:25 pm, er <> wrote:
    > Hi All,
    >
    > I have an array
    >
    > x00,x01,x02,...,x0K0
    > x10,x11,x12,...,x1K1
    > .
    > .
    > .
    > xm0,xm1,xm2,...,xmKm
    >
    > m is *fixed*,
    > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > "resized" *occasionally*
    > each row is modified *often* by the transform algorithm
    >
    > does std::vector<vector<some type> > seem fine? or is any reason to
    > prefer
    > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > standpoint?
    >
    > Thanks.


    ps:
    typical values: m<10
    typical values for K0,...,Km: 100, 1000
    er, Jul 4, 2008
    #3
  4. er

    er Guest

    On Jul 4, 2:44 pm, Puppet_Sock <> wrote:
    > On Jul 4, 2:25 pm, er <> wrote:
    >
    >
    >
    > > Hi All,

    >
    > > I have an array

    >
    > > x00,x01,x02,...,x0K0
    > > x10,x11,x12,...,x1K1
    > > .
    > > .
    > > .
    > > xm0,xm1,xm2,...,xmKm

    >
    > > m is *fixed*,
    > > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > > "resized" *occasionally*
    > > each row is modified *often* by the transform algorithm

    >
    > > does std::vector<vector<some type> > seem fine? or is any reason to
    > > prefer
    > > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > > standpoint?

    >
    > It is not really possible to tell from "an efficiency
    > standpoint" which will be superior. It will depend on
    > many details of such things as object size, how often
    > they get moved, how often you index in, how difficult
    > it is to make copies, how your compiler and library
    > version arrange things, how your platform arranges
    > memory and handles paging and on and on.
    >
    > The usual correct answer when efficiency is an issue
    > (or any resource) is to work up a test case that is as
    > similar to your production environment and cases as
    > you can manage. Work it up with both possible ways of
    > doing things. And get out your stopwatch and do some
    > tests. If it is other resources, try it both ways and
    > see how those other resources are used.
    >
    > If the difference winds up being unimportant, then do
    > it whichever way makes program complexity easier to
    > manage.
    > Socks


    sure, i agree with everything you said, and that's probably what i'll
    end up doing.
    however, i'd be interested to know the sort of things that come into
    play in
    determining the tradeoff between std::vector<std::vector> vs
    std::vector<boost::shared_ptr<vector>>

    for example, what happens
    - when i write on array[row j]?
    - when i resize array[row j]? is there any memory reallocation for the
    rows that aren't j. i would think not, but i'm no expert.

    ps2: the x's are scalars (say double).
    er, Jul 4, 2008
    #4
  5. er

    Guest

    On Jul 4, 11:25 am, er <> wrote:
    > Hi All,
    >
    > I have an array
    >
    > x00,x01,x02,...,x0K0
    > x10,x11,x12,...,x1K1
    > .
    > .
    > .
    > xm0,xm1,xm2,...,xmKm
    >
    > m is *fixed*,


    Using a vector for the rows should be fine then (the outer vector
    below), because the number of rows never change.

    > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > "resized" *occasionally*


    Using a vector for each row is fine too.

    > each row is modified *often* by the transform algorithm


    vector for rows is still fine.

    > does  std::vector<vector<some type> > seem fine?


    Yes.

    > or is any reason to
    > prefer
    > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > standpoint?


    The one with shared_ptr could be unnoticably slower because of the
    extra indirection through the shared_ptr. The vector<vector> uses
    indirection anyway: sizeof(vector<some_type>) should be constant
    regardless of the size of the vector.

    If anything, a vector of vector of shared_ptr could make a difference

    vector<vector<shared_ptr<some_type> > >

    if some_type is very expensive to copy or noncopyable. In that case
    you may want to consider boost::ptr_vector as well:

    vector<ptr_vector<some_type> >

    Ali
    , Jul 4, 2008
    #5
  6. er

    er Guest

    On Jul 4, 3:02 pm, wrote:
    > On Jul 4, 11:25 am, er <> wrote:
    >
    > > Hi All,

    >
    > > I have an array

    >
    > > x00,x01,x02,...,x0K0
    > > x10,x11,x12,...,x1K1
    > > .
    > > .
    > > .
    > > xm0,xm1,xm2,...,xmKm

    >
    > > m is *fixed*,

    >
    > Using a vector for the rows should be fine then (the outer vector
    > below), because the number of rows never change.
    >
    > > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > > "resized" *occasionally*

    >
    > Using a vector for each row is fine too.
    >
    > > each row is modified *often* by the transform algorithm

    >
    > vector for rows is still fine.
    >
    > > does std::vector<vector<some type> > seem fine?

    >
    > Yes.
    >
    > > or is any reason to
    > > prefer
    > > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > > standpoint?

    >
    > The one with shared_ptr could be unnoticably slower because of the
    > extra indirection through the shared_ptr. The vector<vector> uses
    > indirection anyway: sizeof(vector<some_type>) should be constant
    > regardless of the size of the vector.
    >
    > If anything, a vector of vector of shared_ptr could make a difference
    >
    > vector<vector<shared_ptr<some_type> > >
    >
    > if some_type is very expensive to copy or noncopyable. In that case
    > you may want to consider boost::ptr_vector as well:
    >
    > vector<ptr_vector<some_type> >
    >
    > Ali


    excellent! thanks!
    er, Jul 4, 2008
    #6
  7. er

    Jerry Coffin Guest

    In article <b19109c9-ea8d-403a-809a-35b8760a6346
    @d45g2000hsc.googlegroups.com>, says...
    > Hi All,
    >
    > I have an array
    >
    > x00,x01,x02,...,x0K0
    > x10,x11,x12,...,x1K1
    > .
    > .
    > .
    > xm0,xm1,xm2,...,xmKm
    >
    > m is *fixed*,
    > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > "resized" *occasionally*
    > each row is modified *often* by the transform algorithm
    >
    > does std::vector<vector<some type> > seem fine? or is any reason to
    > prefer
    > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > standpoint?


    Since you're not changing the number of rows, there's no particularly
    good reason to use a column of pointers -- you'd do that to avoid
    copying entire rows when the row vector is resized.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Jul 4, 2008
    #7
  8. er

    er Guest

    On Jul 4, 3:32 pm, Jerry Coffin <> wrote:
    > In article <b19109c9-ea8d-403a-809a-35b8760a6346
    > @d45g2000hsc.googlegroups.com>, says...
    >
    >
    >
    > > Hi All,

    >
    > > I have an array

    >
    > > x00,x01,x02,...,x0K0
    > > x10,x11,x12,...,x1K1
    > > .
    > > .
    > > .
    > > xm0,xm1,xm2,...,xmKm

    >
    > > m is *fixed*,
    > > each of K0, K1,...,Km is occasionally changed i.e. each row is
    > > "resized" *occasionally*
    > > each row is modified *often* by the transform algorithm

    >
    > > does std::vector<vector<some type> > seem fine? or is any reason to
    > > prefer
    > > std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    > > standpoint?

    >
    > Since you're not changing the number of rows, there's no particularly
    > good reason to use a column of pointers -- you'd do that to avoid
    > copying entire rows when the row vector is resized.
    >
    > --
    > Later,
    > Jerry.
    >
    > The universe is a figment of its own imagination.


    Absolutely, just wanted it confirmed, just in case. thanks!
    er, Jul 5, 2008
    #8
  9. On Fri, 4 Jul 2008 12:02:25 -0700 (PDT), acehreli@...com wrote:
    >Using a vector for the rows should be fine then (the outer vector
    >below), because the number of rows never change.


    .... if you use reserve() before populating the vector to avoid the
    unnecessary copying of elements.

    >> or is any reason to
    >> prefer
    >> std::vector<std::shared_ptr<vector<some type>> > from an efficiency
    >> standpoint?

    >
    >The one with shared_ptr could be unnoticably slower because of the
    >extra indirection through the shared_ptr. The vector<vector> uses
    >indirection anyway: sizeof(vector<some_type>) should be constant
    >regardless of the size of the vector.


    shared_ptr uses one dynamic allocation per element. This will slow
    down the applicaton, not the 'extra indirection'.



    --
    Roland Pibinger
    "The best software is simple, elegant, and full of drama" - Grady Booch
    Roland Pibinger, Jul 5, 2008
    #9
    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. Java and Swing

    Split string whose length is varying

    Java and Swing, Oct 6, 2005, in forum: C Programming
    Replies:
    9
    Views:
    307
    Christopher Benson-Manica
    Oct 6, 2005
  2. Shust

    2D Ragged Arrays

    Shust, May 1, 2008, in forum: Java
    Replies:
    0
    Views:
    468
    Shust
    May 1, 2008
  3. Mike Robbins

    Ragged Display - Which Control?

    Mike Robbins, Oct 25, 2005, in forum: ASP .Net Web Controls
    Replies:
    4
    Views:
    154
    Mike Robbins
    Oct 26, 2005
  4. Phlip
    Replies:
    17
    Views:
    223
    Rick DeNatale
    May 18, 2009
  5. Matt
    Replies:
    9
    Views:
    1,140
    Mark Curry
    Feb 10, 2012
Loading...

Share This Page