概率型数据结构是为存储集合值而设计的可以让你在一定的时间内或资源约束内回答某些特定的问题这些问题使用其他数据结构难以处理。最重要的事实是答案只可能是正确的或是真实值的近似。并且可以很容易地估计正确答案或其准确性的概率。所以尽管不总是给出正确的答案如果我们接受一定程度的错误仍然可以使用它。有很多具有这样的概率性质的数据结构。每个结构都解决一些具体的问题并且由于它们的随机性就不能在每种情况下都去使用。给一个实际的例子让我们谈谈其中特别受欢迎的一个—HyperLogLog。HyperLogLog参见 https://en.wikipedia.org/wiki/HyperLogLog是一种估算多重集中不同元素数量的算法。使用普通集合你需要存储每个元素这对于非常大的数据集可能是非常不切实际的。HLL 不同于将集合实现作为编程数据结构的经典方式。没有深入到实现细节它只专注于提供集合基数的近似。因此实际值从不被存储。它们无法检索、迭代和测试成员资格。HyperLogLog 在内存中处理时间复杂度和大小的精度以及正确性。例如HLL 的 Redis 实现只需要 12k 字节标准误差为 0.81%对集合大小没有实际限制。使用概率型数据结构是解决性能问题的一种非常有趣的方法。在大多数情况下它是关于某种精确度或正确性的权衡以加快处理速度或更好地利用资源。但它并不总是用于上述场景。概率型数据结构经常用于键/值存储系统中以加速键查找。在这种系统中使用的流行技术之一被称为近似成员查询AMQ。Bloom 过滤器参考 https://en.wikipedia.org/wiki/Bloom_filter就是一个用于此目的有趣的数据结构。缓存当你的应用程序中的某些函数需要很长时间计算时可以考虑的有用的技术是缓存。缓存只是保存一个返回值以供将来参考。可以缓存运行成本高的函数或方法的结果只要• 该函数是确定性的并且每次给定相同的输入时结果具有相同的值• 函数的返回值继续有用并且在一段时间内有效非确定性。换句话说对于同一组参数确定性函数总是返回相同的结果而非确定性函数可能返回随时间变化的结果。这种方法通常可以大大减少计算时间并且还可以节省大量的计算机资源。任何缓存解决方案的最重要的必要条件是拥有一个存储器你可以取回保存的值这通常比重新计算更快。通常以下情况比较适合使用缓存• 查询数据库的可调用项的结果• 渲染为静态值的可调用项的结果例如文件内容Web 请求或 PDF 渲染• 执行复杂计算的确定性可调用对象的结果• 全局映射用于跟踪到期时间的值例如 Web 会话对象• 需要经常和快速访问的结果。缓存的另一个重要的使用案例是保存通过 Web 服务获得的第三方 API 的结果。通过减少网络延迟这可以大大提高应用程序性能如果你需要为每一个 API 请求付费那么这样还可以为你节省费用。根据你的应用程序架构可以有很多种实现缓存的方式并且复杂程度也各不相同。有许多方法提供缓存复杂的应用程序可以在不同级别的应用程序架构堆栈中使用不同的方法。有时高速缓存可以像在进程空间中保存的单个全局数据结构通常为 dict一样简单。在其他情况下你可能需要设置一个专门的缓存服务在精心设计的硬件上运行。本节主要介绍最受欢迎的缓存方法的基本信息并指导你了解常见的使用案例以及常见的陷阱。确定性缓存确定性函数是缓存中最简单并且最安全的使用案例。如果给定完全相同的输入确定性函数总是返回相同的值因此通常可以无限期地存储它们的结果。唯一的限制是用于缓存的存储的大小。缓存这样的结果的最简单的方法是将它们放入进程内存因为这里通常是检索数据最快的地方。这种技术通常被称为记忆化。记忆化在优化递归函数时非常有用这些函数会针对多次相同的输入进行计算。我们已经在第 7 章中讨论了的斐波那契序列的递归实现。当时我们试图用 C 和 Cython 提高我们的程序的性能。现在我们将尝试通过更简单的手段实现相同的目标即在缓存的帮助下。在我们使用缓存之前让我们先回忆一下 fibonacci()函数的代码如下def fibonacci(n):“”“递归计算返回斐波那契数列的第 n 项“””if n 2:return 1else:return fibonacci(n - 1) fibonacci(n - 2)正如我们所看到的fibonacci()是一个递归函数如果输入值大于 2则调用自身两次。这使得它非常低效。运行时间复杂性是 O(2n)它的执行创建了一个非常深且庞大的调用树。对于较大的值此函数执行起来需要很长时间并且很有可能会快速超过 Python解释器的最大递归限制。简单的记忆化尝试可以在字典中存储先前运行的结果并在它们可用时取回它们。fibonacci()函数中的递归调用都包含在这一行代码中return fibonacci(n - 1) fibonacci(n - 2)我们知道 Python 是从左到右地计算指令。这意味着在这种情况下对具有较高参数值的函数的调用将在调用具有较低参数的函数之前执行。因此我们可以通过构造一个非常简单的装饰器来实现记忆化如下所示def memoize(function):“” 记忆单参数函数的调用“”call_cache {}def memoized(argument):try:return call_cache[argument]except KeyError:return call_cache.setdefault(argument,function(argument))return memoizedmemoizedef fibonacci(n):“” 递归计算返回斐波那契数列的第 n 项“”if n 2:return 1else:return fibonacci(n - 1) fibonacci(n - 2)我们使用 memoize()装饰器的闭包的字典作为缓存值的简单存储。对该数据结构中值的存储和取回的平均复杂度为 O(1)因此这大大降低了被记忆函数的总体复杂性。每个唯一的函数调用将只计算一次。在不进入数学证明的情况下我们可以从视觉上推断出在不改变 fibonacci()函数的核心的情况下我们将复杂度从非常昂贵的 O(2n)降到了线性 O(n)。我们的 memoize()装饰器的实现当然不是完美的。对于那个简单的例子它可以良好地运行但它绝对不是一个可复用的软件。如果你需要记住有多个参数的函数或者想要限制缓存的大小你需要更通用的东西。幸运的是Python 标准库提供了一个非常简单和可重用的实用程序当你需要在内存中缓存确定性函数的结果时大多数情况下可以使用它。它是来自 functools 模块的 lru_cache(maxsizetyped)装饰器。名称来自 LRU 缓存它代表最近最少使用least recently used。附加的参数可以对记忆行为进行更精细的控制。• maxsize设置高速缓存的空间上限。None 表示没有限制。• typed定义了不同类型的值是否应该被缓存为相同的结果。lru_cache 在斐波那契序列示例中的用法如下lru_cache(None)def fibonacci(n):“” 递归计算返回斐波那契数列的第 n 项“”if n 2:return 1else:return fibonacci(n - 1) fibonacci(n - 2)