[Top][All Lists]

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

Re: HTTP GET Shakespeare

From: umano
Subject: Re: HTTP GET Shakespeare
Date: Sat, 22 Aug 2015 16:36:41 -0500
User-agent: Roundcube Webmail/1.0.6

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:

Python program:

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".


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.

reply via email to

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