On Tuesday 26 January 2010, Steve Howell wrote:
> Here are the benefits of an O(1) implementation.
[...]
> Did I leave anything out?
Good summary, Steve, thanks!
Anyway, you left two out:
* Inserting at the front gets the same complexity as inserting at the back.
* Inserting and erasing anywhere in the middle can memmove() the smaller
tail, so it changes from O(N) to O(N/2).
Finally, if you drop the invariant first<=last, you can simply wrap around the
pointers. This allows creating a producer/consumer queue which never needs to
move its content.
Cheers!
Uli
**************************************************************************************
Sator Laser GmbH, Fangdieckstraße 75a, 22547 Hamburg, Deutschland
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
**************************************************************************************
Visit our website at <http://www.satorlaser.de/>
**************************************************************************************
Diese E-Mail einschließlich sämtlicher Anhänge ist nur für den Adressaten
bestimmt und kann vertrauliche Informationen enthalten. Bitte benachrichtigen
Sie den Absender umgehend, falls Sie nicht der beabsichtigte Empfänger sein
sollten. Die E-Mail ist in diesem Fall zu löschen und darf weder gelesen,
weitergeleitet, veröffentlicht oder anderweitig benutzt werden.
E-Mails können durch Dritte gelesen werden und Viren sowie nichtautorisierte
Änderungen enthalten. Sator Laser GmbH ist für diese Folgen nicht
verantwortlich.
**************************************************************************************
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
