James Mills wrote:
On Tue, Dec 30, 2008 at 7:10 PM, Roel Schroeven
<rschroev_nospam...@fastmail.fm> wrote:
Hm, you just changed an O(n) algorithm to an O(n**2) algorithm. No big
deal for short strings, but try your solution on a string with length
10000 and see the difference. On my computer the O(n) version takes
0.008 seconds, while your version takes 8.6 seconds. That's 1000 times
slower.
Yes you are right :) Sadly :/
I wonder if there is a way to implement
the same thing with close to O(n)
complexity using list/dict comprehensions.
A while back I posted a Python implementation of 'bag' (also called a
multiset). The code would then become something like:
>>> s = "James Mills and Danielle Van Sprang"
>>> dict(bag(s).iteritems())
{'a': 5, ' ': 5, 'e': 3, 'd': 1, 'g': 1, 'i': 2, 'm': 1, 'J': 1, 'M': 1,
'l': 4, 'n': 4, 'p': 1, 's': 2, 'r': 1, 'V': 1, 'S': 1, 'D': 1}
--
http://mail.python.org/mailman/listinfo/python-list
