get method

[Ross]

I am teaching myself Python by going through Allen Downing's "Think
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:
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.

 

[James Mills]

I am teaching myself Python by going through Allen Downing's "Think
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:
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?

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]

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:
.... 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)
....!: *
: *
e: *
d: *
H: *
l: ***
o: **
r: *
W: *

cheers
James

 

[Ross]

... 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
(e-mail address removed)

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]

I just gave you a hint

Ross:

This exercise is a simple exercise dealing with:
* assignments
* functions
* dictionaries
* looping
* attributes and methods
.... d = dict()
.... for c in s:
.... d[c] = d.get(c, 0) + 1
.... return d
....{'!': 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]

... 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
(e-mail address removed)

I realize the code isn't counting, but how am I to do this without using
an if statement as the problem instructs?

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.

 

[Aaron Brady]

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
(e-mail address removed)

I realize the code isn't counting, but how am I to do this without using
an if statement as the problem instructs?

snip
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]

James Mills schreef:

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]

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]

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:
{'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}

 

[James Mills]

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]

(snip)


What complexity is this ?

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]

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]

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 ?

What set module?
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?

 

[MRAB]

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 ?

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.

 

[James Mills]

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