Ralf Mattes <r...@seid-online.de> skribis: > On Sat, Aug 22, 2015 at 10:18:19PM +0200, Andreas Rottmann wrote: >> um...@openmailbox.org writes:
[...] >> There's a difference in algorithmic complexity here: in Scheme, you use >> SRFI-1's "delete-duplicates", which is noted to be O(n^2) complexity in >> the SRFI-1 specification[0]. In Python, you use set(), which is probably >> implemented using a hash table, yielding roughly O(1) complexity. Since >> your input set is large, it would be better to feed the read words into >> a hash table, instead of using a list and SRFI-1 "delete-duplicates". >> >> [0] http://srfi.schemers.org/srfi-1/srfi-1.html#delete-duplicates > > Of course, that leaves us with the question why code that was explicitly moved > from scheme to the c-level "... so that using srfi-1 wouldn't have performance > penalties" uses such a problematic algorithm. That’s mostly historical, but in the pre-2.0 days, that could make a difference for small lists (one shouldn’t use it for potentially large lists anyway.) Ludo’.
