Changeset 14673

Timestamp:

02/14/17 15:29:14 (8 years ago)

Author:

epitzer

Message:

#2727 improve AMT's size with history (use same rollback semantic) and add comparison value with traditional arrays

File:

• branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs (modified) (1 diff)

branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs

@@ -244 +244 @@
       var nodes = new Dictionary<Node, UInt16>();
       AddNodeSizeRecursively(root, nodes);
-      var size = nodes.Sum(kvp => (long) kvp.Value);
-      if (oldRoots != null) {
-        foreach (var node in oldRoots) {
-          AddNodeSizeRecursively(node.Item1, nodes);
-        }
-      }
-      var sizeWithHistory = nodes.Sum(kvp => (long)kvp.Value);
-      Console.WriteLine("size = {0}, size with history = {1}", size, sizeWithHistory);
-      return sizeWithHistory;
+      var prev = Rollback();
+      while (prev != null) {
+        AddNodeSizeRecursively(prev.root, nodes);
+        prev = prev.Rollback();
+      }
+      return nodes.Sum(kvp => (long) kvp.Value);
+    }
+
+    public long TheoreticalSizeOfArraysWithHistory() {
+      long total = Count;
+      var prev = Rollback();
+      while (prev != null) {
+        total += prev.Count;
+        prev = prev.Rollback();
+      }
+      return total;
     }