如何仅用链表与数组实现O(n)复杂度的文件行公平随机拷贝

核心采用Fisher-Yates（费舍尔-耶茨）洗牌算法实现，该算法可保证所有排列出现概率完全相等，整体时间复杂度为O(n)，仅需用到数组结构即可完成实现，配合密码学安全随机数生成器可避免随机规律被猜测。

实现步骤 #

• 第一步：逐行读取输入文件的所有内容，存入数组中，每一行对应数组的一个元素
• 第二步：执行Fisher-Yates洗牌操作：从数组最后一个索引开始向前遍历，对索引i，生成一个范围在[0, i]的安全随机整数r，交换数组中索引i和r位置的元素
• 第三步：将洗牌完成后的数组逐行写入目标输出文件即可

参考实现代码（Python） #

import secrets

def shuffle_file(input_path: str, output_path: str) -> None:
    # 读取所有行到数组
    with open(input_path, 'r', encoding='utf-8') as in_f:
        lines = in_f.readlines()
    
    # Fisher-Yates 公平洗牌
    for i in range(len(lines) - 1, 0, -1):
        # 用密码学安全的随机数生成器，避免随机序列可被预测
        random_idx = secrets.randbelow(i + 1)
        lines[i], lines[random_idx] = lines[random_idx], lines[i]
    
    # 写入目标文件
    with open(output_path, 'w', encoding='utf-8') as out_f:
        out_f.writelines(lines)

方案合规性说明 #

• 时间复杂度：文件读取、洗牌、写入三个阶段的时间复杂度均为O(n)，整体满足O(n)要求
• 数据结构：仅使用数组存储行数据，若需要适配内存不足的超大文件场景可额外引入链表做分块处理，全程不涉及其他数据结构
• 随机性：采用密码学安全随机数生成器输出随机数，不存在可被猜测的固定规律，也没有轮询等固定分配逻辑
• 公平性：Fisher-Yates算法从数学上保证所有行的任意排列出现概率完全相等，无任何偏向性

内存不足场景的适配方案 #

如果需要处理的文件大小超过可用内存上限，可采用分块+链表的方案实现：

1. 逐行读取输入文件，按内存可容纳的最大大小分割为多个临时块，每个块内部先做Fisher-Yates洗牌后写入本地临时文件，将每个临时块的读取路径、当前偏移、剩余行数等信息封装为链表节点，所有节点组成一个链表
2. 每次生成一个0到当前所有块剩余总行数-1的随机数，遍历链表找到包含该随机数对应位置的块，读取该块的下一行写入目标文件，更新该块的剩余行数，若块内所有行已读取完成则从链表中删除该节点
3. 重复上述操作直到链表为空，最后清理所有临时文件即可
   该方案整体时间复杂度仍为O(n)，符合所有要求。

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