lazysorted 0.1.1

如何使用它

您可以像使用sorted(...) 函数和它生成的 python 列表一样使用 LazySorted：

from lazysorted import LazySorted
from math import floor, ceil


def median(xs):
    """An expected linear time median function"""
    ls = LazySorted(xs)
    n = len(ls)
    if n == 0:
        raise ValueError("Need a non-empty iterable")
    elif n % 2 == 1:
        return ls[n//2]
    else:
        return sum(ls[(n/2-1):(n/2+1)]) / 2.0


def top_k(xs, k, key=None, reverse=False):
    """Efficiently computes the top k elements of xs using the given key, or
    the bottom k if reverse=True"""
    ls = LazySorted(xs, key=key, reverse=reverse)
    return ls[0:k]


def trimmed_mean(xs, alpha=0.05):
    """Computes the mean of the xs from the alpha to (1-alpha) quantiles
    in expected linear time. More robust than the ordinary sample mean."""
    if not 0 <= alpha < 0.5:
        raise ValueError("alpha must be in [0, 0.5)")

    ls = LazySorted(xs)
    n = len(ls)
    if n == 0:
        raise ValueError("Need a non-empty iterable")
    lower = int(floor(n * alpha))
    upper = int(ceil(n * (1 - alpha)))
    return sum(ls.between(lower, upper)) / (upper - lower)

除了上面演示的__len__和__getitem__方法，LazySorted 还支持__iter__、__contains__、 index和count方法，就像常规的 python 列表一样：

>>> import random
>>> from lazysorted import LazySorted
>>> xs = list(range(1000)) + 5 * [1234]
>>> random.shuffle(xs)
>>> ls = LazySorted(xs)
>>> for x in ls:
...     print(x)
...     if x >= 3:
...         break
0
1
2
3
>>> 1235 in ls
False
>>> ls.index(821)
821
>>> ls.count(1234)
5

虽然 LazySorted 构造函数假装等价于 sorted函数，而 LazySorted 对象假装等价于排序的 Python 列表，但它们之间有一些区别：

1. LazySorted 对象是不可变的，而 python 列表不是。

2. 使用内置sorted函数进行排序保证是稳定的，（即，保留比较相等的元素的原始顺序），而 LazySorted 排序是不稳定的。

3. LazySorted 对象有一个between(i, j)方法，它返回排序索引在range(i, j) 内的所有项目的列表，但不一定按顺序排列。例如，这对于在计算 alpha-trimmed 均值时丢弃异常值很有用。

当 python2.x 和 python3.x 之间的 API 不同时，lazysorted 实现了 python3.x 版本。所以 LazySorted 构造函数不支持在 python3.x 中被移除的cmp参数，并且 LazySorted 对象不支持在python3.x中也被移除的 __getslice__ 方法。

所有的 LazySorted 方法都有很好的文档，可以通过内置的help(...)函数访问。

我测试了lazysorted，发现它适用于CPython 2.5、2.6、2.7 和3.1、3.2 和3.3 版本。我没有测试3.0。

这个怎么运作

简而言之，LazySorted 通过懒惰地使用快速排序分区并跟踪用作枢轴的索引来工作。

`quicksort <http://en.wikipedia.org/wiki/Quicksort>`_通过选择列表中的一个元素作为“枢轴”对列表进行排序，然后将数据划分为大于或等于的部分枢轴和小于枢轴的部分。然后用快速排序对这两部分进行递归排序，

`quickselect <http://en.wikipedia.org/wiki/Quickselect>`_通过选择一个枢轴元素并对数据进行分区来查找列表中第 k 个最小的元素，就像在快速排序中一样。然后算法递归到列表的较大或较小部分，具体取决于 k 是否大于或小于枢轴元素的索引。

从这些算法中有两个关键的观察：首先，如果我们只对排序列表的一部分感兴趣，我们只需要在进行分区后递归到我们感兴趣的部分。其次，在进行了一些分区之后，列表是部分排序的，所有枢轴都按其排序顺序排列，并且两个枢轴之间的元素保证大于其左侧的枢轴并小于其右侧的枢轴。

因此，每当从 LazySorted 对象中查询某些数据时，我们首先查看枢轴以查看哪些枢轴分隔了我们想要的数据。然后我们根据需要划分子列表并递归到我们的数据所在的一侧。

还有一些实现细节可以帮助lazysorted快速运行：首先，pivot元素被选择为三个随机元素的中位数，这使得分区可能更加平衡并保证平均情况O（n log n）行为.

其次，对于足够小的列表，lazysorted 使用插入排序而不是快速排序，这在小列表上更快。众所周知，这两个技巧都可以加快快速排序的实现。

第三，由于快速找到绑定索引的枢轴很重要，因此惰性排序将枢轴存储在二叉搜索树中，以便这些查找在 O(log n) 预期时间内发生。BST 惰性排序使用的是Treap，选择它的整体预期速度，尤其是在插入和删除方面。

lazysorted 还努力从 BST 中删除不相关的枢轴；例如，如果在索引 5、26 和 42 处有三个枢轴，并且数据（介于 5 和 26 之间）和（介于 26 和 42 之间）都已排序，那么我们可以删除不相关的枢轴 26，然后说对索引 5 和 42 之间的数据进行排序。

安装

lazysorted 需要 python 头文件 (Python.h)。我相信它们随 OSX 一起提供，但如果你没有它们，它们可以安装在类似 debian 的系统上

$ sudo apt-get install python-dev

然后你可以安装lazysorted

$ sudo python setup.py install

或者，您可以从 pypi 安装lazysorted

$ easy_install --user lazysorted

或者

$ pip install lazysorted

尽管您仍然需要 python 头文件才能正确构建。

测试

我已经付出了相当多的努力来测试lazysorted实际上做了它应该做的事情。您可以自己测试（安装后）

$ python test.py

常问问题

numpy 没有中位数和百分位数函数吗？

是的，但它是通过对整个数组进行排序然后读取请求的值来实现的，而不是使用快速选择或其他 O(n) 选择算法。从 benchmark.py 中可以看出，LazySorted 在经验上更快

难道python3.4不会有一个带中位数功能的统计模块吗？

是的，我真的很兴奋！这是 PEP450。不幸的是，当前的实现是纯python，并通过对数据进行排序并挑选中间元素来计算中位数。

标准库没有 heapq 模块吗？

是的，但它缺乏该模块的全部通用性。例如，您可以使用它在 O(n log k) 时间内获取 k 个最小元素，但不能获取 k 个任意连续元素。这个模块代表了一种不同的范式：您可以像您的列表一样进行编程，并让数据结构处理细节。

惰性排序如何获得许可？

lazysorted 是 BSD 许可的。所以你可以随心所欲地使用它！有关详细信息，请参阅许可证。

我不应该使用lazysorted做什么？

1. 需要稳定排序的应用程序；快速排序分区使排序列表中相等元素的顺序未定义。

2. 需要保证快速最坏情况性能的应用。尽管可能性很小，但 LazySorted 中的许多操作都在最坏情况下运行 O(n^2) 时间。

3. 需要高安全性的应用程序。随机数生成器是不安全的，并且是从系统时间播种的，因此（野心勃勃的）攻击者可以对随机数生成器进行逆向工程，并提供 LazySorted 病态列表，使其在 O(n^2) 时间内运行。

4. 对整个列表进行排序：内置的sorted(...)的 设计和实现非常令人印象深刻。它还具有在具有部分结构的列表上运行速度比 O(n log n) 快的优势。

惰性排序如何大规模工作？

不幸的是，还好。事实证明，这主要是由于 CPython 通过传递指向它们的指针来处理 python 对象，当列表及其元素不再适合缓存时导致缓存未命中。血淋淋的细节可以在我写的一篇关于 Memory Locality 和 Python Objects的博客文章中找到。

但是，直到列表增长到大于大约 100K 的值时，这种效果才会生效，即使超过了惰性排序仍然比完全排序更快。

联络我！

如果您使用此软件并感到如此倾向，我将非常感谢您听到您使用它的目的！你可以在 Twitter @naftaliharris上联系我，或者在我的联系页面上联系我的电子邮件地址。