Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Ragged array whose rows are of varying size

Reply
Thread Tools

Ragged array whose rows are of varying size

 
 
er
Guest
Posts: n/a
 
      07-04-2008
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.
 
Reply With Quote
 
 
 
 
Puppet_Sock
Guest
Posts: n/a
 
      07-04-2008
On Jul 4, 2:25*pm, er <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
er
Guest
Posts: n/a
 
      07-04-2008
On Jul 4, 2:25 pm, er <(E-Mail Removed)> 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

 
Reply With Quote
 
er
Guest
Posts: n/a
 
      07-04-2008
On Jul 4, 2:44 pm, Puppet_Sock <(E-Mail Removed)> wrote:
> On Jul 4, 2:25 pm, er <(E-Mail Removed)> 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).




 
Reply With Quote
 
acehreli@gmail.com
Guest
Posts: n/a
 
      07-04-2008
On Jul 4, 11:25*am, er <(E-Mail Removed)> 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:tr_vector as well:

vector<ptr_vector<some_type> >

Ali
 
Reply With Quote
 
er
Guest
Posts: n/a
 
      07-04-2008
On Jul 4, 3:02 pm, (E-Mail Removed) wrote:
> On Jul 4, 11:25 am, er <(E-Mail Removed)> 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:tr_vector as well:
>
> vector<ptr_vector<some_type> >
>
> Ali


excellent! thanks!
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      07-04-2008
In article <b19109c9-ea8d-403a-809a-35b8760a6346
@d45g2000hsc.googlegroups.com>, http://www.velocityreviews.com/forums/(E-Mail Removed) 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.
 
Reply With Quote
 
er
Guest
Posts: n/a
 
      07-05-2008
On Jul 4, 3:32 pm, Jerry Coffin <(E-Mail Removed)> wrote:
> In article <b19109c9-ea8d-403a-809a-35b8760a6346
> @d45g2000hsc.googlegroups.com>, (E-Mail Removed) 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!
 
Reply With Quote
 
Roland Pibinger
Guest
Posts: n/a
 
      07-05-2008
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
 
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
permute each element of a ragged array? Phlip Ruby 17 05-18-2009 04:34 PM
2D Ragged Arrays Shust Java 0 05-01-2008 09:56 PM
Split string whose length is varying Java and Swing C Programming 9 10-06-2005 07:19 PM
Face curves looking ragged/pixelly Alfred Molon Digital Photography 6 07-25-2004 08:31 PM
Iterating through an array whose size is unknown? matthurne C++ 9 07-16-2004 04:23 PM



Advertisments