Try using a list instead of a vector for the C++ version.
Raj
On Tue, Jul 8, 2008 at 3:06 PM, mk <mrkafk@gmail.c omwrote:
--
"For him who has conquered the mind, the mind is the best of friends;
but for one who has failed to do so, his very mind will be the
greatest enemy."
Rajanikanth
Raj
On Tue, Jul 8, 2008 at 3:06 PM, mk <mrkafk@gmail.c omwrote:
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']
>
3.8792528100638 49
>
(Python 2.5, Windows)
>
Implementing the same algorithm in C++:
>
#include <vector>
#include <iostream>
#include <string>
>
using namespace std;
>
vector<stringmo ve_slice(vector <stringvec, int start, int stop, int dest)
{
int idx = stop - start;
vector<stringfr ag;
>
// 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<stringsl ice;
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(slic e, 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:
>
1.6097668837799 12
>
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.
>
>
--
>
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("m ove_slice.move_ slice(move_slic e.b, 4, 6, 7)", "import
>>>move_slice ")
>>>t.timeit()
>>>t = timeit.Timer("m ove_slice.move_ slice(move_slic e.b, 4, 6, 7)", "import
>>>move_slice ")
>>>t.timeit()
>
(Python 2.5, Windows)
>
Implementing the same algorithm in C++:
>
#include <vector>
#include <iostream>
#include <string>
>
using namespace std;
>
vector<stringmo ve_slice(vector <stringvec, int start, int stop, int dest)
{
int idx = stop - start;
vector<stringfr ag;
>
// 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<stringsl ice;
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(slic e, 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("m ove_slice.move_ slice(move_slic e.b, 6, 7, 7)", "import
>>>move_slice ")
>>>t.timeit()
>>>move_slice ")
>>>t.timeit()
>
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.
>
>
--
>
--
"For him who has conquered the mind, the mind is the best of friends;
but for one who has failed to do so, his very mind will be the
greatest enemy."
Rajanikanth