每日算法 — 使用java实现快照数组：版本控制与持久化数据结构

可莉爸爸 AI算法

引言

在数据库、版本控制系统和函数式编程中，持久化数据结构（Persistent Data Structure）能够在修改后保留历史版本。快照数组（Snapshot Array）是持久化技术最直观的应用之一：支持在任意时刻创建快照，并能高效查询历史版本的值。本文用Java实现基于路径复制（Path Copying）和写时复制（Copy-on-Write）策略的快照数组。

问题定义

设计一个支持以下操作的数据结构：
– set(index, val)：设置指定索引的值
– snap()：创建快照，返回快照ID
– get(index, snap_id)：获取指定快照中某索引的值

约束分析

  • 数组长度可达 10^5
  • 调用次数可达 10^5
  • 需要 O(1) 或 O(log n) 的单次操作复杂度

核心思路：按索引维护版本链

对每个数组位置，维护一个按快照ID排序的(snap_id, value)列表。set时追加记录，get时用二分查找找到不超过目标snap_id的最新记录。

这是时空权衡的经典案例：以空间换时间，避免每次快照复制整个数组。

Java实现

import java.util.*;

/**
 * 基于版本链的快照数组
 * 每个索引位置维护一个按快照ID排序的历史值列表
 */
class SnapshotArray {
    private final int length;
    private int currentSnapId;                          // 当前快照ID
    private final List<List<int[]>> history;            // history[i] = [(snapId, value), ...]

    public SnapshotArray(int length) {
        this.length = length;
        this.currentSnapId = 0;
        this.history = new ArrayList<>(length);

        // 初始化：每个位置有一个默认值0，快照ID为0
        for (int i = 0; i < length; i++) {
            List<int[]> list = new ArrayList<>();
            list.add(new int[]{0, 0}); // [snapId, value]
            history.add(list);
        }
    }

    /**
     * 设置索引值：仅在当前快照生效
     */
    public void set(int index, int val) {
        if (index < 0 || index >= length) return;

        List<int[]> list = history.get(index);
        int[] last = list.get(list.size() - 1);

        if (last[0] == currentSnapId) {
            // 同一快照内重复设置，覆盖前值
            last[1] = val;
        } else {
            // 新快照，追加记录
            list.add(new int[]{currentSnapId, val});
        }
    }

    /**
     * 创建快照：全局快照ID自增
     */
    public int snap() {
        return currentSnapId++;
    }

