Re: HTTP GET Shakespeare

[umano]

On 2015-08-22 15:18, Andreas Rottmann wrote:
> address@hidden writes:
>
> > Hello list, I need some help.
> >
> > I'm following a Computer Science course material in Python and then
> > try to implement the examples and exercises in Guile Scheme.
> >
> > Currently I'm working on a small program to get a text document from
> > the Web and do some string operations with the content, but my
> > implementation in Guile takes about 5-7 minutes to finish, while the
> > Python version takes 6-8 seconds. Also, the printed results are
> > different, but I'm more concerned about the time issue right now.
> >
> > Could you point me to possible mistakes I'm making here?
> >
> > Guile Scheme program:
> > https://gist.github.com/umanomata/99f103ed686acd523d9e
> >
> > Python program:
> > https://gist.github.com/umanomata/1dbb3beb2ce19f09fcee
> 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
>
> Regards, Rotty

Well, I'm embarrassed now. I should have looked what O(n^2) meant. It's 
just that I'm a noob and didn't even know anything about the subject of 
order of complexity :)

I'll read about hash tables then.

Thank you very much Andreas and Ralf.