[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: HTTP GET Shakespeare

From: Ludovic Courtès
Subject: Re: HTTP GET Shakespeare
Date: Sat, 29 Aug 2015 22:49:07 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)

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]
> 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.)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]