add_new() for array like push_back() for vector

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Alex Vinokur

    #1

    add_new() for array like push_back() for vector

    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:alexvn@c onnect.to




  • John Harrison

    #2
    Re: add_new() for array like push_back() for vector


    "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
    news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=blue]
    > 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[/color]
    101 element in an example above)?[color=blue]
    >[/color]

    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


    Comment

    • John Harrison

      #3
      Re: add_new() for array like push_back() for vector


      "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
      news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=blue]
      > 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[/color]
      101 element in an example above)?[color=blue]
      >[/color]

      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


      Comment

      • Thorsten Ottosen

        #4
        Re: add_new() for array like push_back() for vector

        "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
        news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=blue]
        > 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[/color]
        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_inser ter( 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.)


        Comment

        • Thorsten Ottosen

          #5
          Re: add_new() for array like push_back() for vector

          "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
          news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=blue]
          > 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[/color]
          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_inser ter( 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.)


          Comment

          • Alex Vinokur

            #6
            Re: add_new() for array like push_back() for vector


            "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c58j0e$2ot a43$1@ID-196037.news.uni-berlin.de...[color=blue]
            >
            > "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
            > news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=green]
            > > 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[/color]
            > 101 element in an example above)?[color=green]
            > >[/color]
            >
            > 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.
            >[/color]

            I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
            http://groups.google.com/groups?selm....uni-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:alexvn@c onnect.to




            Comment

            • Alex Vinokur

              #7
              Re: add_new() for array like push_back() for vector


              "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c58j0e$2ot a43$1@ID-196037.news.uni-berlin.de...[color=blue]
              >
              > "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
              > news:c58hak$2pi 133$1@ID-79865.news.uni-berlin.de...[color=green]
              > > 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[/color]
              > 101 element in an example above)?[color=green]
              > >[/color]
              >
              > 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.
              >[/color]

              I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
              http://groups.google.com/groups?selm....uni-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:alexvn@c onnect.to




              Comment

              • John Harrison

                #8
                Re: add_new() for array like push_back() for vector

                > >[color=blue][color=green]
                > > But what's the problem? vector is contiguous already, just use a vector.
                > >[/color]
                >
                > I would like to impove performance of algorithm "Computing very long[/color]
                Fibonacci numbers" at[color=blue]
                >[/color]
                http://groups.google.com/groups?selm....uni-berlin.de.[color=blue]
                >
                > In particular I want to try
                > to replace vector<ulong> units_ in class BigInt
                > by an array of ulong's.
                >[/color]

                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


                Comment

                • John Harrison

                  #9
                  Re: add_new() for array like push_back() for vector

                  > >[color=blue][color=green]
                  > > But what's the problem? vector is contiguous already, just use a vector.
                  > >[/color]
                  >
                  > I would like to impove performance of algorithm "Computing very long[/color]
                  Fibonacci numbers" at[color=blue]
                  >[/color]
                  http://groups.google.com/groups?selm....uni-berlin.de.[color=blue]
                  >
                  > In particular I want to try
                  > to replace vector<ulong> units_ in class BigInt
                  > by an array of ulong's.
                  >[/color]

                  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


                  Comment

                  • Alex Vinokur

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


                    "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=blue][color=green][color=darkred]
                    > > >
                    > > > But what's the problem? vector is contiguous already, just use a vector.
                    > > >[/color]
                    > >
                    > > I would like to impove performance of algorithm "Computing very long[/color]
                    > Fibonacci numbers" at[color=green]
                    > >[/color]
                    > http://groups.google.com/groups?selm....uni-berlin.de.[color=green]
                    > >
                    > > In particular I want to try
                    > > to replace vector<ulong> units_ in class BigInt
                    > > by an array of ulong's.
                    > >[/color]
                    >
                    > 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[/color]

                    This improvement is very significant (see below).
                    John, thank you very much.
                    [color=blue]
                    > const uint cur_size = fibs_.size ();
                    >
                    > which will help avoid repeatedly resizing the fibs_ vector.
                    >
                    > john
                    >
                    >[/color]

                    =============== ============
                    ------------------------------
                    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:alexvn@c onnect.to




                    Comment

                    • Alex Vinokur

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


                      "John Harrison" <john_andronicu s@hotmail.com> wrote in message news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=blue][color=green][color=darkred]
                      > > >
                      > > > But what's the problem? vector is contiguous already, just use a vector.
                      > > >[/color]
                      > >
                      > > I would like to impove performance of algorithm "Computing very long[/color]
                      > Fibonacci numbers" at[color=green]
                      > >[/color]
                      > http://groups.google.com/groups?selm....uni-berlin.de.[color=green]
                      > >
                      > > In particular I want to try
                      > > to replace vector<ulong> units_ in class BigInt
                      > > by an array of ulong's.
                      > >[/color]
                      >
                      > 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[/color]

                      This improvement is very significant (see below).
                      John, thank you very much.
                      [color=blue]
                      > const uint cur_size = fibs_.size ();
                      >
                      > which will help avoid repeatedly resizing the fibs_ vector.
                      >
                      > john
                      >
                      >[/color]

                      =============== ============
                      ------------------------------
                      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:alexvn@c onnect.to




                      Comment

                      • Thorsten Ottosen

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

                        "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
                        news:c592gt$2qb h4h$1@ID-79865.news.uni-berlin.de...[color=blue]
                        >
                        > "John Harrison" <john_andronicu s@hotmail.com> wrote in message[/color]
                        news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=blue][color=green][color=darkred]
                        > > > >
                        > > > > But what's the problem? vector is contiguous already, just use a[/color][/color][/color]
                        vector.[color=blue][color=green][color=darkred]
                        > > > >
                        > > >
                        > > > I would like to impove performance of algorithm "Computing very long[/color]
                        > > Fibonacci numbers" at[color=darkred]
                        > > >[/color]
                        > >[/color][/color]
                        http://groups.google.com/groups?selm....uni-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


                        Comment

                        • Thorsten Ottosen

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

                          "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
                          news:c592gt$2qb h4h$1@ID-79865.news.uni-berlin.de...[color=blue]
                          >
                          > "John Harrison" <john_andronicu s@hotmail.com> wrote in message[/color]
                          news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=blue][color=green][color=darkred]
                          > > > >
                          > > > > But what's the problem? vector is contiguous already, just use a[/color][/color][/color]
                          vector.[color=blue][color=green][color=darkred]
                          > > > >
                          > > >
                          > > > I would like to impove performance of algorithm "Computing very long[/color]
                          > > Fibonacci numbers" at[color=darkred]
                          > > >[/color]
                          > >[/color][/color]
                          http://groups.google.com/groups?selm....uni-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


                          Comment

                          • Alex Vinokur

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


                            "Thorsten Ottosen" <nesotto@cs.auc .dk> wrote in message news:40781af1$0 $12740$afc38c87 @news.optusnet. com.au...[color=blue]
                            > "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
                            > news:c592gt$2qb h4h$1@ID-79865.news.uni-berlin.de...[color=green]
                            > >
                            > > "John Harrison" <john_andronicu s@hotmail.com> wrote in message[/color]
                            > news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=green][color=darkred]
                            > > > > >
                            > > > > > But what's the problem? vector is contiguous already, just use a[/color][/color]
                            > vector.[color=green][color=darkred]
                            > > > > >
                            > > > >
                            > > > > I would like to impove performance of algorithm "Computing very long
                            > > > Fibonacci numbers" at
                            > > > >
                            > > >[/color][/color]
                            > http://groups.google.com/groups?selm....uni-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 :-)
                            >[/color]
                            [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:alexvn@c onnect.to






                            Comment

                            • Alex Vinokur

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


                              "Thorsten Ottosen" <nesotto@cs.auc .dk> wrote in message news:40781af1$0 $12740$afc38c87 @news.optusnet. com.au...[color=blue]
                              > "Alex Vinokur" <alexvn@big.foo t.com> wrote in message
                              > news:c592gt$2qb h4h$1@ID-79865.news.uni-berlin.de...[color=green]
                              > >
                              > > "John Harrison" <john_andronicu s@hotmail.com> wrote in message[/color]
                              > news:c58obb$2qa t6b$1@ID-196037.news.uni-berlin.de...[color=green][color=darkred]
                              > > > > >
                              > > > > > But what's the problem? vector is contiguous already, just use a[/color][/color]
                              > vector.[color=green][color=darkred]
                              > > > > >
                              > > > >
                              > > > > I would like to impove performance of algorithm "Computing very long
                              > > > Fibonacci numbers" at
                              > > > >
                              > > >[/color][/color]
                              > http://groups.google.com/groups?selm....uni-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 :-)
                              >[/color]
                              [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:alexvn@c onnect.to






                              Comment

                              Working...