1146-快照数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

实现支持下列接口的「快照数组」- SnapshotArray：

  • SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。 初始时，每个元素都等于 ** 0**。
  • void set(index, val) - 会将指定索引 index 处的元素设置为 val。
  • int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
  • int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

示例：

**输入：** ["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
**输出：** [null,null,0,null,5]
**解释：** SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

提示：

  • 1 <= length <= 50000
  • 题目最多进行50000 次set，snap，和 get的调用 。
  • 0 <= index < length
  • 0 <= snap_id < 我们调用 snap() 的总次数
  • 0 <= val <= 10^9

> Problem: 1146. 快照数组

[TOC]

思路

本题出现在《二分查找·系统掌握》这一训练专栏中，但第一眼看上去似乎和二分法并没有之间关系。不过，经过一系列性能优化后，二分法的妙用就体现出来了。

本节我们先分析一个朴素但效率极低的方法，然后分析针对这一方法的性能优化。

一种朴素但效率极低的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class SnapshotArray {
    int m_snap_id;
    unordered_map<int, vector<int>> m_snap_vec;

public:
    SnapshotArray(int length) {
        m_snap_id = 0;
        m_snap_vec[m_snap_id].resize(length, 0);
    }
    
    void set(int index, int val) {
        m_snap_vec[m_snap_id][index] = val;
    }
    
    int snap() {
        m_snap_id++;
        m_snap_vec[m_snap_id] = m_snap_vec[m_snap_id - 1];
        return m_snap_id - 1;
    }
    
    int get(int index, int snap_id) {
        return m_snap_vec[snap_id][index];
    }
};

本方法通过STL对象unordered_map<int, vector<int>> m_snap_vec;实现对快照数组的访问，即set、get以及snap操作。然而，这一代码提交的结果是：
图片.png
仔细分析，各成员函数中，存储消耗最大的就是set操作，因为每次都会对一个vector对象进行拷贝，调用拷贝构造函数，这个无论是计算还是存储开销都是很大的。于是，接下来我们将分析存储开销的本质成因，以及如何优化。

性能瓶颈分析与优化思路

上述代码之所以需要在set操作中对vector对象进行拷贝，是因为用于访问快照数组的数据结构是一个从snap_id到vector的映射。这会造成大量重复的拷贝，这种拷贝可以从两个维度来分析：

【1】从行（第一维，dim=0）的角度分析，不一定每次snap操作之后，都会对当前快照的数组进行修改操作。如果snap后没有修改当前快照的数组，那get操作其实和访问之前的快照数组是等价的，这使得多次的snap操作都是无效的，完全不需要做；

【2】从列（第二维，dim=1）的角度分析，就算每一次snap操作之后，都对当前的快照数组进行修改了，也不一定每一列的元素都被修改。然而，每一次快照的拷贝操作，却是对每一列都进行拷贝了，这使得有些列的拷贝是无效的，也完全不需要做。

综上所述，我们可以得到一个更为凝练且具有深度的观点：以行id为备份快照的数据结构（即上面的 unordered_map<int, vector>）无法实现具有高效存储与计算性能的快照数组备份和访问。

解题方法

备份快照的数据结构分析

前文已经得出结论，以行id为备份快照的数据结构是无法完成本题的。这种数据结构，简单来说，就是二维数组，即使它是一个无序映射，但实际上这是一个二维数组。

那如何从一个，具有大量重复值/无效值的二维数组出发，提出适用于快照数组备份与访问的方案呢？试想一下，每一列元素，在每一次快照中都不一定被更新，那是不是可以以列为主体呢？只在需要更新时，才存储/更新列元素。

提出基于邻接表的高效存储快照

二维数组的存储方法，可以认为是一种邻接矩阵思想。反之，我们前面提到的，以列为主体的存储思路，就是一种邻接表思想。于是，本小节中我们提出了一种基于邻接表的高效存储快照。

这个数据结构是这样设计的：

1
2
3
4
5
6
7
8
9
class SnapNode {
public:
    int m_id, m_val;

    SnapNode(int id, int val)
    : m_id(id), m_val(val) { }
};

vector<vector<SnapNode>> m_snap_vec;

上面的代码中，m_snap_vec 存储的每一个元素，代表快照数组中的项。这个项为什么是一个vector对象呢？这是因为，每一次经过更新的快照信息，需要维护起来，所以用vector实现维护。根据这一数据结构，我们可以得出下面的高效存储方案：

【1】m_snap_vec 中的每一个元素，都只在 set 操作时更新，类似于懒汉模式；

【2】在快照snap 操作中，无需备份，只需要更新snap的id即可，待到set操作再维护。

基于上述思路，我们可以发现，这种方案具有两个优势：
（1）snap快照操作没有任何额外的存储开销；
（2）set更新操作中只有O(1)的存储开销。

真正做到了，只存储“当前更新/需要维护的信息”，这是理论上的最优解。

提出基于二分法的高效访问快照

在实现了高效的存储后，如何高效的在给定snap_id 的情况下，对历史快照数组进行访问就是下一步需要解决的问题。

首先，我们发现，快照数组信息在更新的过程中，snap_id 是自增的，也就是说m_snap_vec 当中的每一个元素，都是以snap_id 升序排列的。这种单调性，不难让我们想到二分查找技术。于是，可以总结出基于二分法的高效访问快照方案：

【1】根据index，以及根据snap_id 升序排列的m_snap_vec[index]对象，我们可以用二分法求出小于目标id且尽可能大的快照值。

具体的，这个二分法，是在求小于目标snap_id，但尽可能大的元素。

复杂度

  • 时间复杂度（k1表示执行get的次数，n表示m_snap_vec[index]的大小）:

    O(k_1*log_2(n))

  • 空间复杂度（k2表示执行set的次数）:

    添加空间复杂度, 示例： O(k_2)

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class SnapNode {
public:
    int m_id, m_val;

    SnapNode(int id, int val)
    : m_id(id), m_val(val) { }
};

class SnapshotArray {
    int m_snap_id;
    vector<vector<SnapNode>> m_snap_vec;

public:
    SnapshotArray(int length) {
        m_snap_id = 0;
        m_snap_vec.resize(length, {});
    }
    
    void set(int index, int val) {
        m_snap_vec[index].emplace_back(m_snap_id, val);
    }
    
    int snap() {
        m_snap_id++;
        return m_snap_id - 1;
    }
    
    int get(int index, int snap_id) {
        vector<SnapNode>& snapNodes = m_snap_vec[index];
        int l = 0, r = (int)snapNodes.size();
        if (!r) { return 0; }
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (snapNodes[mid].m_id <= snap_id) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        if (l <= 0) { return 0; }
        return snapNodes[l - 1].m_val;
    }
};

结果展示

图片.png

 Comments
On this page
1146-快照数组
  1. > Problem: 1146. 快照数组
  2. 思路
    1. 一种朴素但效率极低的方法
    2. 性能瓶颈分析与优化思路
  3. 解题方法
    1. 备份快照的数据结构分析
    2. 提出基于邻接表的高效存储快照
    3. 提出基于二分法的高效访问快照
  4. 复杂度
  5. Code
  6. 结果展示