原地合并排序分块有序二进制文件的优化方案咨询

场景说明 #

• 练手项目，无需生产部署，了解时序数据库专用方案
• 核心场景：每次将1000个已在内存排序的可序列化样本追加到已有序的二进制文件中，需维持文件整体有序

已尝试的思路 #

• 全量读入内存排序后写回：因文件扩容问题放弃
• 文件分块排序：暂未采用
• 原地排序：当前正在使用的方案

已实现的代码 #

FileWrapper类（模拟二进制文件为随机访问数组） #

import os
import struct
from datetime import datetime
from typing import BinaryIO


class FileWrapper:
    def __init__(self, file: BinaryIO, fmt: str):
        self.file = file
        self.fmt = fmt
        self.sizeof_struct = struct.calcsize(fmt)

    def __getitem__(self, index: int) -> int:
        buffer = self.read_at(index)
        _data = struct.unpack(self.fmt, buffer)
        # timestamp is always the first value
        return _data[0]

    def __len__(self) -> int:
        self.file.seek(0, os.SEEK_END)
        return self.file.tell() // self.sizeof_struct

    def __setitem__(self, index: int, content: bytes) -> None:
        self.file.seek(index * self.sizeof_struct)
        self.file.write(content)

    ## helper method
    def read_at(self, index: int) -> bytes:
        self.file.seek(index * self.sizeof_struct)
        buffer = self.file.read(self.sizeof_struct)
        return buffer

    def swap(self, i: int, j: int) -> None:
        if i == j:
            return

        buffer_i = self.read_at(i)
        buffer_j = self.read_at(j)

        self[i] = buffer_j
        self[j] = buffer_i

自定义原地merge算法 #

def merge(arr, start, mid, end):
    start2 = end
    last_swap = 0

    swaps = 0
    lookups = 0

    while start2 > mid:
        lookups += 1

        if arr[start] <= arr[start2]:
            start += 1
        else:
            swaps += 1
            arr[start], arr[start2] = arr[start2], arr[start]
            if last_swap == 0:
                last_swap = start
            start += 1

        if start >= start2:
            start = last_swap
            start2 -= 1

    n = len(arr)
    print(f"lookups: {lookups}; swaps: {swaps} for n={n}")

当前遇到的问题 #

当前自定义merge算法的IO查找（lookups）与交换（swaps）次数过高：测试101000条数据时，lookups达95742262次，swaps达9716次，担忧硬盘损坏或性能极差。曾尝试基数排序、插入排序、归并排序、快速排序，均存在IO开销过大问题。

此外构思了一种非原地方案：遍历原文件与新样本，将合适数据写入新文件，但违反原地要求，且担心大文件（如4GB）时的块拷贝开销。

咨询问题 #

如何优化原地合并排序的IO开销？或者是否有更适合的低IO排序方案？

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