nanoset.py

Python空集合的内存优化包装器。

⏱️ TL;DR

使用一行代码将代码中空set实例使用的内存减少高达85%

from nanoset import PicoSet as set

🚩 目录

• 概述
  • 关于Python内存使用
  • 简单示例用例
  • 实现
  • 统计
• 安装
• API参考
• 许可证

🗺️ 概述

🐏 关于Python内存使用

Python 是一种优秀的编程语言（来辩），但有时你会质疑为什么它会以某种方式做事。自 Python 2.3 以来，标准库提供了 set 集合，这是一个专门用于成员资格测试的容器。与无处不在的 list 集合相反，set 是无序的（或者更准确地说，不允许你访问它存储元素的方式）。set 的另一个特性是，就像它的数学对应物一样，它不允许重复项，这在某些算法中非常有用。然而，集合是内存密集型的

>>> import sys
>>> sys.getsizeof(list())
56
>>> sys.getsizeof(set())
216

一个空集合比一个空列表多占用三倍以上的内存！对于具有许多 set 属性的数据结构或对象，它们可以快速导致大量内存被浪费。当你习惯了 Rust（大多数 collections 都会惰性分配）时，这更加令人沮丧。这就是 nanoset 走进来救场的地方：

>>> import nanoset
>>> sys.getsizeof(nanoset.NanoSet())
48
>>> sys.getsizeof(nanoset.PicoSet())
32

实际上，这只是一个谎言，但请继续阅读.

💡 简单示例用例

让我们假设我们正在构建一个有序的图数据结构，我们可能想要存储 分类数据 或任何其他类型的层次结构。我们可以简单地使用以下两个类来定义图及其节点

class Graph:
    root: Node
    nodes: Dict[str, Node]

class Node:
    neighbors: Set[node]

这使得添加边和查询两个节点之间是否存在边成为 O(1) 操作，遍历所有节点成为 O(n) 操作，这很可能是我们想要的。我们使用 set 而不是 list，因为我们希望避免存储重复的边，这是一个明智的选择。但现在让我们看看 统计 NCBITaxon 项目，这是美国国家生物技术信息中心开发的一个用于有机体分类的数据库

 Metrics
    Number of classes*: 1595237
    Number of individuals: 0
    Number of properties: 0
    Classes without definition: 1595237
    Classes without label: 0
    Average number of children: 12
    Classes with a single child: 40319
    Maximum number of children: 41761
    Classes with more than 25 children: 0
    Classes with more than 1 parent: 0
    Maximum depth: 38
    Number of leaves**: 1130671

根据这些数据，我们将有 1,130,671 个叶子节点，总共有 1,595,237 个节点，这意味着 70.8% 的空集合。现在你可能认为

好的，我明白了。但在这个例子中，我只需要一个特殊的叶子节点用例，当这个集合为空时，我不存储空的 neighbors 集合，而是存储一个对 None 的引用。然后，当我想从这个节点添加新边时，我可以将这个引用替换为实际的集合。问题解决了！

很高兴我们处于同一水平：这就是 nanoset 为你解决的问题！

🔨 实现

实际上，这根本不是魔法。只需想象一个名为 NanoSet 的类，它作为它所包装的实际 Python set 的代理工作，但只有在需要实际存储数据时才会分配

class NanoSet(collections.abc.Set):

    def __init__(self, iterable=None):
        self.inner = None if iterable is None else set(iterable)

    def add(self, element):
        if self.inner is None:
            self.inner = set()
        self.inner.add(element)

    # ... the rest of the `set` API ...

就是这样！然而，以这种方式在 Python 中做并不会非常高效，因为生成的对象将是 48 字节。使用 slots，这可以减少到 40 字节，这与我们得到的 NanoSet 相当。

注意，这些值仅在内部集合为空时有效！当实际分配集合以存储我们的值时，我们将额外分配 232 字节的数据。这意味着使用 NanoSet 会造成开销，因为非空集合现在将重 264 字节（248 字节用于 PicoSet）。

当时我的方法是将 Optional[Set] 存储在所有地方，效果非常好，我不想为非空集付出任何额外成本！

当然。但这意味着要更改你的整个代码。实际上，与使用 nanoset 相比，你可能不会从这样做中获得很多内存，因为包装器性能不佳的唯一时间是负载因子超过 90% 的时候。此外，仅为了给你一些参考，sys.getsizeof(1) 是 28 字节。

