While working on a problem I observed something weird about sets. Can someone explain the logic behind it. Whenever I was adding an element to set, it inserted it in correct order. Given that set is an un-ordered data structure, how is this possible?
Following is an example of what I observed:
>>> a = set([1,3,5]) >>> a {1, 3, 5} >>> a.pop() 1 >>> a {3, 5} >>> a.add(4) >>> a {3, 4, 5} >>> a.add(6) >>> a {3, 4, 5, 6} >>> a.add(2) >>> a {2, 3, 4, 5, 6} >>>How I stumbled across this observation:
I was tring to solve the problem wherein I have to design a data structure that does insertion, removal and getRandom in O(1) time. The details can be found at
My basic idea is to use a HashMap of number -> List which stores a list of indexes of all the keys inserted in the list. Along with it I maintain a list(V) of values. List and HashMap will allow for constant insertion. HashMap will allow for constant removal of values. We can achieve constant removal of values from list if we swap the element to be removed with the last element of list and then remove the last element.
Basic use case:
- To insert a value 1. 1 is appended to the List(V). This index is stored in HashMap with key as 1.
- To getRandom, an element is picked at random from List(V)
- To delete, a value 1, the last index of 1 is popped from the HashMap, Then this index is swapped with the new element. Then the last index of the swapped element is updated in the HashMap and the last element in List(V) is removed.
The issue I am facing is that I need to insert the new index of swapped element at the correct position in the HashMap for this algorithm to work.
But interestingly when I use a set in HashMap instead of a list, I do not need to take care of it. The set somehow inserts the element at correct position. I know that set is supposed to be an unordered dataset, then why does this work. Can someone explain this behavior of sets?
The following is a code using lists where I have to use binary search to insert the swapped index at proper position. Here definitely delete in not O(1)
import random import bisect class RandomizedCollection: def __init__(self): """ Initialize your data structure here. """ self.myMap = {} self.stack = [] def insert(self, val): """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. :type val: int :rtype: bool """ #print("Inserting",val) #print(self.myMap,self.stack) tmp = self.myMap.get(val,[]) if len(tmp) == 0: self.stack.append(val) tmp.append(len(self.stack)-1) self.myMap[val] = tmp return True else: self.stack.append(val) tmp.append(len(self.stack)-1) self.myMap[val] = tmp return False def remove(self, val): """ Removes a value from the collection. Returns true if the collection contained the specified element. :type val: int :rtype: bool """ #print("Removing",val) #print(self.myMap,self.stack) tmp = self.myMap.get(val,[]) if len(tmp) > 0: if self.stack[-1] != val: idx_to_remove = tmp.pop() last_val = self.stack[-1] #print(idx_to_remove, last_val) self.myMap[last_val].pop() ## removes the last index insert_pos = bisect.bisect_left(self.myMap[last_val],idx_to_remove) self.myMap[last_val].insert(insert_pos,idx_to_remove) self.stack[idx_to_remove],self.stack[-1] = self.stack[-1],self.stack[idx_to_remove] self.stack.pop() else: self.stack.pop() tmp.pop() return True else: return False def getRandom(self): """ Get a random element from the collection. :rtype: int """ return random.choice(self.stack) The following is a similar code using Sets. I am not sure why does this even work.
from collections import defaultdict import random class RandomizedCollection: def __init__(self): """ Initialize your data structure here. """ self.nums = [] self.num_map = defaultdict(set) def insert(self, val): """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. :type val: int :rtype: bool """ self.nums.append(val) self.num_map[val].add(len(self.nums) - 1) return True def remove(self, val): """ Removes a value from the collection. Returns true if the collection contained the specified element. :type val: int :rtype: bool """ if len(self.num_map[val]) == 0: return False index = self.num_map[val].pop() last_index = len(self.nums) - 1 if not (index == last_index): last_val = self.nums[last_index] self.nums[index] = last_val self.num_map[last_val].remove(last_index) self.num_map[last_val].add(index) self.nums.pop() return True def getRandom(self): """ Get a random element from the collection. :rtype: int """ return self.nums[random.randint(0, len(self.nums) - 1)] 1 Answer
Sets in python have no guarantee regarding to order. In fact it is common when order is not maintained. For example, on my Python-2.7 and 3.5.2 implementations:
>>> a = set([3,10,19]) >>> a set([19, 10, 3]) >>> a.add(1) >>> a set([19, 1, 10, 3]) >>> a.pop() 19 >>> a.pop() 1 >>> a set([10, 3]) Order is sometimes maintained with set because this is the way hash-tables work. Usually the set starts as a hash table that has size=a*len(hash_table) buckets. Element value is inserted into bucket number value % size. For small and dense integers value < size. This means that in such cases value is inserted at bucket number value, which is the sorting order of the values.
This is to show that it should be no surprise when set maintains a sorted order in some cases, but this is besides the point. The point is why the RandomizedCollection class works.
Actually, both implementations of RandomizedCollection have the same conceptual data-structure. The self.stack of the list-based variant is read and updated in exactly the same way as self.nums of the set-based variant. They both maintain a flat list of all elements in the RandomizedCollection object.
The list-based implementation uses the fact that self.myMap[val] is a sorted list only in remove() at:
last_val = self.stack[-1] self.myMap[last_val].pop() ## removes the last index Since self.myMap[last_val] is a sorted list of indices, its last element must be the last last_val element in self.stack. Since last_val was taken from the end of self.stack, then the last element of self.myMap[last_val] is guaranteed to point to len(self.stack)-1). This means that popping the last elements of both self.stack and self.myMap[last_val] will keep the data-structure consistent. Other than the above two lines, making self.myMap[val] a sorted list only incurs costs. Searching for index in the list is O(log K) and insertion is O(K).
The set-based solution works on a different order. Instead of removing the index that points to the end of the stack in O(1) by:
self.myMap[last_val].pop() # (Sorted list variant) It erases the same element by using O(1) capabilities of set:
self.num_map[last_val].remove(last_index) The effect is the same. In both cases, the map no longer points to the last element on the stack. There is no need for the set to be ordered, only to be able to remove elements in O(1). Eventually, the last element on the stack will be removed by a simple self.stack.pop() or self.nums.pop().
Sometimes it is not the last element that had to be removed, but the code removed it anyway. The idea is to then remove the correct element, and put the "wrongly" removed element in its stead. The solution with the sorted list works hard in O(K) to reinsert the removed element:
insert_pos = bisect.bisect_left(self.myMap[last_val],idx_to_remove) self.myMap[last_val].insert(insert_pos,idx_to_remove) In the case of the set this is quite simple, since no order is required:
self.num_map[last_val].add(index) And finally, the array that contains the actual values (self.nums and self.stack) is updated so that the last element is finally removed, and reinserted instead of the element that should have been removed in the first place.
To summarize, both data-structures are equivalent. In one, the set of indexes is maintained as a sorted-list and in another as set. The code in the sorted-list variant sometimes takes advantage of the fact that the list is sorted, in order to remove the largest element in O(1). However, for the set case no such optimization is required, since removing any element is O(1), and remove() can be used instead of pop(). 1
