<jupyter_start><jupyter_text>This [**collections**](https://docs.python.org/3/library/collections.htmlmodule-collections) module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, `dict`, `list`, `set`, and `tuple`.**Link to other Notebooks:**- [basic_python.ipynb](https://colab.research.google.com/drive/1GG4qrTubAGu1p0JvJ4dt5UVOI2jHTL8lscrollTo=fbS3rOL3HbIW)- [data_structure.ipynb](https://colab.research.google.com/drive/1NII-_1t4H1gD-dI7CavJa-7VltibUyLpscrollTo=zgIIuZ-97fLW)  [defaultdict](https://docs.python.org/3/library/collections.htmlcollections.defaultdict)`class collections.defaultdict(default_factory=None, /[, ...])`dict subclass that calls a __factory function__ to supply missing values<jupyter_code>from collections import defaultdict
hash_map = defaultdict(list)
hash_map[0].append("first value")
print(hash_map[0])
hash_map = defaultdict(int)
print(hash_map[0])
hash_map[0] += 1
print(hash_map[0])
# self-defined factory function
def factory():
  return [set(), set()]

hash_map = defaultdict(factory)
print(hash_map[0])

hash_map[0][0].add("1")
hash_map[0][1].add("2")
print(hash_map[0])
hash_map = defaultdict()
hash_map.default_factory = hash_map.__len__  # 新key的默认value是当前hash_map的len

a = "a"
b = "b"

print(f"hash_map[1, 2, 3]:\t {hash_map[1, 2, 3]}")  # dict key可以是tuple的
print(f"hash_map[a]:\t\t {hash_map[a]}")  
print(f"hash_map[b]:\t\t {hash_map[b]}")
print(f"hash_map[b]:\t\t {hash_map[b]}")
# Example: use defaultdict as counters

words = ["i","love","leetcode","i","love","coding"]

# using defaultdict
counter = defaultdict(int)
for word in words:
    counter[word] += 1
print(counter)
for key, val in counter.items():
    print(f"key: {key}, \t val: {val}")<jupyter_output>key: i, 	 val: 2
key: love, 	 val: 2
key: leetcode, 	 val: 1
key: coding, 	 val: 1<jupyter_text>[Counter](https://docs.python.org/3/library/collections.htmlcollections.Counter)`class collections.Counter([iterable-or-mapping])`dict subclass for counting hashable objects<jupyter_code>from collections import Counter
c = Counter(['eggs', 'ham', 'eggs'])
c
# it is a dictionary
isinstance(c, dict)
# Return an iterator over elements repeating each as many times as its count.
c.elements()  
sorted(c.elements())
# Return a list of the n most common elements and their counts from the most common to the least.
# Elements with equal counts are ordered in the order first encountered:
c.most_common(1)
from collections import Counter
c = Counter()
print(f"c['123']:\t {c['123']}")  # 遇到新的idx, 默认counter值是0
c["123"] += 1
print(f"c['123']:\t {c['123']}")<jupyter_output>c['123']:	 0
c['123']:	 1<jupyter_text>[OrderedDict](https://docs.python.org/3/library/collections.htmlcollections.OrderedDict)`class collections.OrderedDict([items])``Ordered dictionaries` are just like regular `dictionaries` but have some extra capabilities relating to ordering operations.- `popitem(last=True)`- `move_to_end(key, last=True)`**Internal Implementation Detail**:It is implemented by `dict` and `DoublyLinkedList` (ref: [cpython source code](https://github.com/python/cpython/blob/ed1671ced7c9b951dfc16a0cf32a2b4eab914cf1/Lib/collections/__init__.pyL78))<jupyter_code>from collections import OrderedDict


# basic ordering property 
hash_map1 = OrderedDict()

hash_map1["name"] = "Chet"
hash_map1["gender"] = "M"
hash_map1["age"] = "18"
hash_map1
hash_map2 = OrderedDict()

hash_map2["gender"] = "M"
hash_map2["name"] = "Chet"
hash_map2["age"] = "18"
hash_map2
hash_map1 != hash_map2<jupyter_output><empty_output><jupyter_text>LRUCache<jupyter_code>from collections import OrderedDict


class LRUCache:
    """
    Least recently used cache:
    Any updates or get will require least recently used record to be deleted
    """
    def __init__(self, capacity) -> None:
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        """
        return value of the key if key exist, else return -1
        
        Time Complexity:  O(1)
        Space Complexity: O(1) 
        """
        if key in self.cache:
            self.cache.move_to_end(key, last=True)
        
        return self.cache.get(key, -1)
    

    def put(self, key: int, value: int) -> None:
        """
        update value of key if key exists, otherwise add the key-value pair to the cache;
        if the number of keys exceeds the capacity, then evict the least recently used key.

        Time Complexity:  O(1)
        Space Complexity: O(1) 
        """
        if key in self.cache:  # inplace update
            self.cache.move_to_end(key, last=True)
            self.cache[key] = value
        else:  # add a new item
            if len(self.cache) == self.capacity:  # need to delete least recently used item
                self.cache.popitem(last=False)
                self.cache[key] = value
            else:
                self.cache[key] = value
lru = LRUCache(2)

lru.put(1, 1)
print(f"lru_cache: {lru.cache}")
lru.put(2, 2)
print(f"lru_cache: {lru.cache}")
val = 1
print(f"lru get {val}: {lru.get(val)}")
print(f"lru_cache: {lru.cache}")
lru.put(3, 3)
print(f"lru_cache: {lru.cache}")
val = 2
print(f"lru get {val}: {lru.get(val)}")
print(f"lru_cache: {lru.cache}")
lru.put(1, 10)
print(f"lru_cache: {lru.cache}")<jupyter_output>lru_cache: OrderedDict([(3, 3), (1, 10)])<jupyter_text>[deque](https://docs.python.org/3/library/collections.htmlcollections.deque)`class collections.deque([iterable[, maxlen]])`list-like container with fast appends and pops on either end.Deques are a generalization of `stacks` and `queues` (the name is pronounced “deck” and is short for “double-ended queue”). Deques support **thread-safe**, memory efficient appends and pops from either side of the deque with approximately the same `O(1)` performance in either direction.- append- appendleft- pop- popleft- etc.<jupyter_code>from collections import deque

queue = deque()

queue.append(1)
queue.append(10)
queue.append(100)

print(queue)
while queue:
    val = queue.popleft()
    print(val)
from collections import deque

queue = deque([1, 10 ,100])

print(queue)

while queue:
    val = queue.pop()
    print(val)
# adding list as iterables to deque
from collections import deque


queue = deque([], maxlen=2)

queue.append([1, 10])
queue.append([2, 20])
print(queue)

queue.append([3, 30])
print(queue)
for key, value in queue:
    print(f"key: {key}, value:{value}")<jupyter_output>key: 2, value:20
key: 3, value:30<jupyter_text>[namedtuple](https://docs.python.org/3/library/collections.htmlcollections.namedtuple)`Named tuples` assign meaning to each position in a tuple and allow for more readable, self-documenting code. They can be used wherever regular `tuples` are used, and they add the ability to access fields by name instead of position index.> Like `dictionaries`, they contain keys that are hashed to a particular value. But on contrary, it supports both access from key-value and iteration, the functionality that dictionaries lack.ref: https://www.geeksforgeeks.org/namedtuple-in-python/>`namedtuples` compare on values only (ordered). They are designed to be a drop-in replacement for regular tuples, with named attribute access as an added feature. The field names will not be considered when making equality comparisons. It may not be what you wanted nor expected from the namedtuple type! This differs from dict equality comparisons, which do take into account the keys and also compare order agnostic.ref: https://stackoverflow.com/a/43921348/8280662<jupyter_code># Python code to demonstrate namedtuple()
 
from collections import namedtuple
 
# Declaring namedtuple()
Student = namedtuple('Student', ['name', 'age', 'DOB'])
 
# Adding values
s1 = Student('Nandini', '19', '2541997')
s2 = Student(name='Chet', age='25', DOB='22/07/1993')
print(s1)  # readable __repr__ with a name=value style
print(s2)
# Assigning attributes with a default value is also possible
TransactionDefault = namedtuple('TransactionDefault',['sender','receiver','date','amount'], 
                                defaults=['jojo', 'xiaoxu', None, None])
print(TransactionDefault())
# default value is assigned to the last attribute because non-default argument cannot follow default argument
TransactionDefault2 = namedtuple('TransactionDefault2',['sender','receiver','date','amount'], 
                                 defaults=[None])
print(TransactionDefault2('luffy', 'chet', '2020'))
# namedtuple from dictionary
name_counter = {"chet": 3, "zoe": 3, "xixi": 2, "haha": 1}

NameCounter = namedtuple("NameCounter", name_counter)  #  just pass the keys of a dict directly
NameCounter(**name_counter)  # create tuple instances from this dict, or any other dict with matching keys
# Access using index just like plain tuple
print("The Student age using index is : ", end="")
print(s1[1])
print()

# Access using name
print("The Student name using keyname is : ", end="")
print(s1.name)
print()

# Access using getattr()
print("The Student DOB using getattr() is : ", end="")
print(getattr(s1, 'DOB'))
print()

# unpack like a regular tuple
name, age, DoB = s1
print(f"{name}, {age}, {DoB}")

# _asdict
s1._asdict()<jupyter_output>The Student age using index is : 19

The Student name using keyname is : Nandini

The Student DOB using getattr() is : 2541997

Nandini, 19, 2541997<jupyter_text>`tuple` is an **immutable** data type, but if the attribute itself is **mutable** like list, you are allowed to change the elements inside the list without letting the tuple be aware of the change.<jupyter_code># Assign the attribute

Transaction = namedtuple("Trasction", ["sender", "receiver"])

record = Transaction(sender=["jojo", "kiki"], receiver="chet")
id1 = id(record)
record
record.sender[1] = "gaga"
id2 = id(record)
record
id1==id2
print(record.receiver)
record.receiver="sheng"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13214790866841786, 'fraction_numerical': 0.02455041422509598, 'mean_word_length': 4.77201166180758, 'pattern_counts': {'":': 4, '<': 24, '<?xml version=': 0, '>': 29, 'https://': 11, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '131378', 'license': 'Apache-2.0', 'n_tokens_mistral': 3413, 'n_tokens_neox': 3257, 'n_words': 941, 'path': 'Python/collections.ipynb', 'repo_name': 'Chet-Sheng/Speedy', 'size': '9898'}