顺便问一下，你没有提到 PicoSet。你是怎么把那东西缩小到 32 字节的，因为槽位化的 Python 对象不可能小于 40 字节？

很简单：PicoSet 基本上是 NanoSet，但没有实现 垃圾回收协议。这为我们节省了 8 字节的对象内存，但有一个缺点：垃圾回收器无法看到 PicoSet 内部分配的集合。这不会改变执行，但使用内存分析器进行调试会更困难。以下是一个示例，我们首先使用 NanoSet 分配了 1,000,000 个单例，然后使用 PicoSet，使用 guppy3 检查堆栈。

>>> l = [nanoset.NanoSet({x}) for x in range(1000000)]
>>> guppy.hpy().heap()
Partition of a set of 3036763 objects. Total size = 304996526 bytes.
 Index  Count   %     Size    %   Cumulative %  Kind (class / dict of class)
     0 1000044  33 216105248  71  216105248  71 set
     1 1000000  33  48000000  16  264105248  87 nanoset.NanoSet
     ...
     3     113   0   8716880   3  300851404  99 list
     ...

>>> l = [nanoset.PicoSet({x}) for x in range(1000000)]
>>> guppy.hpy().heap()
Partition of a set of 1036905 objects. Total size = 44998965 bytes.
 Index  Count   %     Size   %   Cumulative  %  Kind (class / dict of class)
     0 1000000  96 32000000  71   32000000   71 nanoset.PicoSet
     1      96   0  8712752  24   32712752   89 list
     ...

在第二次运行中，我们分配的内存量大致相同，节省了 16 MB（将 NanoSet 切换到 PicoSet 时的 1,000,000 个实例节省了 16 字节）。然而，垃圾回收器并不知道一些内存在哪里，因为 PicoSet 隐藏了它分配的集合（这是可以的：它将与 PicoSet 一起被回收）。

因此，我建议在调试时避免使用 PicoSet，这可以通过 Python 的 __debug__ 标志轻松实现。

if __debug__:
    from nanoset import NanoSet as set
else:
    from nanoset import PicoSet as set

这将在使用 -O 标志运行 Python 时导致使用 PicoSet 而不是 NanoSet。

📈 统计数据

好吧，让我们来做一些数学计算。如果分配的集合大小为 S = 232，包装器大小为 s（NanoSet 为 48，PicoSet 为 32），数据结构中非空集合的百分比为 x，那么我们集合的相对大小为

• 如果我们使用 set：S * x / (S * x) = 100%（我们将其用作参考）
• 如果我们使用 nanoset：((S + s) * x + s * (100 - x)) / (S * x)

这给出了以下图表，显示了根据运行时空集合的比例可以节省多少内存

如果我们回到我们的 NCBITaxon 示例，我们有总共 1,595,237 个节点和 1,130,671 个叶子，这意味着在加载整个分类学之后，我们仅通过使用集合就分配了 1,595,237 * 232 = 328.6 MiB 的内存用于 set。然而，如果我们使用 NanoSet，则可以将此减少到 168.7 MiB，甚至使用 PicoSet 可以减少到 144.4 MiB！我们只是通过将 NanoSet 用于 set 而节省了大约 45% 的内存。

🔧 安装

此模块是用 Rust 实现的，但为以下平台编译了本地 Python 轮子：

• Windows x86-64：CPython 3.5, 3.6, 3.7, 3.8
• Linux x86-64：CPython 3.5, 3.6, 3.7, 3.8
• OSX x86-64：CPython 3.5, 3.6, 3.7, 3.8

如果你的平台不在这其中，你需要一个 有效的 Rust nightly 工具链 以及安装 setuptools-rust 库来构建扩展模块。

然后，只需使用 pip 安装即可

$ pip install --user nanoset

📖 API 参考文档

嗯，这是一个针对 set 的综合包装器，所以您可以只阅读标准库文档。除了某些非常特定的边缘情况外，NanoSet 和 PicoSet 都通过了 set 测试套件，该套件位于 CPython。

然而，有一些事情您 不能 做

• 从 PicoSet 或 NanoSet 继承。
• 弱引用 PicoSet 或 NanoSet。
• 在普通的 set 或 frozenset 中检查成员资格，并隐式转换为 frozenset。
• 从 PicoSet 或 NanoSet 创建一个 dict 而不重新散列键。

📜 许可证

本库在开源 MIT 许可证 下提供。