[Edu-sig] Analyzing algorithms...

[Dinu Gherman]

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)