Microdict

一个高性能的Python散列表库，通常比Python字典更快，并且消耗的内存显著更少。它目前支持Python 3.5及以上版本。

为什么是Microdict？为什么需要创建另一个散列表库，当Python内置了字典时？

Python 字典运行速度快，但内存消耗也可能很高。这主要归因于 Python 将数据以 PyObjects 的形式存储在内存中，其内存消耗远大于整数和字符数组等本地类型。因此，在构建内存密集型 Python 应用程序时，Python 字典在很多情况下可能会成为限制因素。这促使我开发了一个类型化的 Python 哈希表库，其内存消耗显著（最多减少 7 倍）低于 Python 字典。它也比 Python 字典更快。此外，其底层的 C 实现还可以超越 Google 的经过高度优化的 Swiss Table 和 Facebook 的 F14 哈希表。请参阅 性能部分。

安装和构建

您可以使用 pip 安装 Microdict： pip install microdict。

Microdict 完全使用 C 扩展构建，因此构建它需要 Python C API 头文件。克隆存储库后，请在终端中使用 python setup.py install 命令构建和安装软件包。Microdict 已在 Linux、Mac OSX 和 Windows 系统上进行了测试。在 Linux/mac osx 系统上，您需要 GCC 7+，在 Windows 系统上需要 Visual C++ 14+ 编译器来构建软件包。为了获得最佳性能，请使用 64 位系统。

运行测试

安装完成后，请在您的 Python 解释器中输入以下代码片段以运行测试

from microdict import run_tests
run_tests.run()

用法

以下代码片段显示了库的常见用法。

from microdict import mdict

dict_i32 = mdict.create("i32:i32") # Generates a dictionary with key and value type of signed 32 bit integer.
dict_i32[1] = 2 # Just like python dictionaries, setting a key value pair.
try:
   print(4 in dict_i32) # prints False after catching a KeyError exception.
except KeyError:
   pass

print(dict_i32[1]) # prints 2
try:
   print(dict_i32.pop(4)) # prints None.
except KeyError:
   pass
print(dict_i32.pop(1)) # Removes [1,2] from the hashtable and prints 2.

dict_i32[10] = 0
dict_i32[5] = 1
dict_i32[6] = 8

for k in dict_i32:
   print(k) # Will print 10, 5, 6

for v in dict_i32.values():
   print(v) # Will print 0, 1, 8

for k,v in dict_i32.items():
   print(k,v) # Will print all the items.

d2 = dict_i32.copy() # Creates a deep copy of dict_i32.
dict_i32.clear([10,6]) # Removes the pairs [10,0] and [6,8]
dict_i32.clear() # Makes the dictionary empty.

pydict = d2.to_Pydict() # Returns a python dictionary containing all the items in d2
pydict[120] = 5
pydict[42] = 9

d2.update(pydict) # d2 now will additionally have the pairs [120, 5] and [42, 9]

dict_i32[111] = 89
dict_i32[123] = 1
d2.update(dict_i32) # d2 now will additionally have the pairs [111, 89] and [123, 1].

print(list(d2.items())) # prints all d2 items
"""
Faster approach shown below. d2.get_items() creates and returns a list of all items. 
So if you don't need a list container, iterate using d2.items() for memory efficiency. 
Same applies for other d2.get_* methods shown below.
"""
print(d2.get_items()) # 
print(list(d2.values())) # prints all d2 values
print(d2.get_values()) # Same but faster approach
print(list(d2)) # prints all d2 keys
print(d2.get_keys()) # Same but faster approach

哈希表类型

目前，Microdict 包含 5 种类型的字典

• "i32:i32" -> 32 位有符号键和 32 位有符号值
• "i32:i64" -> 32 位有符号键和 64 位有符号值
• "i64:i32" -> 64 位有符号键和 32 位有符号值
• "i64:i64" -> 64 位有符号键和 64 位有符号值
• "str:str" -> 字符串键和字符串值。

方法文档

