get method
Ross
Python." I have come across what should be a simple exercise, but I am
not getting the correct answer. Here's the exercise:
Given:
def histogram(s):
d = dict()
for c in s:
if c not in d:
d[c] = 1
else:
d[c] += 1
return d
Dictionaries have a method called get that takes a key and a default
value. If the key appears in the dictionary, get returns the
corresponding value; otherwise it returns the default value. For
example:
>>> h = histogram('a')
>>> print h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0
Use get to write histogram more concisely. You should be able to
eliminate the if statement.
Here's my code:
def histogram(s):
d = dict()
for c in s:
d[c]= d.get(c,0)
return d
This code returns a dictionary of all the letters to any string s I
give it but each corresponding value is incorrectly the default of 0.
What am I doing wrong?
Steven D'Aprano
> Here's my code:
>
> def histogram(s):
> d = dict()
> for c in s:
> d[c]= d.get(c,0)
> return d
>
> This code returns a dictionary of all the letters to any string s I give
> it but each corresponding value is incorrectly the default of 0. What am
> I doing wrong?
You're forgetting to increase the count each time you see a letter:
* Look up the letter c in the dict, and call it count;
* If c isn't found in the dict, use 0 as the count.
* Set the value to count.
But at no point do you increase count.
--
Steven
Scott David Daniels
> ... Use get to write histogram more concisely. You should be able to
> eliminate the if statement.
>
> d = dict()
> for c in s:
> d[c]= d.get(c,0)
> return d
>
> This code returns a dictionary of all the letters to any string s I
> give it but each corresponding value is incorrectly the default of 0.
> What am I doing wrong?
How is this code supposed to count?
--Scott David Daniels
Scott....@Acm.Org
James Mills
Ross, the others have informed you that you are not
actually incrementing the count. I'll assume you've
fixed your function now :) ... I want to show you a far
simpler way to do this which takes advantage of
Python's list comprehensions and mappings (which are
really what dictionaries are):
>>> s = "James Mills and Danielle Van Sprang"
>>> dict([(k, len([x for x in s if x == k])) for k in s])
{'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}
>>>
Let us know when you get to the "List Comprehension"
section - They are very powerful - As as Generators
and Generator Expressions.
Have fun learning Python,
cheers
James
James Mills
<prol...@shortcircuit.net.au> wrote:
> Ross, the others have informed you that you are not
> actually incrementing the count. I'll assume you've
> fixed your function now :) ... I want to show you a far
> simpler way to do this which takes advantage of
> Python's list comprehensions and mappings (which are
> really what dictionaries are):
>
>>>> s = "James Mills and Danielle Van Sprang"
>>>> dict([(k, len([x for x in s if x == k])) for k in s])
> {'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}
>>>>
>
> Let us know when you get to the "List Comprehension"
> section - They are very powerful - As as Generators
> and Generator Expressions.
>
> Have fun learning Python,
Also, here's a nice function:
>>> def histogram(s):
... d = dict([(k, len([x for x in s if x == k])) for k in s])
... for k, v in d.iteritems():
... print "%s: %s" % (k, "*" * v)
...
>>> histogram("Hello World!")
!: *
: *
e: *
d: *
H: *
l: ***
o: **
r: *
W: *
cheers
James
Ross
I realize the code isn't counting, but how am I to do this without
using an if statement as the problem instructs?
James Mills
> I realize the code isn't counting, but how am I to do this without
> using an if statement as the problem instructs?
I just gave you a hint :)
cheers
James
James Mills
<prol...@shortcircuit.net.au> wrote:
> On Tue, Dec 30, 2008 at 11:38 AM, Ross <ross...@gmail.com> wrote:
>> using an if statement as the problem instructs?
>
Ross:
This exercise is a simple exercise dealing with:
* assignments
* functions
* dictionaries
* looping
* attributes and methods
>>> def histogram(s):
... d = dict()
... for c in s:
... d[c] = d.get(c, 0) + 1
... return d
...
>>> histogram("Hello World!")
{'!': 1, ' ': 1, 'e': 1, 'd': 1, 'H': 1, 'l': 3, 'o': 2, 'r': 1, 'W': 1}
Note the 3rd line of the function ?
1. Get the value (with a default of 0) of the key c from the dictionary d
2. Add 1 to this value
3. Store in d with key c
Hope this helps.
cheers
James
Steven D'Aprano
You don't increment a value using if. This would be silly:
# increment x
if x == 0:
x = 1
elif x == 1:
x = 2
elif x == 2:
x = 3 # can I stop yet?
else:
x = "I can't count that high!"
You increment a value using + 1:
x = x + 1
or
x += 1
In the original code, the program did this:
def histogram(s):
d = dict()
for c in s:
if c not in d:
d[c] = 1
else:
d[c] += 1
* look for c in the dict
* if it isn't there, set d[c] to 1
* but if it is there, increment d[c] by 1
Your attempt was quite close:
def histogram(s):
d = dict()
for c in s:
d[c]= d.get(c,0)
return d
which is pretty much the same as:
* set d[c] to whatever d[c] already is, or 0 if it isn't already there.
So what you need is:
* set d[c] to whatever d[c] already is plus one, or 0 plus one if it
isn't already there.
It's a two character change to one line. Let us know if you still can't
see it.
--
Steven
Aaron Brady
cybersource.com.au> wrote:
> On Mon, 29 Dec 2008 17:38:36 -0800, Ross wrote:
> > On Dec 29, 8:07 pm, Scott David Daniels <Scott.Dani...@Acm.Org> wrote:
> >> Ross wrote:
> >> > ... Use get to write histogram more concisely. You should be able to
> >> > eliminate the if statement.
>
> >> > def histogram(s):
> >> > d = dict()
> >> > for c in s:
> >> > d[c]= d.get(c,0)
> >> > return d
>
> >> > This code returns a dictionary of all the letters to any string s I
> >> > give it but each corresponding value is incorrectly the default of 0.
> >> > What am I doing wrong?
>
> >> How is this code supposed to count?
>
> >> --Scott David Daniels
> >> Scott.Dani...@Acm.Org
>
> > I realize the code isn't counting, but how am I to do this without using
> > an if statement as the problem instructs?
> So what you need is:
>
> * set d[c] to whatever d[c] already is plus one, or 0 plus one if it
> isn't already there.
>
> It's a two character change to one line. Let us know if you still can't
> see it.
That's actually really sophisticated. Steven is being really clever
here, by writing a number in an unusual way.
He said:
* set d[c] to whatever d[c] already is plus one, or 0 plus one if it
isn't already there.
It is the same as:
* set d[c] to whatever d[c] already is plus one, or one if it
isn't already there.
Side-by-side. Perhaps you will learn his secret someday. It has to
do with 0+1=1.
Armed with it, he has:
something something +1, something something something +1
Which brings us (to):
( something something, something something something ) +1
Three cheers for thinking.
Roel Schroeven
> Ross, the others have informed you that you are not
> actually incrementing the count. I'll assume you've
> fixed your function now :) ... I want to show you a far
> simpler way to do this which takes advantage of
> Python's list comprehensions and mappings (which are
> really what dictionaries are):
>
>>>> s = "James Mills and Danielle Van Sprang"
>>>> dict([(k, len([x for x in s if x == k])) for k in s])
> {'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}
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.
--
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
-- Isaac Asimov
Roel Schroeven
James Mills
<rschroev_...@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.
cheers
James
MRAB
> On Tue, Dec 30, 2008 at 7:10 PM, Roel Schroeven
> <rschroev_...@fastmail.fm> wrote:
>> 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.
>
>
> I wonder if there is a way to implement
> the same thing with close to O(n)
> complexity using list/dict comprehensions.
>
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,
James Mills
(snip)
> A while back I posted a Python implementation of 'bag' (also called a
> multiset). The code would then become something like:
What complexity is this ?
cheers
James
John Machin
wrote:
The "armchair philosopher" approach: bag has an iteritems method so
it's probably using a dict internally in which case a reasonable
assumption is that the counting is implemented efficiently ... guess:
bag(iterable) is O(len(iterable))
The "crawl through the shrubbery looking for evidence" approach
stumbles on the actual code:
def __init__(self, iterable=None):
self._items = {}
if iterable is not None:
for item in iterable:
self._items[item] = self._items.get(item, 0) + 1
confirming the guess.
James Mills
(snip)
> The "crawl through the shrubbery looking for evidence" approach
> stumbles on the actual code:
Yes I found his implementation soon after :)
Not bad actually... I wonder why bag() isn't
shipped with the std lib - perhaps in teh set
module ?
--JamesMills
Steven D'Aprano
What set module?
>>> import set
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ImportError: No module named set
Adding a multi-set or bag class to the collections module would be a good
idea though. Perhaps you should put in a feature request?
--
Steven
MRAB
> On Wed, Dec 31, 2008 at 10:22 AM, John Machin <sjma...@lexicon.net> wrote:
> (snip)
>
>> stumbles on the actual code:
>
> Not bad actually... I wonder why bag() isn't
> shipped with the std lib - perhaps in teh set
> module ?
>
involving dict or defaultdict are suggested, and I think that a 'bag'
class would be useful. The 'set' class was introduced first in a module,
but it soon became a builtin. My posting was intended a possible
reference implementation.
James Mills
<st...@remove-this-cybersource.com.au> wrote:
> What set module?
Sorry I must have meant the collections module :)
> Adding a multi-set or bag class to the collections module would be a good
> idea though. Perhaps you should put in a feature request?
:) Perhaps I will.
cheers
James
James Mills
> Occasionally someone posts here wanting to count items and solutions
> involving dict or defaultdict are suggested, and I think that a 'bag' class
> would be useful. The 'set' class was introduced first in a module, but it
> soon became a builtin. My posting was intended a possible reference
> implementation.
I think it would be a nice addition to the collections module.
cheers
James