#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    2

    Overloading + operator, something weird.


    Hi guys.
    I'm trying to implement operator overloading for a class called Set, and there's something weird going on with the + operator.

    here's the relevant code segment:

    Code:
    class Set:
        def __init__(self, initList=[]):
            noDupList=[]
            for element in initList: #removing duplications
                if element not in noDupList:
                    noDupList.append(element)
            self._set_=noDupList
            self._set_.sort() #sorting
    
        def __add__(self, aSet):
            temp=self._set_ #creating a local list "temp"
            for element in aSet._set_:
                if element not in self._set_:
                    temp.append(element)
            return Set(temp)
    and here's the main program:

    Code:
    Set1=Set([1,2,3,2,1,3,4,6,7,5])
    Set2=Set([9,8,5,6,7])
    print("Set1: ",Set1)
    print("Set2: ",Set2)
    print("Set1+Set2=",(Set1+Set2))
    the output for this code is:
    Code:
    Set1:  1,2,3,4,5,6,7.
    Set2:  5,6,7,8,9.
    Set1+Set2= 1,2,3,4,5,6,7,8,9.
    so far everything looks good, but when I print Set1 again (after the + operation), this is what I get:
    Code:
    print("Set1: ",Set1)
    Set1:  1,2,3,4,5,6,7,8,9.
    why does Set1 change??
    that doesn't make sense: I didn't change "self" in the __add__ method, I only created a temporary list named "temp" and then returned a NEW Set object.

    any help and tips would be greatly appreciated.
    Last edited by so.very.tired; April 23rd, 2013 at 08:41 AM.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,900
    Rep Power
    481
    Python correctly evaluated your code. temp is a reference to a list, not a new list. Watch:
    Code:
    >>> A = list()
    >>> B = A  # B refers to the same list as A
    >>> C = A[:] # C is a copy of A, an entirely different object.
    >>> [id(O) for O in (A,B,C)]  # A and B have the same id
    [139682567321360, 139682567321360, 139682567444168]
    >>> B.extend('this changes A')
    >>> A
    ['t', 'h', 'i', 's', ' ', 'c', 'h', 'a', 'n', 'g', 'e', 's', ' ', 'A']
    >>> C # C is unchanged because it's a different list
    []
    >>> del A[-5:]; del B[-3]; del A[0]
    >>> B
    ['h', 'i', 's', ' ', 'c', 'a', 'n']
    >>> 
    >>> LAUGH = [[]]*4
    >>> LAUGH
    [[], [], [], []]
    >>> LAUGH[2].append('ha')
    >>> LAUGH
    [['ha'], ['ha'], ['ha'], ['ha']]
    Now---your program. You've got duplicate code, which we abhor. Eliminate it. (also-->set types are built in. Making your own sets is a great exercise. In production code use the built in sets. Also, the original implementation of sets used dictionary keys. Dictionary keys are already a set type. Write an implementation using dictionaries.)
    Code:
    class SetError(Exception): # inherit all the methods of Exception
        pass
    
    class Set:
    
        def __init__(self, initList=[]):
            noDupList=[]
            # where n is len(initList)
            # you've written an order((n**2)*(n*log(n))) algorithm.
            for element in initList: #removing duplications  # this loop is O(n**2)
                if element not in noDupList:
                    noDupList.append(element)
            self._set_=noDupList
            self._set_.sort() #sorting    # the python sort is guaranteed O(n*log(n))
            # rewrite another version of your code to sort first,
            # then eliminate duplicates in a single pass.
            # time the two programs with large data sets of different sizes.
            # Does the original program take roughly n times longer than the new code?
            # Does the new code time scale as O(n*n*log(n))?
            # Present the result in this forum.
            # thanks, Dave.
    
        def __str__(self):
            return 'Set of {}'.format(str(tuple(self._set_)))
    
        def __add__(self, aSet):
            '''
                Set() + None # is invalid.  Trap bad cases.
                Note the duplicate code is removed.  Set.__init__ already does the work.
            '''
            try:
                return Set(self._set_ + aSet._set_)
            except:
                pass
            raise SetError('Cannot add incommensurate types')
    
    
    Set1=Set([1,2,3,2,1,3,4,6,7,5])
    Set2=Set([9,8,5,6,7])
    print("Set1: ",Set1)
    print("Set2: ",Set2)
    print("Set1+Set2=",(Set1+Set2))
    print("Set1: ",Set1)
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    2
    Hi, b49P23TIvg. thanks for the help. appreciate it.

    your code looks too advanced for me, I'm still a newbie.
    we didn't learn exceptions yet, so the exercise instruction specifically mentioning that we can assume that the input will be valid.
    however, (n**2)*(n*log(n)) is too high, and I guess it'll cost me some points.
    Code:
    #rewrite another version of your code to sort first,
    #then eliminate duplicates in a single pass.
    how would you remove duplications in the list? and why does it matter what do I do first (removing duplications from list or sorting)?
    Didn't know about the built in set type. I guess it could be very helpful.

    BTW, thanks for tip.
    added [:] to it and it solved it.
    Last edited by so.very.tired; April 23rd, 2013 at 01:10 PM.

IMN logo majestic logo threadwatch logo seochat tools logo