• microdict.mdict.create (dtype, key_len=None, val_len=None)

  : 返回一个 Microdict 哈希表，类型可以是上述任意一种。

  参数

  • dtype: 一个 Python 字符串类型（str），用于设置要创建的哈希表类型。可以是上述任意一种 类型。
  • key_len: 一个 Python 整数类型（int）。它设置键（UTF-8 字符串）字符的最大字节数。如果传递的 UTF-8 编码字符串键消耗的字节数大于 key_len，则不会接受。此参数仅适用于 dtype="str:str"。它只接受最多 65355 的值，更大的值将引发 TypeError。
  • val_len: 一个 Python 整数类型（int）。它设置值（UTF-8 字符串）字符的最大字节数。如果传递的 UTF-8 编码字符串值消耗的字节数大于 val_len，则不会接受。此参数仅适用于 dtype="str:str"。它只接受最多 65355 的值，更大的值将引发 TypeError。

• microdict.mdict.listDictionaryTypes ()

  : 打印一系列形式为 键类型: key_t . 值类型: val_t 的行，其中 key_t:val_t 形成上述 类型。

以下是在 mdict.create 返回的所有哈希表类型中常见的通用方法。

• clear (key_list = None)

  : 返回 None。如果未提供 key_list，则 clear 方法将删除哈希表中的所有项。

  参数

  • key_list: 这是一个可选参数，但不是关键字可选参数（关键字参数必须不提供）。所以，可以这样使用：keys = [1,2]; d.clear(keys)。如果提供了，它必须是 list 类型。key_list 中的条目是要从哈希表中删除的键。默认情况下，哈希表中不存在的任何条目都将被跳过。对于任何整数哈希表类型，任何非 Python int 条目都将被跳过。程序员需要传递正确大小的整数以防止溢出。对于 str:str 类型，条目必须是 Python UTF-8 字符串，UTF-8 字符字节最多为 key_len，由 mdict.create 设置，否则，该条目将被跳过。

• copy ()

  : 返回与调用者哈希表对象相同类型的 Microdict 哈希表的深拷贝。

• get_items ()

  : 创建并返回一个包含哈希表中所有项（键，值）的 Python list。

• get_keys ()

  : 创建并返回一个包含哈希表中所有键的 Python list。

• get_values ()

  : 创建并返回一个包含哈希表中所有值的 Python list。

• items ()

  : 用于使用 for 循环遍历项。例如：for k,v in d.items() : print(k, v)。

• pop (key)

  : 从哈希表中删除 key 并返回其对应值。如果 key 不存在，则引发 KeyError。

  参数

  • key: 对于任何整数哈希表类型，任何非 Python int 条目将引发 TypeError。程序员需要传递正确大小的整数以防止溢出。对于 str:str 类型，条目必须是 Python UTF-8 字符串，UTF-8 字符字节最多为 key_len，由 mdict.create 设置，否则，将引发 TypeError。

• to_Pydict ()

  : 创建并返回一个包含 Microdict 哈希表中所有项的 Python 字典。

• update (dictionary)

  : 将字典中存在的所有项插入到 Microdict 哈希表中。

  参数

  • dictionary: 必须是 Python 字典或 Microdict 哈希表。如果是 Python 字典，则所有与 Microdict 哈希表类型相同的项将被插入。默认情况下，其他项将被跳过。与 clear 方法文档中关于类型约束的条件也适用于此处。

• values ()

  : 用于使用 for 循环遍历值。例如：for v in d.values() : print(v)。

性能

与 Python 字典竞争

下表中的每个单元格的格式为（速度增益，空间增益）。

• 速度增益的定义如下：。

• 同样，空间增益：

对类型"i32:i32"、"i64:i64"、"str:str"（键和值长度均保持为8个字符）进行了实验。通过平均使用（独特）随机生成数据进行的30次实验的结果来计算速度提升和空间提升。空间消耗使用psutil库进行计算。时间消耗使用time.perf_counter方法进行计算。所有实验均在Python 3.8.2和64位Ubuntu 20.04 LTS系统上完成。以下表格显示了使用完整键集和[]运算符检索所有值时与Python字典的基准测试。

与Google的Swiss Table和Facebook的F14竞争

Microdict的底层C实现与Swiss Table->abseil::flat_hash_map和F14->folly::F14FastMap进行了基准测试，以进一步测试其功能。数据类型使用上述相同设置进行设置。以下表格显示了使用键检索所有值的结果。