Python and STL efficiency

[Neil Cerutti]

On 2006-08-24, JSprenkle at gmail.com <JSprenkle at gmail.com> wrote:
>
> Licheng Fang wrote:
>> Hi, I'm learning STL and I wrote some simple code to compare the
>> efficiency of python and STL.
>>
>> //C++
>> #include <iostream>
>> #include <string>
>> #include <vector>
>> #include <set>
>> #include <algorithm>
>> using namespace std;
>>
>> int main(){
>> 	vector<string> a;
>> 	for (long int i=0; i<10000 ; ++i){
>> 		a.push_back("What do you know?");
>> 		a.push_back("so long...");
>> 		a.push_back("chicken crosses road");
>> 		a.push_back("fool");
>> 	}
>> 	set<string> b(a.begin(), a.end());
>> 	unique_copy(b.begin(), b.end(), ostream_iterator<string>(cout, "\n"));
>> }
>
> I think you probably want this C++ code instead:
>
> //C++
> #include <iostream>
> #include <string>
> #include <vector>
> #include <set>
> #include <algorithm>
> using namespace std;
>
> int main(){
>         vector<string> a;
>         a.reserve( 40000 );  //<------------------ note this change
>         for (long int i=0; i<10000 ; ++i){
>                 a.push_back("What do you know?");
>                 a.push_back("so long...");
>                 a.push_back("chicken crosses road");
>                 a.push_back("fool");
>         }
>         set<string> b(a.begin(), a.end());
>         unique_copy(b.begin(), b.end(), ostream_iterator<string>(cout,
> "\n"));
> }
>
> It will run a lot faster if it doesn't have to keep resizing
> the array.

I don't see why it should run a lot faster that way.

Appending elements to a vector with push_back takes amortized
constant time. In the example above, preallocating 40000 strings
saves (probably) math.log(40000, 2) reallocations of the vector's
storage along with the consequent copy-construction and
destruction of some fixed number of strings. Most of those
reallocations take place while the vector is still proportionally
quite small.

-- 
Neil Cerutti