add_new() for array like push_back() for vector

Discussion in 'C++' started by Alex Vinokur, Apr 10, 2004.

  1. Alex Vinokur

    Alex Vinokur Guest

    Hi,

    vector<T> v (100);
    T *a = new T [100];

    v.push_back(T());
    Is it possible to add new T to array to get _contiguous_ storage area (for 101 element in an example above)?

    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
     
    Alex Vinokur, Apr 10, 2004
    #1
    1. Advertising

  2. "Alex Vinokur" <> wrote in message
    news:c58hak$2pi133$-berlin.de...
    > Hi,
    >
    > vector<T> v (100);
    > T *a = new T [100];
    >
    > v.push_back(T());
    > Is it possible to add new T to array to get _contiguous_ storage area (for

    101 element in an example above)?

    yes. A vector always has contiguous storage. Just say

    const int sz = 100;
    std::copy( a, a+sz, std::back_inserter( v ) );

    br

    Thorsten

    (Btw, one should *always* stay away from builtin arrays in C++, unless there
    is a *very* good reason.
    Use boost::array<> and std::vector<> instead.)
     
    Thorsten Ottosen, Apr 10, 2004
    #2
    1. Advertising

  3. "Alex Vinokur" <> wrote in message
    news:c58hak$2pi133$-berlin.de...
    > Hi,
    >
    > vector<T> v (100);
    > T *a = new T [100];
    >
    > v.push_back(T());
    > Is it possible to add new T to array to get _contiguous_ storage area (for

    101 element in an example above)?
    >


    No, all you can do is allocate a new 101 element array and copy elements
    from the old array to the new array.

    But what's the problem? vector is contiguous already, just use a vector.

    john
     
    John Harrison, Apr 10, 2004
    #3
  4. Alex Vinokur

    Alex Vinokur Guest

    "John Harrison" <> wrote in message news:c58j0e$2ota43$-berlin.de...
    >
    > "Alex Vinokur" <> wrote in message
    > news:c58hak$2pi133$-berlin.de...
    > > Hi,
    > >
    > > vector<T> v (100);
    > > T *a = new T [100];
    > >
    > > v.push_back(T());
    > > Is it possible to add new T to array to get _contiguous_ storage area (for

    > 101 element in an example above)?
    > >

    >
    > No, all you can do is allocate a new 101 element array and copy elements
    > from the old array to the new array.
    >
    > But what's the problem? vector is contiguous already, just use a vector.
    >


    I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
    http://groups.google.com/groups?selm=bo4nls$17vfq6$-berlin.de.

    In particular I want to try
    to replace vector<ulong> units_ in class BigInt
    by an array of ulong's.

    [snip]

    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
     
    Alex Vinokur, Apr 10, 2004
    #4
  5. > >
    > > But what's the problem? vector is contiguous already, just use a vector.
    > >

    >
    > I would like to impove performance of algorithm "Computing very long

    Fibonacci numbers" at
    >

    http://groups.google.com/groups?selm=bo4nls$17vfq6$-berlin.de.
    >
    > In particular I want to try
    > to replace vector<ulong> units_ in class BigInt
    > by an array of ulong's.
    >


    Not sure that would give you any improvement. But of course it all depends
    on your compiler and STL implementation.

    One possible improvement is

    BigInt Fibonacci::get_number (uint n_i)
    {
    fibs_.reserve(n_i + 1); // <<<------------ add this
    const uint cur_size = fibs_.size ();

    which will help avoid repeatedly resizing the fibs_ vector.

    john
     
    John Harrison, Apr 10, 2004
    #5
  6. Alex Vinokur

    Alex Vinokur Guest

    vector.reserve() and performance (Was: add_new() for array like push_back() for vector)

    "John Harrison" <> wrote in message news:c58obb$2qat6b$-berlin.de...
    > > >
    > > > But what's the problem? vector is contiguous already, just use a vector.
    > > >

    > >
    > > I would like to impove performance of algorithm "Computing very long

    > Fibonacci numbers" at
    > >

    > http://groups.google.com/groups?selm=bo4nls$17vfq6$-berlin.de.
    > >
    > > In particular I want to try
    > > to replace vector<ulong> units_ in class BigInt
    > > by an array of ulong's.
    > >

    >
    > Not sure that would give you any improvement. But of course it all depends
    > on your compiler and STL implementation.
    >
    > One possible improvement is
    >
    > BigInt Fibonacci::get_number (uint n_i)
    > {
    > fibs_.reserve(n_i + 1); // <<<------------ add this


    This improvement is very significant (see below).
    John, thank you very much.

    > const uint cur_size = fibs_.size ();
    >
    > which will help avoid repeatedly resizing the fibs_ vector.
    >
    > john
    >
    >


    ===========================
    ------------------------------
    Windows 2000
    CYGWIN_NT-5.0 1.5.5(0.94/3/2)
    GNU g++ version 3.3.1 (cygming special)
    ------------------------------

    ------ Compilation ------
    $ g++ [Optimaze option] -mno-cygwin foo.cpp
    -------------------------

    Computing Fibonacci[50,000].
    Comparative performance.
    -----------------------------------------------
    | Original | Algorithm with |
    Optimization | Algorithm | John Harrison's |
    | | improvement |
    ----------------|-----------------------------|
    No optimization | 6.118 | 5.027 |
    Optimization O1 | 3.344 | 2.423 |
    Optimization O2 | 3.214 | 2.323 |
    Optimization O2 | 3.294 | 2.293 |
    -----------------------------------------------


    Thanks again.

    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
     
    Alex Vinokur, Apr 10, 2004
    #6
  7. Re: vector.reserve() and performance (Was: add_new() for array like push_back() for vector)

    "Alex Vinokur" <> wrote in message
    news:c592gt$2qbh4h$-berlin.de...
    >
    > "John Harrison" <> wrote in message

    news:c58obb$2qat6b$-berlin.de...
    > > > >
    > > > > But what's the problem? vector is contiguous already, just use a

    vector.
    > > > >
    > > >
    > > > I would like to impove performance of algorithm "Computing very long

    > > Fibonacci numbers" at
    > > >

    > >

    http://groups.google.com/groups?selm=bo4nls$17vfq6$-berlin.de.

    Just a quick question: why don't just use the formula for a Fibonacci
    number? It's

    Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)

    its been known for almost 300 years :)

    br

    Thorsten
     
    Thorsten Ottosen, Apr 10, 2004
    #7
  8. Alex Vinokur

    Alex Vinokur Guest

    Re: vector.reserve() and performance (Was: add_new() for array like push_back() for vector)

    "Thorsten Ottosen" <> wrote in message news:40781af1$0$12740$...
    > "Alex Vinokur" <> wrote in message
    > news:c592gt$2qbh4h$-berlin.de...
    > >
    > > "John Harrison" <> wrote in message

    > news:c58obb$2qat6b$-berlin.de...
    > > > > >
    > > > > > But what's the problem? vector is contiguous already, just use a

    > vector.
    > > > > >
    > > > >
    > > > > I would like to impove performance of algorithm "Computing very long
    > > > Fibonacci numbers" at
    > > > >
    > > >

    > http://groups.google.com/groups?selm=bo4nls$17vfq6$-berlin.de.
    >
    > Just a quick question: why don't just use the formula for a Fibonacci
    > number? It's
    >
    > Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
    >
    > its been known for almost 300 years :)
    >

    [snip]

    I wanted
    * to check what (and how fast) can we compute when using _explicit_ Fibonacci formula,
    * to create and to test class BigInt,
    * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only Fibonaccci[n])

    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
     
    Alex Vinokur, Apr 11, 2004
    #8
  9. Re: vector.reserve() and performance (Was: add_new() for array like push_back() for vector)

    >
    > I wanted
    > * to check what (and how fast) can we compute when using _explicit_

    Fibonacci formula,
    > * to create and to test class BigInt,
    > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only

    Fibonaccci[n])
    >


    Another possible optimization, replace

    default :
    fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
    break;

    with

    default :
    fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
    break;

    When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
    been calculated and stored so this is safe to do. Might save a little time
    and can't do any harm.

    Actually my intuition is that it will not save any significant time, but
    worth a try.

    john
     
    John Harrison, Apr 11, 2004
    #9
  10. Alex Vinokur

    Alex Vinokur Guest

    Re: vector.reserve() and performance (Was: add_new() for array like push_back() for vector)

    "John Harrison" <> wrote in message news:c5an40$2nj0mp$-berlin.de...
    > >
    > > I wanted
    > > * to check what (and how fast) can we compute when using _explicit_

    > Fibonacci formula,
    > > * to create and to test class BigInt,
    > > * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only

    > Fibonaccci[n])
    > >

    >
    > Another possible optimization, replace
    >
    > default :
    > fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
    > break;
    >
    > with
    >
    > default :
    > fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
    > break;
    >
    > When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
    > been calculated and stored so this is safe to do. Might save a little time
    > and can't do any harm.
    >
    > Actually my intuition is that it will not save any significant time, but
    > worth a try.
    >
    > john
    >
    >


    I have tested that.
    It is unclear if it saves some time, but indeed it does no harm.
    I am going to use
    * fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));

    P.S. That was one of options in very old algorithm :
    http://groups.google.com/groups?selm=7g0qsd$ (method getFibNumber (int n_i)).

    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
     
    Alex Vinokur, Apr 11, 2004
    #10
    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. Ganesh Gella
    Replies:
    5
    Views:
    1,198
    John Harrison
    Jul 14, 2003
  2. Hitesh Bhatiya
    Replies:
    4
    Views:
    4,530
    John Harrison
    Aug 13, 2003
  3. Avi Bercovich
    Replies:
    5
    Views:
    23,638
    Evan Carew
    Jan 14, 2004
  4. Antonios Christofides

    vector::push_back performance

    Antonios Christofides, Sep 28, 2004, in forum: C++
    Replies:
    30
    Views:
    7,959
    Andrew Koenig
    Oct 7, 2004
  5. Replies:
    8
    Views:
    1,930
    Csaba
    Feb 18, 2006
Loading...

Share This Page