Python Mystery Theatre -- Episode 3: Extend this
Chris Reedy
creedy at mitretek.org
Wed Jul 23 16:49:20 CEST 2003
I tried these out myself after making my guesses. Here's what I found:
Raymond Hettinger wrote:
> [snip]
>
> This time, the extra credit is for picking-out the three
> that surfaced as errors in my own, real code over
> the past few years (the example context below may be
> different, but the type of error occurred in real code).
>
> [snip]
>
> ACT I ---------------------
> def real(z):
> return hasattr(z, 'real') and z.real or z
> def imag(z):
> return hasattr(z, 'imag') and z.imag or 0
> for z in 3+4j, 5, 0+6j, 7.0, 8+0j, 9L:
> print real(z), imag(z)
I spotted the error in this one (I've been bitten by this more than
once) if z.real or z.imag is false, I get z or 0. That results is two
problems:
For 0+6j, the answer is 6j and 6.0, definitely not what was expected.
For 8+0j, the answer is 8.0 and 0, not 8.0 and 0.0. This is close to
what was expected and, if a bug at all, would be a rather subtle one.
I would certainly expect that Raymond's been bitten by this one. I would
guess that every experienced Python programmers been bitten by some form
of this one.
> ACT II ---------------------
> uniq = {}
> for k in (10, 'ten', 10+0j, u'ten', 'Ten', 't'+'en', 10.0):
> uniq(k) = 1
> print len(uniq)
I had to experiment with this one. I guessed 3, which turned out to be
right. I was a little surprised that 'ten' and u'ten' hash the same.
However, after thinking about that, I decided I was happy with that result.
I was more surprised that 10 and 10.0 came out the same. One of these
days I'll take the time to look up the hash algorithm for floats to see
how this was achieved.
> ACT III ---------------------
> s = 'abracadabra'
> for i in [3, 2, 1, 0]:
> print s[i:], s[-i:]
Got this one the first time. -0 == 0, so s[-0:] == s[0:] == s. I'll bet
that this is one that burned Raymond.
> ACT IV ---------------------
> pets = list('cat ')
> pets += 'dog '
> pets.extend('fish ')
> print pets + 'python'
I guessed ['c', 'a', 't', ' ', 'd', 'o', 'g', ' ', 'f', 'i', 's', 'h', '
', 'p', 'y', 't', 'h', 'o', 'n']. I tried it to discover that the print
statement at the end throws. I decided that not concatenating strings to
lists doesn't bother me since I would believe that this is an error
more often than not and pets + list('python') would hopefully make the
intent clear. On the other hand, if I saw pets = list('cat') in code I
was reviewing I suspect that I would want to assure myself that ['c',
'a', 't'] was what was intended and not ['cat'].
I also much bothered by pets += 'dog ' working but pets + 'python' not.
What's the justification for the checking in one place and not the other?
> INTERMISSION (with output included, oh yeah! ------------
>
>>>>import operator
>>>>1 - reduce(operator.add, [1e-7]* 10**7)
>
> 2.4983004554002264e-010
Round off error. Welcome to the world of floating point arithmetic!
> ACT V ---------------------
> class Bin:
> numitems = 0
> contents = []
>
> def add(self, item):
> self.numitems += 1
> self.contents += [item]
>
> laundry = Bin()
> groceries = Bin()
>
> laundry.add('shirt')
> groceries.add('bananas')
> groceries.add('nuts')
> laundry.add('socks')
> groceries.add('pretzels')
>
> print laundry.numitems, laundry.contents
> print groceries.numitems, groceries.contents
Learned something on this one. I caught that, as defined, numitems and
contents are attributes of the class Bin, rather than instances of Bin.
(The fix is to add the missing __init__ method.) I predicted that the
result of both print statements would be:
5 ['shirt', 'bananas', 'nuts', 'socks', 'pretzels']
When I tried it I got:
2 ['shirt', 'bananas', 'nuts', 'socks', 'pretzels']
3 ['shirt', 'bananas', 'nuts', 'socks', 'pretzels']
After thinking about it (and reviewing the Reference Manual), I realized
that self.contents += items does an in place update of Bin.contents, but
the augmented assignment self.numitems += 1, is the same as
self.numitems = self.numitems+1 (since there is no in place update for
integers or immutable objects in general), which has the result of
creating the attribute numitems on the laundry and groceries instances.
> ACT VI -----------------------------------------
> print "What is the technical name for this algorithm or transformation?"
> a = range(0, 100, 10)
> import random
> random.shuffle(a)
> print "Input:", a
> swaps = 0
> for i in range(len(a)):
> for j in range(i+1, len(a)):
> if a[i] > a[j]:
> i, j, a[i], a[j], swaps = j, i, a[j], a[i], swaps+1
> print "Output:", a
> print "Workload;", swaps
I went through a number of different answers on this one. First, there
was the indentation error at if a[i] > a[j]. I decided that was probably
a typo on Raymond's part.
The assignment i,j, ... = j,i, ... . Kept me guessing. Why do that? At
first I though it had no effect. (Note: that the corresponding
assignment in a C program which read:
for(i = 0; i < len(a); i++)
for(j = i+1; j < len(a); j++) ...
would require a lot more thought as to the likely result.
At this point I convinced myself that this was an interchange sort gone
wrong and would just produce garbage. When I tried it, I discovered that
the correct technical name for this program is the identity
transformation. That is, nothing happened.
Reexamining the code, I realized that flipping the two indices has the
effect of assigning the two array elements back to themselves, resulting
in no effect.
About this point in time, I also realized that the sort should work if
you take away the spurious assignments to i and j. That is,
a[i], a[j], swaps = a[j], a[i], swaps
will actually sort the list correctly. The correct technical name for
this is "sort by successive minima". This is a slightly different sort
from an interchange sort or a bubble sort, even though all three of
these sorts are O(n**2).
What's the real lesson here? I have two suggestions:
1. Watch out for side effects when doing compound assignments.
2. Never try to write your own sort when a.sort() is available.
----------------
OK, which three did Raymond personnally stumble over. I'll guess I, III,
and VI. Why VI? Well, because V, while subtle in some ways, doesn't look
to me like one you'd run into until you knew what you were doing, at
which point: why this missing __init__ method. VI looks like something
you might do by accident while trying to write a sort routine.
Chris
More information about the Python-list
mailing list