Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Python and STL efficiency

Thread Tools

Python and STL efficiency

Posts: n/a
Sorry, I did some miscalculation.... what a shame..... Removed) wrote:
> Pebblestone:
> >I heard that python's list is implemented as adjustable array.

> Correct, an array geometrically adjustable on the right.
> >Here's my lisp implementation:<

> What's the memory size of a before computing b? You can compare it with
> Python, that may need less memory (because the array contains
> pointers).
> >BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to me thousands of lines of errors and warnings.<

> Find a Win box It's already compiled for it (for Py 2.3, 2.4).
> >Your python's example (use direct index array index) of my corresponding lisp code works slower than the version which use 'append'.<

> For me (a slow PC) it's almost twice faster, computer life is usually
> complex.
> For me using the esplicit allocation + Psyco makes that program about 4
> times faster (from 8 to 2 seconds).
> >This let me think how python's list is implemented.<

> You also have to think how the * allocation is implemented and many
> other things
> The list implementation is rather readable, Python sources are online
> too.
> >Anyway, python's list is surprisingly efficient.<

> But its access isn't that fast Psyco helps.
> Bye,
> bearophile

Reply With Quote
Posts: n/a
> Sorry, I did some miscalculation.... what a shame.....

Don't worry.
For me using Py 2.4.3 those memory values are 4536 before and 20184 kb
after, it means a difference of 15648 kb, that equals to about 16023552
bytes, that equals to about 1000000 * 4 * 4. That means 4 bytes for
each string reference into the array. If you don't use Psyco the
starting memory value is quite lower.

If you don't use Psyco but you use the append, the values are 1384 and
18880, this means about 4.47 bytes / value, because python lists grow
geometrically, so there is some wasted space.

I find the memory used with PsList called from the Python script:


Reply With Quote
Posts: n/a
Ruby is also not far away

Here's my code:

require 'time'

def f
a = []
1000000.times do
a.push "What do you know"
a.push "so long ..."
a.push "chicken crosses road"
a.push "fool"
b = a.uniq
b.each do |x|
puts x

def f2
a =
1000000.times do |i|
a[i] = "What do you know"
a[i+1] = "so long ..."
a[i+2] = "chicken crosses road"
a[i+3] = "fool"
b = a.uniq
b.each do |x|
puts x

f_start =
f_end =

f2_start =
f2_end =

puts "f: Elapsed time: #{f_end - f_start} sec."
puts "f2: Elapsed time: #{f2_end - f_start} sec."


And the benchmark result:

What do you know
so long ...
chicken crosses road
What do you know
so long ...
chicken crosses road
f: Elapsed time: 3.600294 sec.
f2: Elapsed time: 11.182927 sec.


I like ruby because its purity.

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"));
> }
> #python
> def f():
> a = []
> for i in range(10000):
> a.append('What do you know')
> a.append('so long...')
> a.append('chicken crosses road')
> a.append('fool')
> b = set(a)
> for s in b:
> print s
> I was using and IDLE, respectively. I had expected C++ to be
> way faster. However, while the python code gave the result almost
> instantly, the C++ code took several seconds to run! Can somebody
> explain this to me? Or is there something wrong with my code?

Reply With Quote
Posts: n/a
---------------------------- C++ --------------------------
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <windows.h>

using namespace std;

int main()
DWORD ticks = ::GetTickCount();

const string s1("What do you know");
const string s2("So long...");
const string s3("chicken crosses road");
const string s4("fool");

typedef vector<const string*> str_vector_t;
typedef str_vector_t::iterator vec_iter;
typedef set<const string*> str_set_t;
typedef str_set_t::const_iterator set_iter;

const int size = 1000000;
str_vector_t vec;

for(int i = 0; i < size; ++i){

vec_iter new_end = unique(vec.begin(), vec.end());
str_set_t set_(vec.begin(), new_end);

for(set_iter it = set_.begin(); it != set_.end(); ++it){

return 0;

In MS VC+ 2005 in release configuration it gets the work done in 187

---------------- Python + Psyco----------------
def f():
a = []
for i in range(1000000):
a.append('What do you know')
a.append('so long...')
a.append('chicken crosses road')
b = set(a)
for s in b:
print s

import time
from time import clock

import psyco
f_start = clock()
f_end = clock()

print "Elapsed: %f seconds" % (f_end - f_start)

In Python in manages to do the same in 1.8 secs (psyco boosts it to
0.7; see below)
so long...
What do you know
chicken crosses road
Elapsed: 0.772899 seconds

Well, that's how it is in my book.


Reply With Quote

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
Vector and list iterators and efficiency Thormod Johansen C++ 2 03-26-2007 05:23 PM
stl questions: how can I compare 2 stl list? C++ 5 04-16-2006 09:57 PM
a stl map which use stl pair as the key C++ 2 02-22-2006 07:25 AM
Copy elements from one STL container to another STL container C++ 4 02-16-2006 05:03 PM
To STL or not to STL Allan Bruce C++ 41 10-17-2003 08:21 PM