get method

[MRAB]

James Mills wrote:
> On Tue, Dec 30, 2008 at 7:10 PM, Roel Schroeven
> <rschroev_nospam_ml at 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}