Python and STL efficiency

[Pebblestone]

Sorry, I did some miscalculation.... what a shame.....

 

[bearophileHUGS]

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

 

[Pebblestone]

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 = "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.

 

[andrei.zavidei]

---------------------------- 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