Re: Python and STL efficiency
I tested in Common Lisp and compared the result with python.
My PC is: 3.6GH Pentium4
My OS is: Ubuntu 6.06 i386
My lisp implementation is SBCL 0.9.8 for i386
My python's version is: V2.4.3
Both implementations were installed via apt-get install.
Here's my Lisp program:
++
;;; from slow to fast implementation
(proclaim '(optimize (speed 3) (debug 0) (safety 0) (space 0)))
(defun test1 ()
(let ((a (make-array 0 :adjustable t :fill-pointer 0))
(b nil))
(dotimes (i 100)
(progn
(vector-push-extend "What do you know" a)
(vector-push-extend "so long ..." a)
(vector-push-extend "chicken crosses road" a)
(vector-push-extend "fool" a)))
(setf b (remove-duplicates a :test #'string-equal))
(map 'vector #'print b)))
(defun test2 ()
(let ((a (make-array 0 :adjustable t :fill-pointer 0))
(b nil))
(dotimes (i 100)
(progn
(vector-push-extend "What do you know" a)
(vector-push-extend "so long ..." a)
(vector-push-extend "chicken crosses road" a)
(vector-push-extend "fool" a)))
(setf b (remove-duplicates a :test #'eq))
(map 'vector #'print b)))
(defun test3 ()
(let ((a (make-array 400 :element-type 'string
:adjustable nil
:fill-pointer 0))
(b nil))
(dotimes (i 100)
(progn
(vector-push "What do you know" a)
(vector-push "so long ..." a)
(vector-push "chicken crosses road" a)
(vector-push "fool" a)))
(setf b (remove-duplicates a))
(map 'vector #'print b)))
(defun test4 ()
(let ((a (make-array 400 :element-type 'string
:adjustable nil))
(b nil))
(dotimes (i 100)
(progn
(let ((j (1- (* 4 i
(setf (aref a (incf j)) "What do you know")
(setf (aref a (incf j)) "so long ...")
(setf (aref a (incf j)) "chicken crosses road")
(setf (aref a (incf j)) "fool"
(setf b (remove-duplicates a))
(map 'vector #'print b)))
+++
1. When using string equal comparator (test #1), the speed slows down
dramatically. 1.93 -> 9.35
2. It seems that append(vector-push) in lisp costs much more than
direct access via index.
Here's my benchmark result:
+++
#1
(time (test1))
"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
9.346 seconds of real time
9.020564 seconds of user run time
0.328021 seconds of system run time
0 page faults and
457,565,688 bytes consed.
#2
(time (test2))
"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
1.931 seconds of real time
1.884118 seconds of user run time
0.048003 seconds of system run time
0 page faults and
49,561,312 bytes consed.
#3
(time (test3))
"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
1.721 seconds of real time
1.704107 seconds of user run time
0.016001 seconds of system run time
0 page faults and
32,012,040 bytes consed.
#4
(time (test4))
"What do you know"
"so long ..."
"chicken crosses road"
"fool"
Evaluation took:
0.843 seconds of real time
0.824051 seconds of user run time
0.020001 seconds of system run time
0 page faults and
32,012,040 bytes consed.
+++
Here's my python's code:
ef f():
a = []
for i in range(100):
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
f_start = clock()
f()
f_end = clock()
print "Elapsed: %f seconds" % (f_end - f_start)
And benchmark result:
python -O test.py
so long...
What do you know
fool
chicken crosses road
Elapsed: 1.26 seconds
Oops, Python beat native-compiled lisp code.
++
Any way,
MY CONCLUSION is: C++ is not the right model for symbolic computation.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
> But note this a list (that is an array, a list is a different data > structure) of python becomes filled with pointers. I don't know what > your CL does exactly. I heard that python's list is implemented as adjustable array. Here's my lisp implementation: ++ (defun test-list () (let ((a nil) (b nil)) (dotimes (i 100) (progn (push "What do you know" a) (push "so long ..." a) (push "chicken crosses road" a) (push "fool" a))) (setf b (remove-duplicates a)) (map 'list #'print b))) + And the benchmark result: (time (test-list)) "fool" "chicken crosses road" "so long ..." "What do you know" Evaluation took: 2.88 seconds of real time 2.744172 seconds of user run time 0.136009 seconds of system run time 0 page faults and 74,540,392 bytes consed. ++ BTW, I couldn't install psyco on my system (ubuntu), gcc just prompt to me thousands of lines of errors and warnings. [EMAIL PROTECTED] wrote: > Pebblestone: > > (defun test4 () > > (let ((a (make-array 400 :element-type 'string > >:adjustable nil)) > > (b nil)) > > (dotimes (i 100) > > (progn > > (let ((j (1- (* 4 i > > (setf (aref a (incf j)) "What do you know") > > (setf (aref a (incf j)) "so long ...") > > (setf (aref a (incf j)) "chicken crosses road") > > (setf (aref a (incf j)) "fool" > > (setf b (remove-duplicates a)) > > (map 'vector #'print b))) > > > That test4 function can be compared to this one, with explicit > preallocation (and xrange instead of range!): > > def f2(): > n = 100 > a = [None] * n * 4 > for i in xrange(0, n*4, 4): > a[i] = 'What do you know' > a[i+1] = 'so long...' > a[i+2] = 'chicken crosses road' > a[i+3] = 'fool' > for s in set(a): > print s > > But note this a list (that is an array, a list is a different data > structure) of python becomes filled with pointers. I don't know what > your CL does exactly. > > I can also suggest you to use Psyco too here > (http://psyco.sourceforge.net/): > > import psyco > psyco.bind(f2) > > It makes that f2 more than twice faster here. > > Bye, > bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
Oh, I forgot. Your python's example (use direct index array index) of my corresponding lisp code works slower than the version which use 'append'. This let me think how python's list is implemented. Anyway, python's list is surprisingly efficient. [EMAIL PROTECTED] wrote: > Pebblestone: > > (defun test4 () > > (let ((a (make-array 400 :element-type 'string > >:adjustable nil)) > > (b nil)) > > (dotimes (i 100) > > (progn > > (let ((j (1- (* 4 i > > (setf (aref a (incf j)) "What do you know") > > (setf (aref a (incf j)) "so long ...") > > (setf (aref a (incf j)) "chicken crosses road") > > (setf (aref a (incf j)) "fool" > > (setf b (remove-duplicates a)) > > (map 'vector #'print b))) > > > That test4 function can be compared to this one, with explicit > preallocation (and xrange instead of range!): > > def f2(): > n = 100 > a = [None] * n * 4 > for i in xrange(0, n*4, 4): > a[i] = 'What do you know' > a[i+1] = 'so long...' > a[i+2] = 'chicken crosses road' > a[i+3] = 'fool' > for s in set(a): > print s > > But note this a list (that is an array, a list is a different data > structure) of python becomes filled with pointers. I don't know what > your CL does exactly. > > I can also suggest you to use Psyco too here > (http://psyco.sourceforge.net/): > > import psyco > psyco.bind(f2) > > It makes that f2 more than twice faster here. > > Bye, > bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
Here's the result: What do you know fool chicken crosses road f elapsed: 1.26 seconds f2 elapsed 2.11 seconds [EMAIL PROTECTED] wrote: > Pebblestone: > > (defun test4 () > > (let ((a (make-array 400 :element-type 'string > >:adjustable nil)) > > (b nil)) > > (dotimes (i 100) > > (progn > > (let ((j (1- (* 4 i > > (setf (aref a (incf j)) "What do you know") > > (setf (aref a (incf j)) "so long ...") > > (setf (aref a (incf j)) "chicken crosses road") > > (setf (aref a (incf j)) "fool" > > (setf b (remove-duplicates a)) > > (map 'vector #'print b))) > > > That test4 function can be compared to this one, with explicit > preallocation (and xrange instead of range!): > > def f2(): > n = 100 > a = [None] * n * 4 > for i in xrange(0, n*4, 4): > a[i] = 'What do you know' > a[i+1] = 'so long...' > a[i+2] = 'chicken crosses road' > a[i+3] = 'fool' > for s in set(a): > print s > > But note this a list (that is an array, a list is a different data > structure) of python becomes filled with pointers. I don't know what > your CL does exactly. > > I can also suggest you to use Psyco too here > (http://psyco.sourceforge.net/): > > import psyco > psyco.bind(f2) > > It makes that f2 more than twice faster here. > > Bye, > bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
> 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). Here's the memory usage: 1) before the loop ( fully garbage collected) 29,052,560 bytes, 757,774 objects. 2) after the loop 103,631,952 bytes, 8,760,495 objects. It seems A has consumed 74M bytes, 8bytes each cell. That make sense because a cell in list consists of 2 pointers, (car cdr), and an mem address is 32 bit. [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
Sorry, I did some miscalculation what a shame. [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python and STL efficiency
Ruby is also not far away :-)
Here's my code:
require 'time'
def f
a = []
100.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(400)
100.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. :p
Licheng Fang wrote:
> Hi, I'm learning STL and I wrote some simple code to compare the
> efficiency of python and STL.
>
> //C++
> #include
> #include
> #include
> #include
> #include
> using namespace std;
>
> int main(){
> vector a;
> for (long int i=0; i<1 ; ++i){
> a.push_back("What do you know?");
> a.push_back("so long...");
> a.push_back("chicken crosses road");
> a.push_back("fool");
> }
> set b(a.begin(), a.end());
> unique_copy(b.begin(), b.end(), ostream_iterator(cout, "\n"));
> }
>
> #python
> def f():
> a = []
> for i in range(1):
> 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?
--
http://mail.python.org/mailman/listinfo/python-list
