Python列表多位置高效插入及图像置乱算法优化问询

一、高效插入Dummy值的实现（基于NumPy） #

列表的insert操作每次都会移动后续元素，插入次数多时时间复杂度高达O(k*N)（k为插入次数）。用NumPy可以通过批量构造数组的方式一次性完成插入，将时间复杂度降到O(N + k)，效率提升显著：

import numpy as np

def insert_dummies_numpy(original_array, indices, dummy_val):
    # 转换为NumPy数组以利用批量操作
    original_np = np.array(original_array)
    final_len = len(original_array) + len(indices)
    # 初始化全为dummy值的结果数组
    result = np.full(final_len, dummy_val, dtype=original_np.dtype)
    
    # 生成掩码：标记原数组元素应放置的位置（排除dummy值的索引）
    mask = np.ones(final_len, dtype=bool)
    mask[indices] = False
    # 将原数组元素批量填入对应位置
    result[mask] = original_np
    
    return result.tolist()  # 如需转回列表则调用tolist，否则直接返回NumPy数组

效率优势 #

NumPy底层基于C实现批量内存操作，避免了Python循环中多次移动元素的开销，即使处理百万级元素的数组也能保持线性时间复杂度。

二、置乱算法的优化思路 #

1. 去掉Dummy值：修改split_and_flip支持任意长度的可逆操作 #

原算法因奇数长度无法拆分还原而受限，可调整递归逻辑，让奇数长度数组也能可逆处理：当数组长度为奇数时，单独保留中间元素，对前后两个偶数长度的子数组递归处理，最终拼接时保留中间元素的位置：

def split_and_flip_improved(array: list) -> list:
    size = len(array)
    if size <= 1:
        return array.copy()
    
    half = size // 2
    # 拆分前半段、中间元素（奇数时）、后半段
    if size % 2 == 1:
        h1 = array[:half]
        mid = [array[half]]
        h2 = array[half+1:]
    else:
        h1 = array[:half]
        mid = []
        h2 = array[half:]
    
    # 递归处理前后子数组
    h1 = split_and_flip_improved(h1)
    h2 = split_and_flip_improved(h2)
    
    # 翻转前后段后拼接，中间元素保持原位置
    return h1[::-1] + mid + h2[::-1]

对应的还原函数只需反向执行该逻辑：拆分翻转后的数组，分别还原前后子数组，再拼接即可。这样无需补dummy值，直接支持任意长度数组的可逆置乱。

2. 预计算置换索引，实现O(N)级置乱/还原 #

递归处理数组会频繁生成新列表，大尺寸图像的RGB数组处理时内存开销和时间成本较高。可以提前计算每个元素的最终位置索引，通过索引映射完成置乱/还原：

核心步骤：

• 预计算置换数组perm，perm[i]表示原数组第i个元素在置乱后的位置
• 置乱：shuffled_array = original_array[perm]（NumPy下直接索引，O(N)）
• 还原：计算逆置换数组inv_perm（inv_perm[perm[i]] = i），执行restored_array = shuffled_array[inv_perm]

示例代码：

def compute_permutation(n: int) -> list:
    perm = list(range(n))
    
    def helper(start, end):
        if end - start <= 1:
            return
        length = end - start
        half = length // 2
        mid = start + half
        # 翻转前后段并放回原位置
        perm[start:mid] = perm[start:mid][::-1]
        perm[mid:end] = perm[mid:end][::-1]
        # 递归处理前后段
        helper(start, mid)
        helper(mid, end)
    
    helper(0, n)
    return perm

# 置乱示例
original = np.array([1,2,3,4,5,6,7,8])
perm = compute_permutation(len(original))
shuffled = original[perm]

# 还原示例
inv_perm = np.argsort(perm)  # 快速计算逆置换
restored = shuffled[inv_perm]

这种方法的优势是置换索引只需计算一次，后续置乱和还原都是纯数组索引操作，速度极快，适合处理高清图像。

3. 迭代替代递归，避免栈溢出 #

原递归函数处理超大数组（如长度2^20）时，可能触发Python递归深度限制。可将递归逻辑改为迭代版本，用栈存储待处理的数组区间：

def split_and_flip_iterative(array: list) -> list:
    arr = array.copy()
    stack = [(0, len(arr))]
    
    while stack:
        start, end = stack.pop()
        length = end - start
        if length <= 1:
            continue
        half = length // 2
        mid = start + half
        # 翻转前后段
        arr[start:mid] = arr[start:mid][::-1]
        arr[mid:end] = arr[mid:end][::-1]
        # 将前后段压入栈继续处理
        stack.append((mid, end))
        stack.append((start, mid))
    
    return arr

迭代版本性能与递归相当，但不会出现栈溢出问题，稳定性更强。

内容的提问来源于stack exchange，提问作者UraniumX92