itertools.islice实现--高效地切片列表

Question

之前，我试图回答一个问题，想要尽可能高效地迭代一个列表切片。

for x in lst[idx1:]:

由于它创建了一个副本（一般来说，这是 O(n)），因此并不理想。我的下一个想法是使用 itertools.islice。但是，如果你查看文档，会发现 islice 会调用 next 直到找到它要查找的索引位置，然后开始生成值。这也是 O(n)。似乎有一种优化可以用于传递给 islice 的对象是 list 或 tuple 的情况——似乎可以直接（在 C 中）迭代“切片”，而不必实际制作副本。我很好奇这个优化是否已经在 源代码 中实现，但我没有找到任何信息。我对 C 和 Python 源代码树并不十分熟悉，所以完全有可能我错过了。

我的问题是：

是否有一种方法可以在一个被优化的 C 实现中迭代列表“切片”而不制作列表“切片”的副本并且不浪费一堆不需要的元素？

我很清楚我可以为此编写自己的生成器（非常简单，没有考虑到许多参数应该是可选的等等）:

def myslice(obj,start,stop,stride):
    for i in xrange(start,stop,stride):
        yield obj[i]

但是这肯定无法打败经过优化的C实现。

---

如果你想知道为什么我需要这个，而不只是直接循环遍历一个切片，请考虑以下区别：

takewhile(lambda x: x == 5, lst[idx:])  #copy's the tail of the list unnecessarily

与

takewhile(lambda x: x == 5, islice(lst,idx,None)) #inspects the head of the list unnecessarily 

最后：

takewhile(lambda x: x == 5, magic_slice(lst,idx,None)) #How to create magic_slice???

- mgilson

---

迭代本身是O(n)。迭代加切片仍然是O(n)。迭代加islice也是O(n)。现在只需做最干净的事情，当速度成为问题时再担心它，并在以后或永远不担心大O的问题。 - Duncan

@Duncan -- 但迭代不一定要是O(N)的。假设我只想从切片中获取前M个元素？（M不一定是静态的--它可以基于某些“谓词”函数）。我也同意过早优化可能会使代码更难阅读。我主要只是好奇。 - mgilson

请注意——svn.python.org不再更新。源代码现在位于hg.python.org/cpython。（我已经向python.org网站管理员发送了邮件，建议他在svn.python的顶部放置一个通知，但没有任何效果。） - Fred Foo

@larsmans -- 谢谢你帮我修好了那个问题。我只是谷歌了“itertools源代码”，然后找到了第一个结果。也许我们该请Guido来修复这个问题，他在Google工作，对吧？;-) - mgilson

Answer 1

值得一提的是，NumPy切片是非拷贝的（它们创建一个对底层数组的视图）。因此，如果您可以使用NumPy数组来处理数据，那么这将解决问题。此外，通过向量化，您还可以获得额外的性能提升。

- NPE

---

如果你的数据可以使用Numpy数组，那么这是一个相当大的限制——你不能高效地使用.append方法添加元素到Numpy数组中。然而，这仍然是一个非常好的观点。（+1）。 - mgilson

确实，这是一个很大的限制。NumPy并不适用于所有问题，但当它适用时，它确实能够非常出色地工作。 - NPE

那个有什么优势呢，相比于同样不复制的 itertools.islice？ - Kirk Strauser

@larsmans 哇 - 看来你和 OP 是对的。islice 确实从第一个对象开始，并调用 obj->tp_iternext() 直到它到达正确的索引。我有点震惊，它不会做像 if isinstance(obj, list): start = obj[index]; current = index 这样的事情，以在对象中间进行 O(1) 跳过。 - Kirk Strauser

@KirkStrauser：我也是这样，但是itertools的所有内容都旨在支持一种流数据的惰性处理方式。当然，您可以自由提交补丁 :) - Fred Foo

@larsmans 我已经在那个问题领域玩过一段时间了，但是我会把C语言的编程工作留给那些不介意这种疯狂层面的人。 :-) - Kirk Strauser

Answer 2

有没有一种方法可以在不复制列表切片的情况下迭代列表切片，而且又不会在优化的C实现中浪费大量不需要的元素？

是的，如果您编写了该C实现，则有。Cython使此特别容易。

cdef class ListSlice(object):
    cdef object seq
    cdef Py_ssize_t start, end

    def __init__(self, seq, Py_ssize_t start, Py_ssize_t end):
        self.seq = seq
        self.start = start
        self.end = end

    def __iter__(self):
        return self

    def __next__(self):
        if self.start == self.end:
            raise StopIteration()
        r = self.seq[self.start]
        self.start += 1
        return r

- Fred Foo

---

咕哝着 - 我总是想着总有一天我会教自己Cython（甚至读过一两次教程），但我总是拖延真正使用它，因为我的Fortran技能比我的C技能更好，f2py让我的生活变得如此轻松。我想这是一个例子，说明f2py仅仅是不够用了，也许我应该下定决心好好复习一下我的C/Cython。 - mgilson

@mgilson，我知道你发表这篇文章已经有很长时间了，但是这个怎么工作呢？ - sos

Answer 3

如果您使用 PyPy（因为您关心性能），它们会优化字符串切片以避免复制：http://doc.pypy.org/en/latest/interpreter-optimizations.html

- Gurgeh

---

我经常想知道是否有任何实现利用字符串的不可变性。无论如何，这仍然不能适用于任意序列。 - mgilson

Answer 4

islice 是 itertools 模块中的一个函数，因此它可以与一般的迭代器一起使用（并且绝对应该这样做），而不仅仅是与列表一起使用。因此，在 itertools 的源代码中找不到您的优化，因为它应该适用于任何给定的迭代器。

在您的情况下，正确的方法是：

def magic_slice(lst, start, end=None):
    for pos in xrange(start, (end or len(lst))):
        yield lst[pos]

takewhile 会逐个调用您的生成器，并 yield 新值 - 与通用列表遍历和 xrange 迭代相同的“速度”。因此，在这种实现中的开销是最小的。如果您需要更多 - 您可以在 C 级别上重写此类函数，但我不认为这样做有很多优势。

- Alexey Kachayev

---

它应该适用于任何迭代器/可迭代对象的事实并不排除特殊序列的实现。 - Fred Foo

虽然我同意itertools应该继续适用于任何可迭代对象，但源代码中有一些特殊情况需要针对列表和元组进行处理，因为当你使用这些数据类型时，可以更有效地完成操作。 （例如，请参见list.extend的代码） - mgilson