Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Táto stránka sa týka školského roku 2016/17. V školskom roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://people.ksp.sk/~kuko/ds


Perzistentné dátové štruktúry

Z VPDS
Prejsť na: navigácia, hľadanie

Sources

Persistent data structures

  • keep old versions of the data structure
  • partial persistence: update only current version, query any old version, linearly ordered versions
  • full persistence: update any version, versions form a tree
  • confluent persistence: combine versions together, versions form a DAG
  • fully functional: never modify nodes, only create new
  • backtracking: query and update only current version, revert to an older version
  • retroactive: insert updates to the past, delete past updates, query at any past time relative to current set of updates

Pointer machine

  • model of computation, without arrays
  • constant-size nodes, holding data (numbers, characters, etc) and pointers to other nodes
  • pointers can be assigned: address of a newly created node, copy of another pointer, null
  • no pointer arithmetic
  • root node with all global variables, all variable names in the program of the form root.current.left.x

General transformation with node copying

  • Algorithm see slides

First, let us prove that the algorithm for the update will terminate

  • assume that outdegree of each node is at most 2p-1
  • update on one node may trigger other updates etc, in the worst case the each newest node might be rebuilt (replaced by another)
  • However, no node is replaced by a new node twice within one recursive update
  • Assume by contradiction that such a node exists and consider the first node that is rebuilt the second time. Between its first and second rebuild it must have acquired 2p mods, but these mods must have been caused by nodes to which this nodes points to being rebuilt. There are at most 2p-1 such nodes and none of them was rebuilt more than once because we consider the first node which is rebuilt twice.

Notes for the amortized analysis:

  • as real cost, count the number of recursive calls (all other computation proportional to that)
  • want to prove that the amortized cost of one update is 2
    • if there is space in the node for another mod, real cost is 1 (only one call to modify), change of potential is 1, so amortized cost is 2
    • if the node is full, real cost is 1, change of potential is -2p plus amortized cost of all subsequent recursive calls. By induction, each of these calls has amortized cost 2, so overall amortized cost is 1
    • what is the induction on? The depth in the tree of recursive calls (leaves are the base cases where node not full). We have already proved that this node is finite.