    /**
     * 查询指定快照中某索引的值
     * 二分查找不超过 snap_id 的最新记录
     */
    public int get(int index, int snapId) {
        if (index < 0 || index >= length || snapId < 0 || snapId >= currentSnapId) {
            return 0;
        }

        List<int[]> list = history.get(index);

        // 二分查找：找到最后一个小于等于 snapId 的记录
        int left = 0, right = list.size() - 1;
        int result = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int[] record = list.get(mid);

            if (record[0] <= snapId) {
                result = record[1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    public int getSnapCount() {
        return currentSnapId;
    }
}

/**
 * 完全持久化数组：基于路径复制的二叉树结构
 * 每次修改只复制从根到叶子的一条路径，共享未修改节点
 */
class PersistentArray {
    private static class Node {
        int value;          // 叶节点存储值，内部节点不使用
        Node left, right;   // 左右子树

        Node(int value) {
            this.value = value;
        }

        Node(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }

    private final int size;           // 数组大小
    private final int leafStart;      // 叶子层起始索引（用于线段树索引）
    private List<Node> roots;         // 每个版本的根节点

    public PersistentArray(int[] initial) {
        this.size = initial.length;
        this.leafStart = Integer.highestOneBit(size);
        if (leafStart < size) leafStart <<= 1;

        // 构建初始线段树
        Node root = build(initial, 0, leafStart - 1);
        this.roots = new ArrayList<>();
        this.roots.add(root);
    }

    private Node build(int[] arr, int l, int r) {
        if (l == r) {
            int val = (l < arr.length) ? arr[l] : 0;
            return new Node(val);
        }
        int mid = (l + r) >>> 1;
        Node left = build(arr, l, mid);
        Node right = build(arr, mid + 1, r);
        return new Node(left, right);
    }

    /**
     * 创建新版本：修改指定索引的值
     */
    public int set(int version, int index, int val) {
        if (version < 0 || version >= roots.size() || index < 0 || index >= size) {
            return -1;
        }
        Node newRoot = update(roots.get(version), 0, leafStart - 1, index, val);
        roots.add(newRoot);
        return roots.size() - 1; // 返回新版本号
    }

    private Node update(Node node, int l, int r, int idx, int val) {
        if (l == r) {
            return new Node(val); // 叶节点：创建新节点
        }
        int mid = (l + r) >>> 1;
        Node newLeft = node.left;
        Node newRight = node.right;

        if (idx <= mid) {
            newLeft = update(node.left, l, mid, idx, val);
        } else {
            newRight = update(node.right, mid + 1, r, idx, val);
        }

        return new Node(newLeft, newRight); // 内部节点：复制路径
    }

    /**
     * 查询指定版本的值
     */
    public int get(int version, int index) {
        if (version < 0 || version >= roots.size() || index < 0 || index >= size) {
            return 0;
        }
        return query(roots.get(version), 0, leafStart - 1, index);
    }

    private int query(Node node, int l, int r, int idx) {
        if (l == r) return node.value;
        int mid = (l + r) >>> 1;
        if (idx <= mid) return query(node.left, l, mid, idx);
        else return query(node.right, mid + 1, r, idx);
    }

    public int getVersionCount() {
        return roots.size();
    }
}

/**
 * 测试入口
 */
public class SnapshotArrayDemo {
    public static void main(String[] args) {
        System.out.println("=== 快照数组测试（版本链法） ===");
        SnapshotArray snapArr = new SnapshotArray(5);

        snapArr.set(0, 5);
        snapArr.set(1, 10);
        System.out.println("初始设置: index0=5, index1=10");

        int snap0 = snapArr.snap();
        System.out.println("创建快照 " + snap0);

        snapArr.set(0, 7);
        snapArr.set(2, 3);
        System.out.println("修改后: index0=7, index2=3");

        int snap1 = snapArr.snap();
        System.out.println("创建快照 " + snap1);

        snapArr.set(1, 20);

        System.out.println("\n历史值查询：");
        System.out.println("snap0 index0 = " + snapArr.get(0, snap0)); // 5
        System.out.println("snap0 index1 = " + snapArr.get(1, snap0)); // 10
        System.out.println("snap1 index0 = " + snapArr.get(0, snap1)); // 7
        System.out.println("snap1 index2 = " + snapArr.get(2, snap1)); // 3
        System.out.println("snap0 index2 = " + snapArr.get(2, snap0)); // 0（未设置）

        System.out.println("\n=== 持久化数组测试（路径复制法） ===");
        int[] initial = {1, 2, 3, 4, 5};
        PersistentArray perArr = new PersistentArray(initial);
        System.out.println("初始数组: " + Arrays.toString(initial));

        int v1 = perArr.set(0, 0, 100); // 基于版本0修改index0
        System.out.println("版本1: 设置index0=100");

        int v2 = perArr.set(v1, 2, 300); // 基于版本1修改index2
        System.out.println("版本2: 基于版本1设置index2=300");

        System.out.println("\n跨版本查询：");
        System.out.println("版本0 index0 = " + perArr.get(0, 0));   // 1
        System.out.println("版本1 index0 = " + perArr.get(1, 0));   // 100
        System.out.println("版本2 index0 = " + perArr.get(2, 0));   // 100
        System.out.println("版本2 index2 = " + perArr.get(2, 2));   // 300
        System.out.println("版本1 index2 = " + perArr.get(1, 2));   // 3
        System.out.println("版本0 index2 = " + perArr.get(0, 2));   // 3

        System.out.println("\n总版本数: " + perArr.getVersionCount());
    }
}

两种方案对比

维度 版本链法（SnapshotArray） 路径复制法（PersistentArray）
修改复杂度 O(1) 追加 O(log n) 复制路径
查询复杂度 O(log v) 二分，v=版本数 O(log n) 线段树查询
空间增长 O(修改次数) O(log n × 版本数)
适用场景 稀疏修改、大量快照 稠密修改、需完整持久化
代码复杂度 低 中等

持久化数据结构原理

路径复制（Path Copying）

每次修改只复制从根节点到被修改叶节点路径上的节点，其余节点在新旧版本间共享。这使得新旧版本的空间差异仅为O(树高)。

写时复制（Copy-on-Write）

更进一步的优化：仅在需要修改时才复制节点。若某节点从未被修改，所有版本共享同一实例。

复杂度分析

SnapshotArray

操作 时间 空间
set O(1) 均摊 O(1) 每次修改
snap O(1) O(1)
get O(log m)，m=该位置修改次数 O(1)

PersistentArray

操作 时间 空间
set O(log n) O(log n)
get O(log n) O(1)

实际应用

  • 数据库MVCC：MySQL的InnoDB通过undo log实现多版本并发控制
  • Git版本控制：文件系统的内容寻址存储本质上是持久化数据结构
  • Redux状态管理：JavaScript应用中的不可变状态树
  • 函数式编程：Clojure、Haskell等语言的默认数据结构

总结

快照数组展示了持久化数据结构的两种典型实现思路。版本链法以简洁高效著称，适合大多数实际场景；路径复制法则是理解函数式数据结构和MVCC机制的敲门砖。掌握这些技术，能够在设计需要历史回溯的系统时游刃有余。

Tagged with: