Collections | OmniBBFB

最近用到了Python中的collections模块，就索性整理了一下。

`from collections import *`

在Python官方术语对照表中或是使用print(collections.__doc__)有

This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.

即collections模块中提供了一些相比传统容器（字典、列表、集合以及元组）更高级的容器数据类型。包括~~（凑字数）~~：

namedtuple: factory function for creating tuple subclasses with named fields （一个工厂函数，用来创建元组的子类，子类的字段是有名称的。）
deque: list-like container with fast appends and pops on either end （类似列表的容器，但 append 和 pop 在其两端的速度都很快。）
ChainMap: dict-like class for creating a single view of multiple mappings （类似字典的类，用于创建包含多个映射的单个视图。）
Counter: dict subclass for counting hashable objects （用于计数可哈希(hashable)对象的字典子类）
OrderedDict: dict subclass that remembers the order entries were added （字典的子类，能记住条目被添加进去的顺序。）
defaultdict: dict subclass that calls a factory function to supply missing values （字典的子类，通过调用用户指定的工厂函数，为键提供默认值。）
UserDict: wrapper around dictionary objects for easier dict subclassing （封装了字典对象，简化了字典子类化）
UserList: wrapper around list objects for easier list subclassing （封装了列表对象，简化了列表子类化）
UserString: wrapper around string objects for easier string subclassing （封装了字符串对象，简化了字符串子类化）

工厂方法

上文提到，稍作整理，遇事不决，问GPT。

Prompt: Python 中的工厂方法设计模式

Reply:

在 Python 中实现工厂设计模式是一种常用的设计模式，使得创建对象的过程更加灵活和模块化。工厂设计模式用于创建一个接口，用以创建对象，但是实际的实例化过程会延迟到子类中完成。这种模式的主要好处是能够更好地管理对象的创建过程，尤其是当对象的创建逻辑比较复杂时。

简单工厂模式、工厂方法模式和抽象工厂模式是工厂设计模式的三种变种。

以下是工厂方法模式的一个 Python 示例：

# 工厂方法模式

# 抽象产品类
class Animal:
    def speak(self):
        pass

# 具体产品类
class Dog(Animal):
    def speak(self):
        return "Woof!"

class Cat(Animal):
    def speak(self):
        return "Meow!"

# 抽象工厂类
class AnimalFactory:
    def get_animal(self, animal_type):
        raise NotImplementedError

# 具体工厂类
class ConcreteAnimalFactory(AnimalFactory):
    def get_animal(self, animal_type):
        if animal_type == "dog":
            return Dog()
        elif animal_type == "cat":
            return Cat()
        else:
            raise ValueError("Unknown animal type")

# 客户端代码
def animal_speak(animal_type):
    factory = ConcreteAnimalFactory()
    animal = factory.get_animal(animal_type)
    print(animal.speak())

# 测试
animal_speak("dog") # 输出 "Woof!"
animal_speak("cat") # 输出 "Meow!"

在上面的例子中，Animal 类是一个抽象的产品类，定义了一个抽象方法 speak()。Dog 和 Cat 是具体的产品类，它们继承自 Animal 类并且实现了 speak 方法。AnimalFactory 是一个抽象的工厂类，它定义了一个方法 get_animal。ConcreteAnimalFactory 是具体的工厂类，实现了 get_animal 方法，以根据不同的输入参数（在这种情况下是字符串 “dog” 或者 “cat”）返回不同的产品实例。

客户端代码就是使用 ConcreteAnimalFactory 类来生成 Dog 或 Cat 的实例，并调用它们的 speak() 方法。

这样的设计模式允许你在不直接依赖于具体类的情况下创建对象，使得增加新的产品类更加灵活并且遵循面向对象设计原则中的开闭原则（对扩展开放，对修改封闭）。

综上可得工厂方法设计模式中的基本关系：

具体产品类继承抽象产品类并实现/覆写抽象交互方法为具体交互方法
具体工厂类继承抽象工厂类并实现/覆写抽象生产方法为具体生产方法（称为工厂方法），后者根据输入生产具体产品（类的实例）
客户端函数调用具体工厂（类的实例）的具体生产方法生产具体产品（类的实例）

这里是另一个不错的代码示例。

namedtuple 命名元组

命名元组可以通过名称而不是下标访问元组元素。

直接使用namedtuple方法将创建一个类tuple的子类，其实例为命名元组：

NT = collections.namedtuple('typename', ['field_name_1', 'field_name_2'])  
values = ['value1', 'value2']  
nt = NT(*values)  
print(nt)  
  
# typename(field_name_1='value1', field_name_2='value2')

或者使用_make方法从可迭代对象创建。其和字典的区别在于没有字典，即使用了__slots__方法，因此存储代价更小，使用_asdict方法可以创建对应的字典。并且命名元组是不可变的，使用_replace方法更改将创建一个新命名元组：

new_nt = nt._replace(field_name_1='new_value1', field_name_2='new_value2')  
print(nt)  
print(new_nt)  
  
# typename(field_name_1='value1', field_name_2='value2')  
# typename(field_name_1='new_value1', field_name_2='new_value2')

另外，可以使用defaults参数为命名元组“靠右”赋默认值，以及_fields属性和_fields_defualts属性自省：

NT = collections.namedtuple('tn', ['fn_1', 'fn_2'], defaults=[3])  
values = ['value1', 'value2']  
nt = NT(*values)  
print(nt)  
print(nt._fields)  
print(nt._field_defaults)

# tn(fn_1='value1', fn_2='value2')  
# ('fn_1', 'fn_2')  
# {'fn_2': 3}

参考：

deque 双端队列

虽然列表也有pop方法和append方法，可以充当栈或队列，但是在列表的开头插入或删除元素的时间复杂度为 O(N) ，而在双端队列两端插入或删除元素时间复杂度都是 O(1) ，因此后者更适合充当栈或队列。

顾名思义，双端队列自带各种左端方法，如popleft，appendleft和extendleft。一个比较常用的参数是maxlen，通过限制长度可以保留有限历史记录。

这里还介绍了在deque中放入迭代器，实现轮询调度器：

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    iterators = deque(map(iter, iterables))
    while iterators:
        try:
            while True:
                yield next(iterators[0])
                iterators.rotate(-1)
        except StopIteration:
            # Remove an exhausted iterator.
            iterators.popleft()

记录：

Prompt: 轮询调度器

Reply:

轮询调度器（Round-Robin Scheduler）是一种操作系统中用于CPU调度的算法。它是时间片调度的一个非常简单和公平的例子，也被用在其他类型的调度（如网络调度）中。在轮询调度中，每个进程被分配一个固定时间的时间片（quantum），在这段时间内可以运行。当时间片用完后，如果该进程还没有完成，它会被放回到队列的末尾，等待下一次被调度。

轮询调度的特点是所有的进程被平等对待，并按照顺序获取CPU时间。这避免了优先级较低的进程饿死（即永远得不到足够的CPU时间）的情况发生。由于每个进程都获得了相同的时间片，这种调度算法通常被认为是相对公平的。

举一个简单的例子，设想我们有三个进程（P1、P2和P3），每个进程需求的处理时间分别是 20ms、25ms和30ms，而我们的轮询调度器分配的时间片是 10ms。调度会按照以下方式进行：

P1运行10ms，满时间片，但未完成，回队列末尾。
P2运行10ms，满时间片，但未完成，回队列末尾。
P3运行10ms，满时间片，但未完成，回队列末尾。
P1再次获得10ms，完成后剩余时间片未用完。
P2再次获得10ms，满时间片，未完成，回队列末尾。
P3再次获得10ms，满时间片，未完成，回队列末尾。
由于P1已完成，轮到P2继续运行，最后5ms运行完成。
P3运行最后10ms，完成。

这种方式下，尽管进程需要不同的处理时间，他们还是能够按照公平的顺序来获得CPU处理时间。然而轮询调度的缺点是可能导致运行效率的问题，因为每个时间片的结束都可能涉及到上下文切换，这在有大量进程时可能会引起显著的开销。此外，轮询调度不一定能提供最佳的响应时间，尤其是对于有交互的应用程序来说。

为了优化性能，操作系统会根据实际情况设计更加复杂的调度算法，例如优先级调度、多级队列调度等，以平衡响应时间和系统利用率。

参考：

ChainMap 链映射

假设现在有一堆字典，链映射类可以在内部创建一个容纳这些字典的列表并重新定义一些常见的字典操作来遍历这个列表，其实例仍然可以看成一个“字典”。一个例子是，回忆对象的属性字典和类的MRO：

访问对象的属性时会依次搜索自身，所属类及其父类（按照MRO）的属性字典
MRO中子类在左父类在右

理解这个例子也就理解了new_chlid方法和parents属性：

dict_1 = {'x': 1}  
dict_2 = {'x': 2}  
dict_3 = {'x': 3}  
cm = collections.ChainMap(dict_2, dict_1)  
print(cm)  
print(cm.maps)  
print(cm.new_child(dict_3))  
print(cm.parents)  
  
# ChainMap({'x': 2}, {'x': 1})  
# [{'x': 2}, {'x': 1}]  
# ChainMap({'x': 3}, {'x': 2}, {'x': 1})  
# ChainMap({'x': 1})

参考：

Counter 计数器

计数器类是类dict的子类，特别地，也是类defaultdict的子类，因此返回一个计数字典，并且可以使用total方法计算总数，使用most_common方法返回最常见元素及其出现次数的列表。另外由于计数字典的值都是整数，可以进行加减，交并，比较以及取正负部的操作，并且每次运算之后非正部分在字典中不会被保留。

most_common example

ct1 = collections.Counter(x=1, y=2, z=3)  
ct2 = collections.Counter(x=3, y=2, z=1)  
ct3 = collections.Counter(x=-1, y=0, z=1)  
print(ct1 + ct2)  
print(sorted((ct1 - ct2).elements()))  
print(ct1 & ct2)  
print(-ct3)  
print(-(ct1 - ct2))  
  
# Counter({'x': 4, 'y': 4, 'z': 4})  
# ['z', 'z']  
# Counter({'y': 2, 'x': 1, 'z': 1})  
# Counter({'x': 1})  
# Counter()

另外，每次运算之后非正部分是直接扔掉不再保留的。

参考：

OrderedDict 有序字典

有序字典旨在擅长重新排序操作。空间效率、迭代速度和更新操作的性能是次要的。一个有序字典的大小是一个普通字典的两倍，因为它内部维护着另外一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。

参考：

defaultdict 默认字典

默认字典可以省去字典添加键值对时的if not in。其由default_factory属性实现，举个栗子：

dd = collections.defaultdict(list)  
dd['key'].append('value')  
print(dd)  
print(dd.default_factory)  
  
# defaultdict(<class 'list'>, {'key': ['value']})  
# <class 'list'>

可以直接对列表进行操作，而不需要检查键是否已经存在，原因在于键查询失败时default_factory属性会调用所给的工厂函数提供一个实例作为默认值。另外默认字典还定义了一个__missing__方法，用于调用default_factory属性中的工厂函数初始化键值对，如果工厂函数为None则会抛出KeyError异常：

dd.__missing__('key')  
print(dd)  
dd.default_factory = None  
dd.__missing__('key')  
  
# defaultdict(<class 'list'>, {'key': []})  
# KeyError: 'key'

这里提供了一个技巧以递归定义默认字典，使得默认字典的值也是默认字典：

foo = lambda: collections.defaultdict(foo)  
dd = foo()  
print(dd)  
print(type(dd['key']))  
  
# defaultdict(<function <lambda> at 0x0000021BBC31E2A0>, {})  
# <class 'collections.defaultdict'>

参考：

UserDict, UserList, UserString

这三兄弟分别是封装了字典，列表和字符串对象的类，适用于那些想要自定义这些数据结构的高叟，主要是为了避免继承和覆写时可能产生的一些问题。

from collections import *#

工厂方法#

namedtuple 命名元组#

deque 双端队列#

ChainMap 链映射#

Counter 计数器#

OrderedDict 有序字典#

defaultdict 默认字典#

UserDict, UserList, UserString#