lazysorted 0.1.1

如何使用

您可以像使用 排序（…） 函数及其生成的python列表：

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)

除了演示的方法 上面，lazysorted还支持 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

尽管懒散的构造函数假装等同于 sorted 函数，而lazysorted对象假装等价 对于排序后的python列表，它们之间有一些不同：

1. 懒散排序的对象是不可变的，而python列表是不可变的。
2. 使用内置的sorted函数进行排序 稳定，（即，保持比较元素的原始顺序 相等），而懒散排序不稳定。
3. lazysorted对象有一个 between（i，j） 方法，该方法返回 排序索引在 范围（i，j） 内的所有项的列表， 但不一定按顺序。这很有用，例如 计算α修正平均值时丢弃异常值。
< > >

当python2.x和python3.x之间的api不同时，将进行懒散排序 实现python3.x版本。所以懒散的构造函数没有 支持在python3.x中删除的 cmp 参数，以及 lazysorted对象不支持 也在python3.x中删除。

所有懒散排序的方法都有很好的文档，可以 通过内置的帮助（…）功能访问。

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