On Mon, Jul 21, 2008 at 1:21 PM, Marc 'BlackJack' Rintsch
<[EMAIL PROTECTED]> wrote:
> On Mon, 21 Jul 2008 18:12:54 +0200, mk wrote:
>
>> Seriously, though, would there be any advantage in re-implementing
>> Python in e.g. C++?
>>
>> Not that current implementation is bad, anything but, but if you're not
>> careful, the fact that lists are implemented as C arrays can bite your
>> rear from time to time (it recently bit mine while using lxml). Suppose
>> C++ re-implementation used some other data structure (like linked list,
>> possibly with twists like having an array containing pointers to 1st
>> linked list elements to speed lookups up), which would be a bit slower
>> on average perhaps, but it would behave better re deletion?
Aside (actual reply below): at least for a sorted LL, you're basically
describing Henriksen's algorithm. They can asymptotically be faster,
based on amortized analysis, but they're somewhat more complicated to
implement.
>
> An operation that most people avoid because of the penalty of "shifting
> down" all elements after the deleted one. Pythonistas tend to build new
> lists without unwanted elements instead. I can't even remember when I
> deleted something from a list in the past.
>
> Ciao,
> Marc 'BlackJack' Rintsch
The other side of the equation though is the OO-overhead for C++
programs as compared to C. (A couple years ago we used an
instrumentation tool to check the instruction count for a simple hello
world program written in C (ie, main(){printf("Hello world!"); return
0;}) and Python (main(){cout<<"hello world"<<endl;return 0;}), and the
instruction count was significantly higher for C++. I expect any sort
of C++ objects you used to implement Python structures will be slower
than the equivalent in C. So even if writing it in C++ would reduce
the overhead for deleting from a list, I expect you would lose a lot
more.
--
http://mail.python.org/mailman/listinfo/python-list
