12

早些时候，我试图回答一个问题，我想尽可能高效地迭代列表切片。

for x in lst[idx1:]:

不理想，因为它创建了一个副本（通常，这是O(n)）。我的下一个想法是使用itertools.islice. 但是，如果您查看文档，它似乎islice会调用next，直到找到它正在寻找的索引，此时它将开始产生值。这也是O(n)。islice如果传递给的对象是 alist或 a ，这里似乎有一个可用的优化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???
4

4 回答 4

4

我认为值得一提的是 NumPy 切片是非复制的（它们在底层数组上创建一个视图）。因此，如果您可以将 NumPy 数组用于您的数据，那将解决问题。最重要的是，您可以通过矢量化获得额外的性能改进。

于 2012-11-29T15:24:27.447 回答
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
于 2012-11-29T16:01:37.520 回答
1

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

于 2012-11-29T16:06:33.053 回答
0

islice是itertools模块中的一个函数，因此它iterator通常与 s 一起工作（并且绝对应该工作），而不仅仅是lists。因此，您无法在itertools源代码中找到您的优化，因为它应该适用于任何给定的迭代器。

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

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

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

于 2012-11-29T15:55:12.797 回答