Jeffrey Elkner wrote:
After attending Pai Chou's wonderful presentation, "Algorithm Education in Python" at Python10, I got permission from the instructor of an algorithms course I am currently taking to do our programming assignments in Python (after first assuring him that they would not be difficult to read ;-)
Our first assignment is to implement merge and heap sort and then to compare them empirically as to the number of assignments and comparisons made by each.
I've written the sorts. Does anyone have any suggestions as to the best way to do the empirical analysis? Is there a better way than just creating counters and then littering my code with increment statements?
Please let me know if you have any ideas?
Thanks!
This is a very late contribution, but as I'm going through some of the hidden corners of my mailbox I might be able to add a comment, if you permit? I *think* sorting algorithms are compared using the number of compare and swap operations, so I assume by counting assign- ments you actually meant swap operations, isn't it? If so I believe the issue can be solved in the good old OO-way by creating an abstract sorting base class with concrete sub- classes of it. My preference would something like this (with visualising calls commented): --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- class Sorter: """An abstract sorting class. This contains hooks for swapping and comparing elements to be implemented in subclasses. Other methods could be filled in for visualising the algorithm used (and/or be called on respective delegates). """ def __init__(self): self.cmpCount = 0 self.swapCount = 0 def __call__(self, aList=None): self.sort(aList) def swap(self, aList, i, j): self.swapCount = self.swapCount + 1 L = aList L[i],L[j] = L[j],L[i] def compare(self, aList, i, j): self.cmpCount = self.cmpCount + 1 L = aList return cmp(L[i], L[j]) def sort(self, aList): raise "NotImplemented" class BubbleSort(Sorter): def sort(self, aList): L = aList # SHOW_bereich_quickest(0, len(L)-1) for x in range(len(L)): for z in fullrange(0, len(L)-2): # SHOW_element1(z) # SHOW_element2(z+1) if self.compare(L, z, z+1) >= 0: self.swap(L, z, z+1) # SHOW_zeig([z, z+1]) bs = BubbleSort() print bs.__class__.__name__ L = [9, 5, 2, 7, 6, 1, 3] print L bs(L) print L args = (bs. cmpCount, bs.swapCount) print "compares: %d, swaps: %d" % args --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- With some slight modifications you can plug this directly into the code posted by Gregor Lingl, replacing the bubble function with the following code like this: --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- class Sorter: def __init__(self, aList=None): self.cmpCount = 0 self.swapCount = 0 return self(aList) def __call__(self, aList=None): return self.sort(aList) def swap(self, aList, a, b): self.swapCount = self.swapCount + 1 L = aList L[a],L[b] = L[b],L[a] def compare(self, aList, a, b): self.cmpCount = self.cmpCount + 1 L = aList return cmp(L[a], L[b]) def sort(self, aList): return aList ############################################################## ## BubbleSort und Verwandte class bubble(Sorter): def sort(self, aList=None): global L SHOW_bereich_quickest(0,len(L)-1) for x in range(len(L)): for z in fullrange(0,len(L)-2): SHOW_element1(z) SHOW_element2(z+1) if self.compare(L, z, z+1) >= 0: self.swap(L,z,z+1) SHOW_zeig([z,z+1]) --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- 8< --- Jeff, does this also solve your problem, or is anything fun- damentally wrong with it? At least you don't have to implement many double underscore methods... Of course, I know more recent Python versions have function attributes, but then, strictly speaking, they aren't func- tions any more. Regards, Dinu -- Dinu C. Gherman ................................................................ "The world becomes a better place as a result of the refusal to bend to authority and doctrine." (Noam Chomsky)