数组Snapshot

霍建华 发表于 2019-3-14 06:02
对着每个index 做一个treemap即可

get o1

那每个index需要copy所有snapshot的值吗？比如
snap 0 {1,2,3}
set(1, 20).  //index 1's value becomes to 20
snap 1 {1,20,3}
set(2, 30). //index 2's value becomes to 30
snap 2 {1,20,30}
好像我遇到的不太一样，他和我说的是每次set都会生成一个新的snapshot，所以是上面这种变化。

get(2) //return 30 from current snapshot
get(2,1) //return 3 from snap 1
如果只对index存(snap, value)，那么2->(0, 3), (2, 30)，(1, 3)这个在生成snap 1的时候需不需要copy呢？需要的话空间上和二维数组一样，时间上也是要把其他所有的copy一份。不copy的话get(2,1)怎么得到3呢？

用Python 写了两种版本，第一种存仅更新改变的Version减缓内存，Get 用二分法查找．第二种做了点改变，每1024个 Frame把整个数组复制一遍，查找先用哈希再用二分快一些，牺牲了点内存，多久复制整个数组可以随状况自订改变

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-3-18 08:01):
忘了用插入代码． ． ．

第二种

您好！
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这是关系数据库的snapshot Isolation的simple
naive实现呀！

简单的写了下数组的。 基本思想是：

• 维护一个version num，TakeSnapshot时加1
• 数组的每个元素是一个{since_version, value} 的vector （保存的其实是the value since a version的信息）
• Get，O(log(那个元素不同版本的个数))，二分查找到想要的since_version即可，我这里用的是upper_bound的结果减1
• Set，O(1)。看看那个位置最新的version，如果和当前version相等，直接覆盖；否则append
  

1. #include <algorithm>
   
2. #include <cassert>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. template <typename ValueType>
   
8. class VersionedArray {
   
9. public:
   
10.   using Version = size_t;
    
11. 
    
12.   // default_val is the default value when an element doesn't exist.
    
13.   explicit VersionedArray(size_t size, ValueType default_val)
    
14.       : v_(size), default_val_(default_val) {}
    
15. 
    
16.   void Set(size_t pos, ValueType val) {
    
17.     assert(pos < v_.size());
    
18. 
    
19.     if (v_[pos].empty() || v_[pos].back().first != ver_) {
    
20.       v_[pos].push_back({ver_, val});
    
21.     } else {
    
22.       v_[pos].back().second = val;
    
23.     }
    
24.   }
    
25. 
    
26.   int Get(size_t pos, Version ver) {
    
27.     assert(pos < v_.size());
    
28.     if (v_[pos].empty()) {
    
29.       return default_val_;
    
30.     }
    
31. 
    
32.     // Find a version > ver, then the previous version is what we want.
    
33.     auto it = upper_bound(
    
34.         v_[pos].begin(), v_[pos].end(), make_pair(ver, -1),
    
35.         [](const pair<Version, int>& v1, const pair<Version, int>& v2) {
    
36.           return v1.first < v2.first;
    
37.         });
    
38.     if (it == v_[pos].begin()) {
    
39.       return default_val_;
    
40.     }
    
41.     return prev(it)->second;
    
42.   }
    
43. 
    
44.   void TakeSnapshot() { ver_++; }
    
45. 
    
46.   Version LatestVersion() const { return ver_; }
    
47. 
    
48. private:
    
49.   vector<vector<pair<Version, ValueType>>> v_;
    
50.   Version ver_ = 0;
    
51.   const ValueType default_val_;  // Default value when an element doesn't exist.
    
52. };
    
53. 
    
