1. imos

    Posted

    imos
Changes in title
+shared_ptrを用いた永続データ構造(配列)
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,92 @@
+## プログラム
+
+```C++
+
+#include <boost/shared_ptr.hpp>
+#include <stdio.h>
+using namespace std;
+using boost::shared_ptr;
+
+template<class T>
+struct PersistentArray {
+ static const int kShiftSize = 4;
+ int shift_, size_;
+ shared_ptr<PersistentArray> data_[1 << kShiftSize];
+ shared_ptr<T> leaf_;
+
+ PersistentArray(): size_() {}
+ PersistentArray(const long size): size_(size) {
+ if (!size) return;
+ for (shift_ = 0; (1 << (shift_ * kShiftSize)) < size; shift_++);
+ if (shift_ == 0) {
+ leaf_.reset(new T());
+ return;
+ }
+ long child_size = 1 << ((shift_ - 1) * kShiftSize);
+ for (long start = 0; start < size; start += child_size) {
+ data_[start / child_size].reset(new PersistentArray(
+ (start + child_size < size) ? child_size : (size - start)));
+ }
+ }
+
+ const T &Get(const long index) const {
+ if (shift_ == 0) {
+ assert(index == 0);
+ return *leaf_;
+ }
+ int shift = (shift_ - 1) * kShiftSize;
+ return data_[index >> shift]->Get(index & ~-(1 << shift));
+ }
+
+ void Set(const long index, const T &value) {
+ if (shift_ == 0) {
+ assert(index == 0);
+ leaf_.reset(new T(value));
+ return;
+ }
+ int shift = (shift_ - 1) * kShiftSize;
+ PersistentArray *pa = new PersistentArray();
+ *pa = *(data_[index >> shift]);
+ data_[index >> shift].reset(pa);
+ data_[index >> shift]->Set(index & ~-(1 << shift), value);
+ }
+};
+
+int main() {
+ PersistentArray<int> a(100000), b(100000), c(100000);
+ a.Set(7000, 100);
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ b.Set(7000, 200);
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ c = b;
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ b = a;
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ a.Set(7000, 300);
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ b.Set(7000, 400);
+ printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
+ for (int i = 0; i < 10000; i++) {
+ a.Set(8000, 300);
+ b.Set(8000, 400);
+ assert(a.Get(8000) == 300);
+ assert(b.Get(8000) == 400);
+ a = b;
+ assert(a.Get(8000) == 400);
+ assert(b.Get(8000) == 400);
+ }
+}
+```
+
+## 出力結果
+
+```sh
+% time ./PersistentArray
+ 100 0 0
+ 100 200 0
+ 100 200 200
+ 100 100 200
+ 300 100 200
+ 300 400 200
+./PersistentArray 0.36s user 0.17s system 55% cpu 0.966 total
+```