美文网首页
可持久化数据结构

可持久化数据结构

作者: ITgecko | 来源:发表于2019-01-07 13:18 被阅读0次
概念
  • 可持久化数据结构(Persistent data structure)是一种在发生改变时,会保存之前的版本的数据结构。这是一种不可变的(immutable
    )数据结构,对数据进行操作时,不会在原数据上进行更新改变,而是会生成另一个新的发生改变了的新数据。主要不要和数据持久化(Persistent storage
    )
    混淆,那是一种存储概念。
  • 所有数据版本(versions)都可以访问,但只有最新的版本才能修改的话,称为部分持久化数据结构(partially)。所有版本都能访问、都能修改,称为全持久化数据结构(fully)。非持久化的数据结构称为ephemeral(短暂的?)。
  • 结合immutable.js来看一个示例,map1进行操作后会新生成一个对象map2。这里immutable.js提供的Map就是可持久化数据结构,无论你如何进行操作(这些操作函数自然都是纯函数),原数据是不会发生改变的,而是会产生新的数据。
const { Map } = require("immutable");
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 50);
map1.get('b') + " vs. " + map2.get('b'); // 2 vs. 50
  • 注意虽然map2和map1是两个不同的对象,但map2并不是从map1进行深克隆就得到的,这样如果对象结构很复杂并且有多次操作的话会有很大的性能耗损。所以不同数据version,在这里也就是不同的js对象,会进行Structural Sharing(结构共享)。就比如上面的map1和map2,他们的a、c属性的值相同,所以这部分数据节点他们会共同占用。(后面会有具体的图片示例,可以清晰地了解结构共享)。
可持久化数据结构示例
  • 单向链表(singly linked list
    )应该是最简单的可持久化数据结构,每个节点拥有一个next指向下一个节点。我们来看下示例,我们首先有两个链表:xs和ys。
xs = [0, 1, 2]
ys = [3, 4, 5]
  • 以图片来看应该是这样:
![xs和ys](https://img.haomeiwen.com/i6383319/656cd8df30b91c68.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
  • 接着进行一个合并操作,xs在前、ys在后合并生成第三链表zs [0, 1, 2, 3, 4, 5]。以可持久化数据结构的做法来做的话,步骤如下:1. 复制xs得到zs 2. 然后zs的末端节点指向ys,这样就让zs和ys链表共享了ys的三个节点。
  • 过程图示如下:


    image.png
  • 这种共享节点的做法只适用于单向列表,如果是双向链表,这样做就改变了ys头部节点的pre指向,违反了数据不可变原则。
  • 接着来看另一种数据类型二叉树。首先有一个二叉树xs,结构如下:


    image.png
  • 接着在xs的f节点,添加一个left子节点e,同时生成一个新树ys。过程图示如下:


    image
  • 原来的树xs会保存下来,然后新树ys和老树xs会共享很多公用节点。

相关文章

  • 可持久化数据结构

    零、介绍 最近在刷MIT 6.851,记录下笔记。 What 可持久化数据结构就是能存储、查询数据的历史版本的数据...

  • 可持久化数据结构

    概念 可持久化数据结构(Persistent data structure)是一种在发生改变时,会保存之前的版本的...

  • 可持久化线段树

    在这里,所谓“可持久化”的数据结构并非指将数据存在非易失的存储器上,而是指保存了数据修改的历史信息。比如说对可持久...

  • Redis实现消息队列的方式

    实现方式 通过数据结构list来实现 通过pub/sub实现 通过List实现 实现机制 优点 能够实现持久化:可...

  • 基于Redis5.0.2的总结随笔

    Redis支持数据持久化,众多数据结构存储,master-slave模式数据备份等多种功能。 Redis持久化 持...

  • 「数据结构进阶」例题之可持久化数据结构

    0x40「数据结构进阶」例题 可持久化数据结构能够维护数据集的历史状态,其核心思想在于仅仅维护数据集改变的量,这样...

  • 线性基

    可持久化线性基

  • 分布式-缓存

    缓存 Memcached 不可持久化Redis 可持久化 Memcached Memcached数据访问模型添加新...

  • 可持久化线段树

    题目链接:可持久化数组 可持久化数组: 题目链接:Kth number 静态主席树: 题目链接:Dynamic R...

  • JDBC

    JDBC 持久化和持久化技术 持久化技术概念 把数据保存到可掉电式的存储设备中,持久化的实现过程大多是通过各种关系...

网友评论

      本文标题:可持久化数据结构

      本文链接:https://www.haomeiwen.com/subject/dcjzlqtx.html