54. int main(int, char*[]) {
    
55.   constexpr int NOT_FOUND = numeric_limits<int>::min();
    
56.   VersionedArray<int> va(10, NOT_FOUND);
    
57.   va.Set(0, 0);
    
58.   assert(va.Get(0, va.LatestVersion()) == 0);
    
59.   assert(va.Get(1, va.LatestVersion()) == NOT_FOUND);
    
60. 
    
61.   va.TakeSnapshot();  // Now latest version is 1
    
62. 
    
63.   va.Set(0, 10);
    
64.   va.Set(1, 11);
    
65.   va.Set(1, 111);
    
66. 
    
67.   assert(va.Get(0, 0) == 0);
    
68.   assert(va.Get(0, 1) == 10);
    
69.   assert(va.Get(1, 0) == NOT_FOUND);
    
70.   assert(va.Get(1, 1) == 111);
    
71. 
    
72.   va.Set(1, 1111);
    
73. 
    
74.   va.TakeSnapshot();  // Now latest version is 2
    
75.   va.TakeSnapshot();  // Now latest version is 3
    
76.   va.TakeSnapshot();  // Now latest version is 4
    
77.   assert(va.Get(0, 0) == 0);
    
78.   assert(va.Get(0, 1) == 10);
    
79.   assert(va.Get(0, 2) == 10);
    
80.   assert(va.Get(0, 3) == 10);
    
81.   assert(va.Get(0, 4) == 10);
    
82. 
    
83.   assert(va.Get(1, 0) == NOT_FOUND);
    
84.   assert(va.Get(1, 1) == 1111);
    
85.   assert(va.Get(1, 2) == 1111);
    
86.   assert(va.Get(1, 3) == 1111);
    
87.   assert(va.Get(1, 4) == 1111);
    
88. 
    
89.   return 0;
    
90. }
    

复制代码

补充内容 (2019-4-18 01:34):
Followup的map，和数组相比，基本类似

补充内容 (2019-4-18 01:35):
刚才补充了一句话，原来能高亮的代码排版全乱了。麻烦版主看到了帮忙修改一下代码的格式。

1. class Snapshot:
   
2.     def __init__(self, length):
   
3.         if length<=0:
   
4.             raise Exception("Invalid length %s"%length)
   
5.         self.version = 1
   
6.         self.dictionary = [{} for i in range(length)]
   
7. 
   
8. 
   
9.     def setValue(self, index, value):
   
10.         if 0<=index < len(self.dictionary):
    
11.         
    
12.             self.dictionary[index][self.version]=value
    
13.         else:
    
14.             raise Exception ("Invalid index %s"%index)
    
15. 
    
16. 
    
17.    
    
18.     def getValue(self, index, version):
    
19.         if version not in self.dictionary[index]:
    
20.             raise Exception ("Version %s not exist"%version)
    
21. 
    
22.         return self.dictionary[index][version]
    
23. 
    
24.    
    
25.     def snap(self):
    
26.         self.version = self.version+1
    
27. 
    
28. sp = Snapshot(3)
    
29. sp.setValue(1,1)
    
30. 
    
31. sp.setValue(0,0)
    
32. sp.setValue(2,2)
    
33. sp.snap()
    
34. sp.setValue(1,0)
    
35. 
    
36. assert sp.getValue(1, 1) ==  1
    
37. assert sp.getValue(1, 2) == 0
    
38. 
    
39. 
    
40. 
    
41. 
    

复制代码

1. '''
   
2. 如果题意中是要求如果输入了不存在的版本号返回最进的版本，那么就就要binary search key
   
3. '''
   
4. class Snapshot:
   
5.     def __init__(self):
   
6.         self.version = 1
   
7.         self.keys = collections.defaultdict(list)
   
8.         self.values = collections.defaultdict(list)
   
9. 
   
10. 
    
11.     def setValue(self, index, value):
    
12.         if  self.keys[index]  and self.version == self.keys[index][-1]:
    
13.             self.values[index][-1]=value
    
14.         else:
    
15.             self.keys[index].append(self.version)
    
16.             self.values[index].append(value)
    
17. 
    
18. 
    
19.    
    
20.     def getValue(self, index, version):
    
21.         versions = self.keys[index]
    
22.         versionIndex = bisect.bisect_right(versions, version)
    
23.         if versionIndex:
    
24.             
    
25.             return self.values[index][versionIndex-1]
    
26.         else:
    
27.             return ""
    
28. 
    
29.    
    
30.     def snap(self):
    
31.         self.version = self.version+1
    
32. 
    
33. 
    
34. sp = Snapshot()
    
35. #version 1
    
36. sp.setValue(1,1)
    
37. sp.setValue(1,2)
    
38. sp.setValue(0,0)
    
39. sp.setValue(2,2)
    
40. sp.snap() #version 2
    
41. sp.snap() #version 3
    
42. sp.snap() #version 4
    
43. sp.setValue(1,0)
    
44. sp.setValue(2, 20)
    
45. 
    
46. 
    
47. assert sp.getValue(1, 1) ==  2
    
48. assert sp.getValue(1, 2) == 2
    
49. assert sp.getValue(2, 7) == 20
    
50. assert sp.getValue(1, 4) == 0
    
51. assert sp.getValue(1, 3) == 2

复制代码