6
\$\begingroup\$

I wanted to ask for a code review for my implementation of Set:

#!python
from linkedlist import Node, LinkedList
from hashtable import HashTable




class Set(object):
    def __init__(self, elements=None):
        # intilaize the size of the set, starts with intial size of 10 
        if elements is None:
            initial_size = 10
        else:
            initial_size = len(elements)
        #     
        self.data = HashTable(initial_size)
        for item in elements:
            if self.data.contains(item):
                continue
            else:
                self.data.set(item, None)

    def __str__(self):
        return str(self.data.keys())

    def set_contents(self):
        """Get the contents of the set [key inside a HashTable]"""
        return self.data.keys()

    def size(self):
        """Find size of the set"""
        return self.data.size

    def contains(self, element):
        """return a boolean contained inside of the set [key inside a HashTable]"""
        """Best case running time for contains is O(1) near beginning of set
        Worst case running time for contains O(n) near end of set """
        return self.data.contains(element)

    def add(self, element):
        """Add the element of the set"""
        # O (1)
        """Best case running time: O(1) near beginning of list of keys
        Worst case running time: O(n) near end of list of keys """
        if self.contains(element):
            return
        else:
            self.data.set(element, None)

    def remove(self, element):
        # Raise value error if not available
        if self.contains(element):
            self.data.delete(element)
        else:
            raise ValueError("Element not in set")

    def union(self, second_set):
        """Return a new  set, that is a union of first_set and second_set"""
        # O(n) since it goes through every item and has contains"""
        # create a new set that has the set conents
        result_set = self.set_contents()

        for item in second_set.set_contents():
            if self.contains(item):
                continue
            else:
                result_set.append(item)
        return Set(result_set)

    def intersection(self, second_set):
        """Return a new set, that is intersection of this set and second_set."""
        """O(n) since it goes through every item and has contains"""
        # create an empty set
        result_set = []
        for item in second_set.set_contents():
            # check if the set contains the item 
            if self.contains(item):
                result_set.append(item)
            # else:
            #     return ValueError("Set is empty")
        return Set(result_set)

Is_Subset

    def is_subset(self, second_set):
        """Return True if second set is a subset of this set,else False"""
        # O(n); goes through every item and has contains
        # Compariing the size of the 2 set  
        # to make sure if set is in the second set
        # for bucket in self.buckets:
            # for element in bucket.iterate():
            #     if not other.contains(element)
        if self.size() <= second_set.size():
            for item in self.set_contents():
                if second_set.contains(item):
                    continue
                else:
                    return False
            return True
        else:
            return False

# set_set_test = Set()
set_test = Set([1, 2, 3, 4, 5,6,7,8,9,10])
set_test2 = Set([ 11,12])
test_intersection = set_test.intersection(set_test2)
print(test_intersection)
set_test2 = Set([6, 7, 8,9,10])

print(set_test)
print(set_test2)

set_test.add(1)
print(set_test)
print(set_test.intersection(set_test2))
print(set_test.union(set_test2))

print(set_test.is_subset(set_test2))

set_test = Set([1, 2, 3])
set_test2 = Set([1, 2, 3, 4, 5, 6, 7, 8])
print(set_test.is_subset(set_test2))

set_test = Set([1, 2, 3])
set_test2 = Set([1, 2, 3])
print(set_test.is_subset(set_test2))

set_test = Set([1, 2, 3, 4])
set_test2 = Set([1, 2, 3])
print(set_test.is_subset(set_test2))

set_test = Set([1, 2, 3, 4, 5])
set_test2 = Set([4, 5, 6, 7, 8])
print(set_test.is_subset(set_test2))
\$\endgroup\$
  • \$\begingroup\$ Your is_subset method returns True if the current set is a subset of the second_set, even though your method comment says the opposite. \$\endgroup\$ – Raimund Krämer Dec 22 '17 at 12:32
  • \$\begingroup\$ Hello, in order to provide a deeper review, I'd like to be able to test your code. Are the required modules (linked list and hash table) available somewhere? Happy holidays! \$\endgroup\$ – Josay Dec 24 '17 at 15:04
