Python set in implementation

Python Programming/Sets

Starting with version 2.3, Python comes with an implementation of the mathematical set. Initially this implementation had to be imported from the standard module set, but with Python 2.6 the types set and frozenset became built-in types. A set is an unordered collection of objects, unlike sequence objects such as lists and tuples, in which each element is indexed. Sets cannot have duplicate members — a given object appears in a set 0 or 1 times. All members of a set have to be hashable, just like dictionary keys. Integers, floating point numbers, tuples, and strings are hashable; dictionaries, lists, and other sets (except frozensets) are not.

Contents

Overview [ edit | edit source ]

Sets in Python at a glance:

set1 = set() # A new empty set set1.add("cat") # Add a single member set1.update(["dog", "mouse"]) # Add several members, like list's extend set1 |= set(["doe", "horse"]) # Add several members 2, like list's extend if "cat" in set1: # Membership test set1.remove("cat") #set1.remove("elephant") - throws an error set1.discard("elephant") # No error thrown print(set1) for item in set1: # Iteration AKA for each element print(item) print("Item count:", len(set1))# Length AKA size AKA item count #1stitem = set1[0] # Error: no indexing for sets isempty = len(set1) == 0 # Test for emptiness set1 = "cat", "dog"> # Initialize set using braces; since Python 2.7 #set1 = <> # No way; this is a dict set1 = set(["cat", "dog"]) # Initialize set from a list set2 = set(["dog", "mouse"]) set3 = set1 & set2 # Intersection set4 = set1 | set2 # Union set5 = set1 - set3 # Set difference set6 = set1 ^ set2 # Symmetric difference issubset = set1  set2 # Subset test issuperset = set1 >= set2 # Superset test set7 = set1.copy() # A shallow copy set7.remove("cat") print(set7.pop()) # Remove an arbitrary element set8 = set1.copy() set8.clear() # Clear AKA empty AKA erase set9 = x for x in range(10) if x % 2> # Set comprehension; since Python 2.7 print(set1, set2, set3, set4, set5, set6, set7, set8, set9, issubset, issuperset) 

Constructing Sets [ edit | edit source ]

One way to construct sets is by passing any sequential object to the «set» constructor.

>>> set([0, 1, 2, 3]) set([0, 1, 2, 3]) >>> set("obtuse") set(['b', 'e', 'o', 's', 'u', 't']) 

We can also add elements to sets one by one, using the «add» function.

>>> s = set([12, 26, 54]) >>> s.add(32) >>> s set([32, 26, 12, 54]) 

Note that since a set does not contain duplicate elements, if we add one of the members of s to s again, the add function will have no effect. This same behavior occurs in the «update» function, which adds a group of elements to a set.

>>> s.update([26, 12, 9, 14]) >>> s set([32, 9, 12, 14, 54, 26]) 

Note that you can give any type of sequential structure, or even another set, to the update function, regardless of what structure was used to initialize the set.

The set function also provides a copy constructor. However, remember that the copy constructor will copy the set, but not the individual elements.

>>> s2 = s.copy() >>> s2 set([32, 9, 12, 14, 54, 26]) 

Membership Testing [ edit | edit source ]

We can check if an object is in the set using the same «in» operator as with sequential data types.

>>> 32 in s True >>> 6 in s False >>> 6 not in s True 

We can also test the membership of entire sets. Given two sets S 1 > and S 2 > , we check if S 1 > is a subset or a superset of S 2 > .

>>> s.issubset(set([32, 8, 9, 12, 14, -4, 54, 26, 19])) True >>> s.issuperset(set([9, 12])) True 

Note that «issubset» and «issuperset» can also accept sequential data types as arguments

Note that the = operators also express the issubset and issuperset functions respectively.

>>> set([4, 5, 7])  set([4, 5, 7, 9]) True >>> set([9, 12, 15]) >= set([9, 12]) True 

Like lists, tuples, and string, we can use the «len» function to find the number of items in a set.

Removing Items [ edit | edit source ]

There are three functions which remove individual items from a set, called pop, remove, and discard. The first, pop, simply removes an item from the set. Note that there is no defined behavior as to which element it chooses to remove.

>>> s = set([1,2,3,4,5,6]) >>> s.pop() 1 >>> s set([2,3,4,5,6]) 

We also have the «remove» function to remove a specified element.

However, removing a item which isn’t in the set causes an error.

>>> s.remove(9) Traceback (most recent call last): File "", line 1, in ? KeyError: 9 

If you wish to avoid this error, use «discard.» It has the same functionality as remove, but will simply do nothing if the element isn’t in the set

We also have another operation for removing elements from a set, clear, which simply removes all elements from the set.

Iteration Over Sets [ edit | edit source ]

We can also have a loop move over each of the items in a set. However, since sets are unordered, it is undefined which order the iteration will follow.

>>> s = set("blerg") >>> for n in s: . print(n, "", end="") . r b e l g 

Set Operations [ edit | edit source ]

Python allows us to perform all the standard mathematical set operations, using members of set. Note that each of these set operations has several forms. One of these forms, s1.function(s2) will return another set which is created by «function» applied to S 1 > and S 2 > . The other form, s1.function_update(s2), will change S 1 > to be the set created by «function» of S 1 > and S 2 > . Finally, some functions have equivalent special operators. For example, s1 & s2 is equivalent to s1.intersection(s2)

Intersection [ edit | edit source ]

Any element which is in both S 1 > and S 2 > will appear in their intersection.

