From: Josh C. <jc...@nc...> - 2007-05-19 05:07:13
|
On Fri, 18 May 2007, gga wrote: > > Josh Cherry wrote: >>> >>> it is much faster. Of course, calling end() *should* be constant time. >>> > > In C++, maybe, where the compiler may be able to inline the call > completely. When you bind it to a scripting language, end() is always a > function call. This slowdown is unavoidable. Inlining has nothing to do with it, and the O(n) or O(n^2) slowdown is not unavoidable. The time for an end() call should not grow with the number of elements in the container. Of course calling it from a scripting language will be slower than a call in C++, but it should still be O(1). It is O(n) or O(n^2) because of an unnecessary check of every element. > I should also point out that this: > >>> cont = pystl.pylist(xrange(n)) > > will indeed do a dummy check on each element of the range when *FILLING* > the container, not when iterating thru it. Again, this check cannot be > avoided. > > And, it will also create a temporary container BEFORE calling the copy > constructor of the container (which in turn has to copy the stuff again). > Take this out of the timing and you'll see the numbers perform much better. That has complexity O(n), no higher than in C++, though of course with a larger constant factor. Constructing the container is not the slow part in the Python examples we've been discussing (otherwise, eliminating the call to end() every iteration wouldn't speed things up drastically). I haven't looked carefully at your ruby results, but the ruby stl support may well be different from the Python stl support with respect to the unnecessary check. Josh |