3
\$\begingroup\$

Since you explicitly ask about your is_subset implementation in the title, I will review this first, and the rest of the code afterwards.

Bug

As I already commented on the question, the method works the opposite of what its documentation says, and also of what the method name implies. It returns True if this set is a subset of the second_set. If the code is correct and the comment wrong (which I don't think is the case), then I suggest fixing the comment and changing the method name to is_subset_of(self, superset_candidate). If the method name and comment are correct, then after fixing the code I recommend to rename the parameter second_set to subset_candidate.

Comments

You have code commented out inside your method. That can make the reader wonder why that is. Is it commented out because it can be deleted? Will it be needed later? If a reader looks for a bug in the method, was the bug caused by the commented code that is actually needed?

Logic

This looks complicated as it is nested quite deeply:

    if self.size() <= second_set.size():
        for item in self.set_contents():
            if second_set.contains(item):
                continue
            else:
                return False
        return True
    else:
        return False

You can improve it by returning early if the first condition is False, and you can omit the continue by inverting the if-condition:

if not self.size() <= second_set.size():
    return False

for item in self.set_contents():
    if not second_set.contains(item):
        return False
return True

The Rest of the Code

from linkedlist import Node, LinkedList

It seems like you are not using that import.


In your __init__ method you use a # to separate two blocks. Rather just use a blank line instead.


You use data as the name of your variable that holds the elements. elements might be a better name, as data could be anything and you expect a set to contain elements, not data.


for item in elements:
    if self.data.contains(item):
        continue
    else:
        self.data.set(item, None)

Checking whether the item is already a key in the HashTable should not be needed. Just overwriting it with the value None if it is already there is basically the same effect as skipping it. So the 5 lines could be shortened to 2 lines.


def set_contents(self):
    """Get the contents of the set [key inside a HashTable]"""
    return self.data.keys()

This looks like it should be get_contents. I see that it is supposed to mean "the contents of the set", but since getters and setters are common in many programming languages the reader would expect a method with this name to change a value named contents, i. e. to set the value. You could name it get_contents() instead, or just contents(). But: Accessing the contents like this is not a common operation for a set. A set should already represent the elements itself, giving access to them via iteration. If you do want to implement this method to access the contents directly, I suggest the name to_list. Generally I recommend having a look at the Python documentation for sets to then reimplement the same interface.

As a side note, I don't quite understand what your comment is trying to say, especially that part in brackets. If the intention is to tell the reader how the method is implemented, then that does not belong in the method's doc comment. How the interface is realized by the implementation should not be important to the user.


def size(self):
    """Find size of the set"""
    return self.data.size

Python supports using the len(x) function for types that implement the __len__ method. It is also part of the actual interface of Set in Python. Being consistent with how you check for a collection's size or length can be important, because a user of your type might not expect it to have a size() method and could get an error when calling len() for your type.

Apart from that, the comment is misleading, as "find" is typically used for operations that search through many items, like in a database, and simply returning a value is referred to as "getting" the value.


def contains(self, element):
    """return a boolean contained inside of the set [key inside a HashTable]"""
    """Best case running time for contains is O(1) near beginning of set
    Worst case running time for contains O(n) near end of set """
    return self.data.contains(element)

Here your comment is quite confusing again. A better comment would be something like """returns True if the element is in the Set, otherwise returns False""". Also, have a look at the __contains__ method in Python, which enables you to check if a collection contains an element by using a in b.


def add(self, element): """Add the element of the set""" # O (1) """Best case running time: O(1) near beginning of list of keys Worst case running time: O(n) near end of list of keys """ if self.contains(element): return else: self.data.set(element, None)

Like in your __init__ method, you skip or return if the value is already contained. However, if it is contained, overwriting it with None would make your method shorter and more readible, and would probably even be more efficient, since you wouldn't need to look through all of your keys to check if it is already contained. Your first comment should say """Add element to the set""", probably just a typo again that it says "of the set". Then your next comment line suggests that the operation is of complexity O(1), contradicting the following line that says that it is O(1) only near the beginning of the list of keys. Again, that is an implementation detail that should not be in your doc string, and I recommend not to mix # and """ """ comments. The triple quotes version for the documentation comment that describes what the method does, and # to clarify parts of your code. And since """ """ is a multiline string, you don't need to put two of those in following lines. Just put the whole comment in one multilines string, perhaps using single blank lines to separate logical blocks of the comment.


def remove(self, element):
    # Raise value error if not available
    if self.contains(element):
        self.data.delete(element)
    else:
        raise ValueError("Element not in set")

That comment is obsolete, as it just describes what the code says 4 lines later without adding any information.


def union(self, second_set):
    """Return a new  set, that is a union of first_set and second_set"""
    # O(n) since it goes through every item and has contains"""
    # create a new set that has the set conents
    result_set = self.set_contents()

    for item in second_set.set_contents():
        if self.contains(item):
            continue
        else:
            result_set.append(item)
    return Set(result_set)

If I'm not mistaken, this is not O(n) but O(n²), because for every item in the second set, you go through the whole first set to see if it is already in it. That is if the sets are approximately of the same size, which can be assumed in the average case. Considering that you do basically the same in your constructor, it is even less efficient. But you don't even need to care about duplicates first if you check for duplicates in the constructor anyway. Since you don't even need to check if the element is already contained, and can just overwrite it, you can actually do it in O(n):

def union(self, second_set):
    return Set(self.set_contents() + second_set.set_contents())

def intersection(self, second_set):
    """Return a new set, that is intersection of this set and second_set."""
    """O(n) since it goes through every item and has contains"""
    # create an empty set
    result_set = []
    for item in second_set.set_contents():
        # check if the set contains the item 
        if self.contains(item):
            result_set.append(item)
        # else:
        #     return ValueError("Set is empty")
    return Set(result_set)

For similar reasons as above with union, this is not O(n). Also you have comments again that just describe what the code does, which is obsolete, however in the case of the first one it is even wrong, because you don't create an empty set, but an empty list. And you have a comment that is actually code, which is confusing. Is it not needed? Can it be deleted?

The method implementation can be done more efficiently and more readible by using a list comprehension:

def intersection(self, second_set):
    items = [i for i in self.set_contents if second_set.contains(i)]
    return Set(items)

If you have the operations union and intersection, you usually also want an operation difference which gives you the subset of elements which are not contained in the other set. An example implementation would be this:

def difference(self, second_set):
    items = [i for i in self.set_contents if not second_set.contains(i)]
    return Set(items)
\$\endgroup\$
  • \$\begingroup\$ thanks for the comment and feedback. I will make sure that I correct that bug when explaining what the code does. \$\endgroup\$ – NinjaG Dec 22 '17 at 17:48
5
\$\begingroup\$

Warning: This is not tested

        for item in self.set_contents():
            if second_set.contains(item):
                continue
            else:
                return False
        return True

can be rewritten with no continue

        for item in self.set_contents():
            if not second_set.contains(item):
                return False
        return True

Then, this is the usual situation where all or any can be used.

For instance, you'd get something like:

        return all(second_set.contains(item) for item in self.set_contents())

Then, the whole function becomes:

def is_subset(self, second_set):
    """Return True if second set is a subset of this set,else False"""
    # O(n); goes through every item and has contains
    # Compariing the size of the 2 set  
    # to make sure if set is in the second set
    # for bucket in self.buckets:
        # for element in bucket.iterate():
        #     if not other.contains(element)
    return self.size() <= second_set.size() and \
              all(second_set.contains(item) for item in self.set_contents())
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.