Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

Python and STL efficiency

 
 
Pebblestone
Guest
Posts: n/a
 
      08-25-2006
Sorry, I did some miscalculation.... what a shame.....




http://www.velocityreviews.com/forums/(E-Mail 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
 
 
 
 
bearophileHUGS@lycos.com
Guest
Posts: n/a
 
      08-25-2006
Pebblestone:
> 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:
http://www.sysinternals.com/Utilities/PsList.html

Bye,
bearophile

 
Reply With Quote
 
 
 
 
Pebblestone
Guest
Posts: n/a
 
      08-26-2006
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"
end
b = a.uniq
b.each do |x|
puts x
end
end

def f2
a = Array.new(4000000)
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"
end
b = a.uniq
b.each do |x|
puts x
end
end


f_start = Time.now
f
f_end = Time.now

f2_start = Time.now
f2
f2_end = Time.now

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
fool
What do you know
so long ...
chicken crosses road
fool
nil
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 VC++.net 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
 
andrei.zavidei@gmail.com
Guest
Posts: n/a
 
      08-27-2006
---------------------------- 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;
vec.reserve(size*4);

for(int i = 0; i < size; ++i){
vec.push_back(&s1);
vec.push_back(&s2);
vec.push_back(&s3);
vec.push_back(&s4);
}

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){
cout<<*it<<endl;
}
cout<<::GetTickCount()-ticks<<endl;

return 0;
}

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

---------------- 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')
a.append('fool')
b = set(a)
for s in b:
print s

import time
from time import clock

import psyco
psyco.full()
f_start = clock()
f()
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
fool
chicken crosses road
Elapsed: 0.772899 seconds


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

Regards,
Andrei

 
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
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? silverburgh.meryl@gmail.com C++ 5 04-16-2006 09:57 PM
a stl map which use stl pair as the key Allerdyce.John@gmail.com C++ 2 02-22-2006 07:25 AM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
To STL or not to STL Allan Bruce C++ 41 10-17-2003 08:21 PM



Advertisments