Re: HTTP GET Shakespeare

[Ludovic Courtès]

Ralf Mattes <address@hidden> skribis:

> On Sat, Aug 22, 2015 at 10:18:19PM +0200, Andreas Rottmann wrote:
>> address@hidden 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’.