Re: [Tutor] counter not working in Quick Sort script
That make sense, thank you. I changed the quick_sort() to
def quick_sort(A, start, stop, count):
if start < stop:
# increment count by length of partition less the pivot
count += (stop - start - 1)
print(count)
split = partition(A, start, stop)
# recursively sort lower partition
left = quick_sort(A, start, split-1, count)
if left:
count = left
# recursively count upper partition
right = quick_sort(A, split, stop, count)
if right:
count = right
return count
Yes, the sorting worked on all the *lists I tested.* For counting comparisons,
I used a sorted list with a known number of comparisons to be able check the
accumulator variable.
-Patricia
On Thu, 10/29/15, Alan Gauld wrote:
Subject: Re: [Tutor] counter not working in Quick Sort script
To: tutor@python.org
Date: Thursday, October 29, 2015, 9:12 PM
On 29/10/15 19:11, Patti
Scott via Tutor wrote:
Caveat: I didn't check the algorithms for
correctness,
I'll just take your word
for that.
> My
accumulator variable to count the number of comparisons
returns nonsense.
> def
quick_sort(A, start, stop, count):
>
if start < stop:
> #
increment count by length of partition less the pivot
> count += (stop - start -
1)
> print(count)
> split = partition(A, start,
stop)
>
>
# recursively sort lower partition
>
quick_sort(A, start, split-1, count)
> # recursively count upper
partition
> quick_sort(A,
split, stop, count)
>
> return count
Notice that you only set count
once at the top of the function.
What the
recursive instances of the function do is irrelevant
because you don't use their return values.
So the return value
of this function is
always (count + stop - start -1) for the
initial invocation value of count.
I suspect you really want to
do something to count based on
the returns
from the recursive calls too.
> def main():
>
unsorted = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
This looks very sorted to me? Is that
correct?
> count
= quick_sort(unsorted, 0, len(unsorted), 0)
count should return
0+len()-0-1 -> len-1 = 7
> print(unsorted)
> print("There are {}
comparisons.".format(count))
>
> main()
>
>
> This code is giving
me this output:
>
>
➜ algorithms python3 quick_sort_first.py
> 7
This is the outer
functions count
> 13
> 18
> 22
> 25
> 27
> 28
> 28
These are the recursive values
of count which are
invisible to the outer
invocation
> [1, 2, 3,
4, 5, 6, 7, 8]
This is the
sorted result
> There
are 7 comparisons.
And this
reflects the outer value of count again.
Your code does exactly what you told it to
do.
Your problem is that you are not using
the returned
counts from the recursive
calls.
--
Alan G
Author of the Learn to
Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription
options:
https://mail.python.org/mailman/listinfo/tutor
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
[Tutor] counter not working in Quick Sort script
Mac OS 10.10
Python 3.4.3
I self-study Python and am using it for a Coursera algorithm class.
Hi! My script sorts correctly on all my test arrays. My accumulator variable
to count the number of comparisons returns nonsense. I'm counting the (length
- one) of each sublist that will be sorted in place, not the individual
comparisons. I put in a print statement for the count variable, and the
expected values print, but the function seems to be returning the first
increment of the count variable instead of the final value. I reread on the
difference between print and return, but I haven't figured this out yet. I
think I'm doing something language-specific wrong would appreciate another set
of eyes.
def partition(A, start, stop):
p = A[start] # make pivot first element in partition
i = start + 1
for j in range(i, stop):
# swap elements if A[j] bigger than pivot
if A[j] < p:
A[j], A[i] = A[i], A[j]
i += 1
# swap pivot into sorted index
A[start], A[i-1] = A[i-1], A[start]
return i
def quick_sort(A, start, stop, count):
if start < stop:
# increment count by length of partition less the pivot
count += (stop - start - 1)
print(count)
split = partition(A, start, stop)
# recursively sort lower partition
quick_sort(A, start, split-1, count)
# recursively count upper partition
quick_sort(A, split, stop, count)
return count
def main():
unsorted = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
count = quick_sort(unsorted, 0, len(unsorted), 0)
print(unsorted)
print("There are {} comparisons.".format(count))
main()
This code is giving me this output:
➜ algorithms python3 quick_sort_first.py
7
13
18
22
25
27
28
28
[1, 2, 3, 4, 5, 6, 7, 8]
There are 7 comparisons.
Thank you,
Patricia
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] [OT] Best Practices for Scientific Computing
Could someone clarify "Modularize code rather than copying and pasting?" thanks On Fri, 11/14/14, Albert-Jan Roskam wrote: Subject: [Tutor] [OT] Best Practices for Scientific Computing To: "Python Mailing List" Date: Friday, November 14, 2014, 12:19 PM Hi, I thought this might be worth sharing, especially on a windy, rainy Friday evnening: http://www.plosbiology.org/article/info%3Adoi%2F10.1371%2Fjournal.pbio.1001745 Here are the best practices mentioned in the article: Write programs for people, not computers. A program should not require its readers to hold more than a handful of facts in memory at once. Make names consistent, distinctive, and meaningful. Make code style and formatting consistent. Let the computer do the work. Make the computer repeat tasks. Save recent commands in a file for re-use. Use a build tool to automate workflows. Make incremental changes. Work in small steps with frequent feedback and course correction. Use a version control system. Put everything that has been created manually in version control. Don't repeat yourself (or others). Every piece of data must have a single authoritative representation in the system. Modularize code rather than copying and pasting. Re-use code instead of rewriting it. Plan for mistakes. Add assertions to programs to check their operation. Use an off-the-shelf unit testing library. Turn bugs into test cases. Use a symbolic debugger. Optimize software only after it works correctly. Use a profiler to identify bottlenecks. Write code in the highest-level language possible. Document design and purpose, not mechanics. Document interfaces and reasons, not implementations. Refactor code in preference to explaining how it works. Embed the documentation for a piece of software in that software. Collaborate. Use pre-merge code reviews. Use pair programming when bringing someone new up to speed and when tackling particularly tricky problems. Use an issue tracking tool. Have a great weekend! Regards, Albert-Jan ~~ All right, but apart from the sanitation, the medicine, education, wine, public order, irrigation, roads, a fresh water system, and public health, what have the Romans ever done for us? ~~ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] methods of sorting
This makes sense. Thanks. No question on the specific code, I was just thinking I should show I'd done any experimenting with the methods Hi Patti, My answers below, interleaved between your questions. On Tue, Apr 22, 2014 at 04:18:38PM -0700, Patti Scott wrote: > I'm practicing with lists. I was looking for documentation on sorting > with cmp() because it isn't immediately clear to me how comparing > items two at a time can sort the entire list. Identify max or min > values, yes, but not sort the whole list. So, the Sorting HOW TO > (Dalke, Hettinger) posted on python.org goes into detail on using a > key parameter for sorted() and .sort(), and using operator module > functions. Think about how you might sort four items 42, 23, 57, 30. There are many different ways to sort, and this is one of the least efficient, but easiest to understand. We start by putting the unsorted items on the left, and the sorted items on the right, as if we were sorting a handful of playing cards: [42, 23, 57, 30] [] Take the first item from the left, and find where it belongs on the right. Since the right is currently empty, that's easy: [23, 57, 30] [42] Now take the next item from the left, and find where it belongs on the right. How do you do that? By comparing it to each item already there. If it compares less than the item, insert it just before the item; otherwise keep going. In this case, we compare 23 < 42, which returns True, so we insert 23 to the left of 42. [57, 30] [23, 42] Now repeat with the next item. In this case, 57 < 23 returns False, so we continue. 57 < 42 also returns False, and there are no more numbers to check so we put 57 at the end: [30] [23, 42, 57] Finally we compare 30 < 23, which returns False, then 30 < 42, which returns True, so we insert 30 just to the left of 42: [] [23, 30, 42, 57] Now that we know how to sort using "less than" < as the comparison function, we can use some other comparison function that works similarly. Instead of using < we can use the built-in function cmp(a, b), which returns -1 if a < b, 0 if a == b, and +1 if a > b. Or instead of using the built-in cmp function, we can use any function that takes two arguments, the items to be compared, and returns one of -1, 0 or 1. Even though the Python list.sort() method is a lot faster and more clever than what I show above, it too allows you to provide a custom comparison function to decide which comes earlier or later when sorting. Here's an example with and without a comparison function: py> sorted(['dog', 'aardvark', 'chicken', 'horse']) ['aardvark', 'chicken', 'dog', 'horse'] py> sorted(['dog', 'aardvark', 'chicken', 'horse'], ... lambda a, b: cmp(len(a), len(b))) ['dog', 'horse', 'chicken', 'aardvark'] In the second case, we sort by the length of the words, not the content of the word. So "dog" (three letters) compares less than "aardvark" (eight letters). A couple of other notes: - Rather than define a comparison function using def, I use lambda as a shortcut. lambda creates a function, but limited only to a single expression. So "lambda a, b: cmp(len(a), len(b))" is equivalent to: def function(a, b): return cmp(len(a), len(b)) - Notice that I use the built-in cmp function inside my comparison function. That's just for convenience, you don't have to do that. > How obsolete are the cmp() and the decorate-sort-undecorate methods? > To be understood but probably not used in new code? Both are very obsolute, but for different reasons. The problem with using a comparison function is that it is very inefficient and it can really slow down sorting of large lists by a lot. It is better to use the DSU idiom rather than call a comparison function. In fact, that is so much better, that recent versions of Python make the DSU idiom built-in: that's what the "key" argument to the sort() and sorted() functions is for. When you supply a key function to sort, it internally uses the DSU idiom. You almost never need to use it yourself. Using the key function is so much better than using a comparison function that in Python 3 the comparison function was dropped altogether and using key is the only way to customize sorting. > Python Programming, Zelle; Python 2.7.3, PowerShell, Notepad ++ > > I tried several means of sorting for exercises, eg [lots of code shown] I'm sorry, did you have a question about the sorting code or were you just sharing it with us? If you're asking which should be preferred, I would prefer the version using the key=... argument to sort. -- Steven___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] methods of sorting
I'm practicing with lists. I was looking for documentation on sorting with
cmp() because it isn't immediately clear to me how comparing items two at a
time can sort the entire list. Identify max or min values, yes, but not sort
the whole list. So, the Sorting HOW TO (Dalke, Hettinger) posted on
python.org goes into detail on using a key parameter for sorted() and .sort(),
and using operator module functions.
How obsolete are the cmp() and the decorate-sort-undecorate methods? To be
understood but probably not used in new code?
Python Programming, Zelle; Python 2.7.3, PowerShell, Notepad ++
I tried several means of sorting for exercises, eg
# sortgpa3.py
# extended to let user print report out by name,GPA or credit hours
from gpa import Student, makeStudent
def readStudents(filename):
infile = open(filename, 'r')
students = []
for line in infile:
students.append(makeStudent(line))
infile.close()
return students
def writeStudents(students, filename):
outfile = open(filename, 'w')
for s in students:
outfile.write("%0.2f\t%s\t%0.2f\t%0.2f\n" % (s.gpa(),s.getName(),
s.getHours(), s.getQPoints()))
outfile.close()
def cmpGPA(s1, s2):
#function compares two students based on GPA
return cmp(s1.gpa(), s2.gpa())
def cmpHours(s1, s2):
#function compares two students based on credits
return cmp(s1.getHours(), s2.getHours())
def cmpNames(s1, s2):
#function compares two students' names
return cmp(s1.getName(), s2.getName())
def main():
print "This program sorts student grade information by GPA."
order = raw_input("Do you want results printed by name, credits or GPA? ")
filename = raw_input("Enter the name of the data file: ")
data = readStudents(filename)
if order[0] == ('c' or 'C'):
data.sort(cmpHours)
elif order[0] == ('g' or "G"):
data.sort(cmpGPA)
else:
data.sort(cmpNames)
filename = raw_input("Enter a name for the output file: ")
writeStudents(data, filename)
print "The data has been written to file %s." % (filename)
main()
or,
def main():
print "This program sorts students based on user request."
filename = raw_input("Enter name of the file containing student data: ")
data = readStudents(filename)
order = raw_input("Choose the field on which to sort students (name, GPA or
credits): ")
#print order[0]
if order[0] == ('n' or "N"):
tuples = [(student.getName(), student) for student in data]
tuples.sort()
data = [(tuples[i][1]) for i in range(len(tuples))]
#data.sort()
elif order[0] == ('c' or "C"):
tuples = [(student.getHours(), student) for student in data]
tuples.sort()
data = [(tuples[i][1]) for i in range(len(tuples))]
elif order[0] == ('g' or "G"):
tuples = [(student.gpa(), student) for student in data]
tuples.sort()
data = [(tuples[i][1]) for i in range(len(tuples))]
filename = raw_input("Enter a name for the output file: ")
writeStudents(data, filename)
print "The data has been written to %s ." % (filename)
if __name__=='__main__':
main()
or,
def main():
print "This program sorts students based on user request."
filename = raw_input("Enter name of the file containing student data: ")
data = readStudents(filename)
order = raw_input("Choose the field on which to sort students (name, GPA or
credits): ")
print order[0]
if order[0] == ('g' or "G"):
data = sorted(data, key=lambda student: student.gpa())
elif order[0] == ('c' or "C"):
data = sorted(data, key=lambda student: student.getHours())
elif order[0] == ('n' or "N"):
data = sorted(data, key=lambda student: student.getName())
filename = raw_input("Enter a name for the output file: ")
writeStudents(data, filename)
print "The data has been written to %s ." % (filename)
if __name__=='__main__':
main()___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] conditional execution
Thank you Emile, Zach, Chris and d. I am actually catching lots of my typos before I try to run anything ... From: spir To: tutor@python.org Sent: Wednesday, April 2, 2014 3:18 AM Subject: Re: [Tutor] conditional execution On 04/01/2014 06:24 PM, Zachary Ware wrote: > Hi Patti, > > On Tue, Apr 1, 2014 at 11:07 AM, Patti Scott wrote: >> I've been cheating: comment out the conditional statement and adjust the >> indents. But, how do I make my program run with if __name__ == 'main': >> main() at the end? I thought I understood the idea to run a module called >> directly but not a module imported. My program isn't running, though. > > The simple fix to get you going is to change your ``if __name__ == > 'main':`` statement to ``if __name__ == '__main__':`` (add two > underscores on each side of "main"). To debug this for yourself, try > putting ``print(__name__)`` right before your ``if __name__ ...`` > line, and see what is printed when you run it in different ways. > > Hope this helps, and if you need any more help or a more in-depth > explanation of what's going on, please don't hesitate to ask :) And you don't even need this idiom if your module is only to be executed (not imported). Just write "main()". d ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] conditional execution
I've been cheating: comment out the conditional statement and adjust the
indents. But, how do I make my program run with if __name__ == 'main': main()
at the end? I thought I understood the idea to run a module called directly
but not a module imported. My program isn't running, though.
Below is the last textbook example (Python Programming, Zelle) I reworked.
Runs when I comment out the conditional statement. I am self-studying. Python
2.7.3, Notepad++, Windows PowerShell.
# calc.pyw
# a 4-function calculator that uses Python arithmetic
# illustrates use of objects and lists to build a simple GUI
from graphics import *
from button import Button
class Calculator:
# this class implements simple calculator GUI
def __init__(self):
# create window for calculator
win = GraphWin('calculator')
win.setCoords(0,0,6,7)
win.setBackground('slategray')
self.win = win
# now create the widgets
self.__createButtons()
self.__createDisplay()
def __createButtons(self):
# create list of buttons
# start with all the standard-sized buttons
# bSpecs gives center coords and labels of buttons
bSpecs = [(2,1,'0'), (3,1,'.'),
(1,2,'1'), (2,2,'2'), (3,2,'3'), (4,2,'+'), (5,2,'-'),
(1,3,'4'), (2,3,'5'), (3,3,'6'), (4,3,'*'), (5,3,'/'),
(1,4,'7'), (2,4,'8'), (3,4,'9'), (4,4,'<-'), (5,4,'C')]
self.buttons = []
for (cx,cy, label) in bSpecs:
self.buttons.append(Button(self.win, Point(cx,cy), .75,.75, label))
# create the larger equals button
self.buttons.append(Button(self.win, Point(4.5,1), 1.75, .75, '='))
# activate all buttons
for b in self.buttons:
b.activate()
def __createDisplay(self):
bg = Rectangle(Point(.5,5.5), Point(5.5, 6.5))
bg.setFill('white')
bg.draw(self.win)
text = Text(Point(3,6), "")
text.setFace('courier')
text.setStyle('bold')
text.setSize(16)
text.draw(self.win)
self.display = text
def getButton(self):
# waits for button to be clicked and returns label of that button
while True:
p = self.win.getMouse()
for b in self.buttons:
if b.clicked(p):
return b.getLabel() # method exit
def processButton(self, key):
# updates calculator display for press of this key
text = self.display.getText()
if key == 'C':
self.display.setText("")
elif key == "<-":
# backspace, slice off the last character
self.display.setText(text[:-1])
elif key == '=':
# evaluate the expression and display result
# the try ... except mechanism catches errors in the
# formula being evaluated
try:
result = eval(text)
except:
result ='ERROR'
self.display.setText(str(result))
else:
# normal key press, append it to end of display
self.display.setText(text+key)
def run(self):
# infinite event loop to process button clicks
while True:
key = self.getButton()
self.processButton(key)
#this runs the program
if __name__ == 'main':
#first create a calulator object
theCalc = Calculator()
# now call the calculator's run methond
theCalc.run()
and I get
PS C:\Users\Owner\Py Programs> python calc.py
PS C:\Users\Owner\Py Programs>
Thanks___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
[Tutor] Unit testing individual modules
Python 2.4
self-study with Python Programming: An Introduction to Computer Science by Zelle
I am trying to import a program that has a conditional execution statement at
the end so I can troubleshoot individual modules in the main() program.
Below is the textbook example program. When I try to import the program from
Idle, I get
Traceback (most recent call last):
File "", line 1, in -toplevel-
import rball
ImportError: No module named rball
(Also if I try to import with .py or .pyc)
From the commandline interface, I can import the program, but __name__ is
still "__main__" and I haven't successfully unit tested any of the individual
functions.
# rball.py
# textbook example of top-down design for Monte Carlo raquetball simulation
from random import random
def main():
#printIntro()
#probA, probB, n = getInputs()
#winsA, winsB = simNGames(n,probA,probB)
#printSummary(winsA, winsB)
def printIntro():
print "This program simulates a game of racquetball between two"
print 'players called "A" and "B." The ability of each player is'
print "indicated by a probability (a number between 0 and 1) that"
print "the player wins the point when serving. Player A always"
print "has the first serve."
def getInputs():
#Returns the three simulation parameters
n = input("How many games to simulate? ")
a = input("What is the probability player A wins service? ")
b = input("What is the probability player B wins service? ")
return a, b, n
def simNGames(n, probA, probB):
#simulates n games of racquetball between players whose
# abilities are represented by the prob. of winning serivce
#Returns total number of wins for A and B
winsA = winsB = 0
for i in range(n):
scoreA, scoreB = simOneGame(probA, probB)
if scoreA > scoreB:
winsA = winsA + 1
else:
winsB = winsB + 1
return winsA, winsB
def simOneGame(probA, probB):
#Simulates a single game between players whose
# abilities are represented by the prob. of winning service.
# Returns final scores for A and B, one game
serving = 'A'
scoreA = scoreB = 0
while not gameOver(scoreA, scoreB):
if serving == 'A':
if random()< probA:
scoreA = scoreA + 1
else:
serving = 'B'
else:
if random() < probB:
scoreB = scoreB + 1
else:
serving = 'A'
return scoreA, scoreB
def gameOver(a,b):
# a and b represent running scores for one racquetball game
# Returns True if game over, False otherwise
return a==15 or b==15
def printSummary(winsA, winsB):
# Prints a summary of wins for each player.
n = winsA + winsB
print
print "Games simulated:", n
print "Wins for A: %d (%0.1f%%)" % (winsA, float(winsA)/n*100)
print "Wins for B: %d (%0.1f%%)" % (winsB, float(winsB)/n*100)
printIntro()
probA, probB, n = getInputs()
winsA, winsB = simNGames(n,probA,probB)
printSummary(winsA, winsB)
if __name__ == "__main__": main()___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
