时间戳

首页 > 解决方案 > 如何在不复制的情况下传递python列表切片？

python - 如何在不复制的情况下传递python列表切片？

问题描述

我写了一个快速选择算法如下：

def partition(arr):
    pvt = 0
    for i in range(len(arr) - 1):
        if arr[i] < arr[-1]:
            arr[i], arr[pvt] = arr[pvt], arr[i] # mv smaller elements before pvt
            pvt += 1
    arr[-1], arr[pvt] = arr[pvt], arr[-1]
    return pvt

def quickselect(k, arr):
    p = partition(arr)
    while k != p:
        p = partition(arr[:p]) if k < p else partition(arr[p:])
    return arr[k]

我打算做的是在具有 O(n) 复杂度的 arr 中找到第 k 个元素。但是当我完成编码时，我发现 arr[:p] 实际上传递了一个副本而不是原始列表的切片，这不会使递归分区正常工作。据我所知，熊猫系列切片实际上做了我想要的。如果我将 arr 作为 pd.Series 传递，它似乎工作正常。但是有没有更原生的方式来传递 python 列表 arr[:p] 的原始切片？

标签： pythonlist

解决方案

arr[:p] 是副本，所以不复制就无法通过。

正如您已经发现的那样，您可以使用执行“视图切片”的不同类型 - <code>memoryview, np.array,pd.Series等。

或者您可以将整个列表和切片信息一起传递，如下所示：

def partition(arr, start, stop):
    pvt = 0
    for i in range(start, stop - 1):
        if arr[i] < arr[stop-1]:
            arr[i], arr[pvt] = arr[pvt], arr[i] # mv smaller elements before pvt
            pvt += 1
    arr[stop-1], arr[pvt] = arr[pvt], arr[stop-1]
    return pvt

def quickselect(k, arr, start=None, stop=None):
    if start is None: start = 0
    if stop is None: stop = len(arr)
    p = partition(arr, start, stop)
    while k != p:
        p = partition(arr, start, p) if k < p else partition(arr, p, stop)
    return arr[k]

或者您可以编写一个简单的包装器来携带列表、开始和停止值，并通过适当的转发来实现collections.abc.Sequence（或MutableSequence）。这是更多的前期工作，但它可能会使您编写的其他代码更具可读性。

您可以在此处找到可变和不可变切片视图的简单版本。它没有像我希望的那样经过彻底测试，但它似乎适用于您的quickselect. （当然，线性工作而不是二次工作的成本可能会被为每个切片构建包装器对象的常数乘数所淹没，直到您获得合适大小的列表……）

推荐阅读