Out of curiosity I decided to make some speed comparisons of the same
algorithm in Python and C++. Moving slices of lists of strings around
seemed like a good test case.
Python code:
def move_slice(list_arg, start, stop, dest):
frag = list_arg[start:stop]
if dest > stop:
idx = dest - (stop - start)
else:
idx = dest
del list_arg[start:stop]
list_arg[idx:idx] = frag
return list_arg
b = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
>>> import timeit
>>> t = timeit.Timer("move_slice.move_slice(move_slice.b, 4, 6, 7)",
"import move_slice")
>>> t.timeit()
3.879252810063849
(Python 2.5, Windows)
Implementing the same algorithm in C++:
#include <vector>
#include <iostream>
#include <string>
using namespace std;
vector<string> move_slice(vector<string> vec, int start, int stop, int dest)
{
int idx = stop - start;
vector<string> frag;
// copy a fragment of vector
for (idx = start; idx < stop; idx++)
frag.push_back(vec.at(idx));
if( dest > stop)
idx = dest - (stop - start);
else
idx = dest;
// delete the corresponding fragment of orig vector
vec.erase( vec.begin() + start, vec.begin() + stop);
// insert the frag in proper position
vec.insert( vec.begin() + idx, frag.begin(), frag.end());
return vec;
}
int main(int argc, char* argv)
{
vector<string> slice;
string u = "abcdefghij";
int pos;
for (pos = 0; pos < u.length(); pos++)
slice.push_back(u.substr(pos,1));
int i;
for (i = 0; i<1000000; i++)
move_slice(slice, 4, 6, 7);
}
Now this is my first take at vectors in C++, so it's entirely possible
that an experienced coder would implement it in more efficient way.
Still, vectors of strings seemed like a fair choice - after all, Python
version is operating on similarly versatile objects.
But I was still rather surprised to see that C++ version took 15% longer
to execute!
(vector, 4, 6, 7)
$ time slice
real 0m4.478s
user 0m0.015s
sys 0m0.031s
Compiler: MinGW32/gcc 3.4.5, with -O2 optimization (not cygwin's gcc,
which for some reason seems to produce sluggish code).
When I changed moving the slice closer to the end of the list / vector,
Python version executed even faster:
>>> t = timeit.Timer("move_slice.move_slice(move_slice.b, 6, 7, 7)",
"import move_slice")
>>> t.timeit()
1.609766883779912
C++:
(vector, 6, 7, 7)
$ time slice.exe
real 0m3.786s
user 0m0.015s
sys 0m0.015s
Now C++ version took over twice the time to execute in comparison to
Python time!
Am I comparing apples to oranges? Should the implementations be
different? Or does the MinGW compiler simply suck?
Note: it appears that speed of Python lists falls down quickly the
closer to the list beginning one deletes or inserts elements. C++
vectors do not seem to be as heavily position-dependent.
--
http://mail.python.org/mailman/listinfo/python-list