>>> s1 = set([4, 6, 9]) >>> s2 = set([1, 6, 8]) >>> s1.intersection(s2) set([6]) >>> s1 & s2 set([6]) >>> s1.intersection_update(s2) >>> s1 set([6]) 

Union [ edit | edit source ]

The union is the merger of two sets. Any element in S 1 > or S 2 > will appear in their union.

>>> s1 = set([4, 6, 9]) >>> s2 = set([1, 6, 8]) >>> s1.union(s2) set([1, 4, 6, 8, 9]) >>> s1 | s2 set([1, 4, 6, 8, 9]) 

Note that union’s update function is simply «update» above.

Symmetric Difference [ edit | edit source ]

The symmetric difference of two sets is the set of elements which are in one of either set, but not in both.

>>> s1 = set([4, 6, 9]) >>> s2 = set([1, 6, 8]) >>> s1.symmetric_difference(s2) set([8, 1, 4, 9]) >>> s1 ^ s2 set([8, 1, 4, 9]) >>> s1.symmetric_difference_update(s2) >>> s1 set([8, 1, 4, 9]) 

Set Difference [ edit | edit source ]

Python can also find the set difference of S 1 > and S 2 > , which is the elements that are in S 1 > but not in S 2 > .

>>> s1 = set([4, 6, 9]) >>> s2 = set([1, 6, 8]) >>> s1.difference(s2) set([9, 4]) >>> s1 - s2 set([9, 4]) >>> s1.difference_update(s2) >>> s1 set([9, 4]) 

Multiple sets [ edit | edit source ]

Starting with Python 2.6, «union», «intersection», and «difference» can work with multiple input by using the set constructor. For example, using «set.intersection()»:

>>> s1 = set([3, 6, 7, 9]) >>> s2 = set([6, 7, 9, 10]) >>> s3 = set([7, 9, 10, 11]) >>> set.intersection(s1, s2, s3) set([9, 7]) 

frozenset [ edit | edit source ]

A frozenset is basically the same as a set, except that it is immutable — once it is created, its members cannot be changed. Since they are immutable, they are also hashable, which means that frozensets can be used as members in other sets and as dictionary keys. frozensets have the same functions as normal sets, except none of the functions that change the contents (update, remove, pop, etc.) are available.

>>> fs = frozenset([2, 3, 4]) >>> s1 = set([fs, 4, 5, 6]) >>> s1 set([4, frozenset([2, 3, 4]), 6, 5]) >>> fs.intersection(s1) frozenset([4]) >>> fs.add(6) Traceback (most recent call last): File "", line 1, in module> AttributeError: 'frozenset' object has no attribute 'add' 

Exercises [ edit | edit source ]

1. Create the set , call it s.
2. Create the set .
3. Create the frozen set , call it fs.
4. Create a set containing the frozenset fs, it should look like )>.

Reference [ edit | edit source ]

Источник

Internal working of Set in Python

Sets and their working Set in Python can be defined as the collection of items. In Python, these are basically used to include membership testing and eliminating duplicate entries. The data structure used in this is Hashing, a popular technique to perform insertion, deletion and traversal in O(1) on average. The operations on Hash Table are some what similar to Linked List. Sets in python are unordered list with duplicate elements removed.

Basic Methods on Sets are:-

Creating Set:- In Python, Sets are created through set() function. An Empty list is created. Note that empty Set cannot be created through <>, it creates dictionary.

Checking if an item is in : Time complexity of this operation is O(1) on average. However in worst case it can become O(n).

Adding elements:- Insertion in set is done through set.add() function, where an appropriate record value is created to store in the hash table. Same as checking for an item, i.e., O(1) on average. However in worst case it can become O(n).

Union:- Two sets can be merged using union() function or | operator. Both Hash Table values are accessed and traversed with merge operation perform on them to combine the elements, at the same time duplicates are removed. Time Complexity of this is O(len(s1) + len(s2)) where s1 and s2 are two sets whose union needs to be done.

Intersection:- This can be done through intersection() or & operator. Common Elements are selected. They are similar to iteration over the Hash lists and combining the same values on both the Table. Time Complexity of this is O(min(len(s1), len(s2)) where s1 and s2 are two sets whose union needs to be done.

Difference:- To find difference in between sets. Similar to find difference in linked list. This is done through difference() or – operator. Time complexity of finding difference s1 – s2 is O(len(s1))

Symmetric Difference:- To find element in both the sets except the common elements. ^ operator is used. Time complexity of s1^s2 is O(len(s1))

Symmetric Difference Update: Returns a new set which contains symmetric difference of two sets. Time complexity is O(len(s2)) clear:- Clears the set or Hash Table.

If Multiple values are present at the same index position, then the value is appended to that index position, to form a Linked List. In, Python Sets are implemented using dictionary with dummy variables, where key beings the members set with greater optimizations to the time complexity. Set Implementation:-
Sets with Numerous operations on a single HashTable:- Examples:

# empty set, avoid using <> in creating set or dictionary is created x = set() # set is created in unordered way B = set('hello') # set is created A = set('abcdefg') # set A.add('h') fruit = # True fast membership testing in sets 'pear' in fruit 'mango' in fruit # False A == B # A is equivalent to B A != B # A is not equivalent to B A = B A > B # A is proper superset of B A | B # the union of A and B A & B # the intersection of A and B A - B # the set of elements in A but not B A ˆ B # the symmetric difference a = # Set Comprehension

Источник