专栏首页Apache IoTDB重新认识数据结构:从空间占用开始

重新认识数据结构:从空间占用开始

数据结构与算法是基础知识了,一般涉及数据结构的增删改查,深入一点的可以估计增删改查的时间复杂度和空间复杂度。本文介绍另一种衡量数据结构的方式:空间占用。这种分类让我对数据结构有了一个全新的认识。

假如需要存储数据的信息论(香农之子)最低空间占用为Z个bit(其实就是原始数据的空间占用),那么对这些数据的一种表示(数据结构)可以根据其空间占用分成三类:空间占用逐渐增大。

(1)Implicit(隐式):占用 Z+O(1) bits,如 Z+3 bits

(2)Succinct(简洁):占用 Z+o(Z) bits,如 Z + lgZ bits

(3)Compact(紧凑):占用 O(Z) bits,如 2Z bits,1.1Z bits

这里可能会造成疑惑,Succinct 和 Compact 有啥区别,个人认为附加的空间只要和 Z 不是线性关系就是 Succinct,是线性关系就是 Compact。

空间占用 Implicit < Succinct < Compact。看一个比较形象的图:空间占用就是这些数据的围墙,实际建筑物占空间并不大,重点是围墙内的面积。这张图就很 Succinct 了。

下边通过例子来具体介绍:

Implicit 数据结构

普通数组:除了原始数据,只多存了一个数组长度。(和链表区分开,链表还有数据之间的指针)

以null结尾的字符串:除了原始字符数据,只多了一个 null 字符。

这些数据结构基本都是一些非常简单的数据结构,虽然空间占用很高效,但是如果不做特殊处理,在其上的操作复杂度都不低,查找都是O(n)的。当然也可以先将数据排序再存到数组里,也属于 implicit 数据结构。

为什么叫 implicit 呢,我觉得应该是原始数据中隐藏着结构,因为并没有用指针之类的明显表示数据之间的关系。

Succinct 数据结构

这种数据结构的定义是 Jacobson 1989 年左右提出来的。

链表就不是 Succinct 数据结构,在链表中每个数据都带一个指针,假如数据有 n 个,为了区分这n个数据,指针的长度最少为 lg(n)个 bit。比如要区分 4 个数据至少需要 2 个bits。这样假如每个数据占 x 个bit,Z=xn,指针占用 nlg(n)个,总占用 ( 1+x/lg(n) ) Z 个bits。Z 的一次项系数大于1。

Succinct的起源是用 Level-Ordered Unary Degree Sequence(LOUDS)编码将一棵普通的树形结构编码成 Succinct tree。

看下面这棵树(来自《Space-efficient Static Trees and Graphs》),其每个节点的编码是这样来的:如果其有 n 个子节点,那么他的编码就是 n 个 1 加一个 0。

接下来用一另一棵树介绍这些节点编码如何组织成一个数组:(为什么换个图呢,因为不是我画的,来自《SuRF: Practical Range ery Filtering with Fast Succinct Tries》)。我们回过头来看 LOUDS 的名字,他是分层的,有序的。这些编码按层次从左到右依次排列,组成了 LOUDS 编码,如下图:

这样,就将一棵树编码成了一个数组。省掉了指针,但是这样怎么查找子节点或父节点呢?

在这个数组上提出了两个基本操作:

看不下去后边的等号公式可以不看,直接听我讲:

rank_q(x) 返回数组位置 x 之前(包括x)值为 q 的数据个数。比如位置 5 之前有几个 1 为 rank_1(5)。

select_q(x) 返回第 x 个 q 的数据位置。比如第 5 个 1 的位置为 select_1(5)。

那么,这两个操作如何实现节点的查找呢?首先一个节点是有多个 bit 编码的,由 0 分割。一般一个节点用它的起始位置 p 表示。节点的下标从 0 开始。

(1)第 i 个节点的位置:select_0(i)+1,即第 i 个0的位置 +1。

(2)起始位置为 p 的节点的 下标为 k 的子节点的位置:select_0(rank_1(p+k)) +1

(3)起始位置为 p 的节点的父亲节点的位置:select_1(rank_0(p))

看,他们搭配出来可以在数组里完成树的功能,这就是索引之美。

Compact 数据结构

我们常用的数据结构实现方式大部分都是 Compact 数据结构。需要用指针来记录数据的相对位置和关系。

如链表,用指针实现的树。

总结

树、堆等只是逻辑数据结构,是实现方式决定了其是 Succinct 还是 compact。而这个实现方式的区分一般就看他是用数组实现的还是用指针实现的,比如,树状数组就属于 Succinct,用链表实现的二叉树就是Compact。Implicit 数据结构基本都是基础数据结构,很难玩出花样,而Succinct 数据结构未来可能会有更多应用。

参考:

https://en.wikipedia.org/wiki/Succinct_data_structure

《SuRF: Practical Range ery Filtering with Fast Succinct Tries》

《Space-efficient Static Trees and Graphs》

本文分享自微信公众号 - IoTDB漫游指南(Apache-IoTDB),作者:铁头乔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 把 SSD 说个明白

    上篇文章介绍了机械硬盘和固态硬盘:硬盘的各种概念。在文章里有说到固态硬盘只有一种访问方式,不管是顺序读写还是随机读写,SSD都没有寻址时间。但是有朋友来讨论固态...

    Apache IoTDB
  • 硬盘的各种概念

    不得不说,关于磁盘的各种概念网上说法很多,看了半天快把我看晕了,最后总结了总结,基于我的认知基本理顺了。

    Apache IoTDB
  • java 字节流入门(文件流)

    在编程语言的教材中,文件流大多是放在最后一章介绍的,而且大学不怎么考流,所以没有重视过。在开始学习 java 流时,发现大多博客上来就放一大家子类图,每次看到都...

    Apache IoTDB
  • 【基础编程】侃侃数据结构与算法-扯扯概念

    ? 为啥扯淡,因为我们开发人员很少用到它,目前流行的android开发有数据结构么?没有,至少你在用api的时候基本上是看不见的。c++有在STL基本容器中s...

    程序员互动联盟
  • 数据结构?

    数据结构可以实现一种或多种抽象数据类型,而抽象数据类型(Abstract Data Type [ADT])就是一种数学的抽象,一些操作的集合【插入、删除等操作】...

    半纸渊
  • 数据结构学习秘籍

    网络上太多的同学吐槽被虐,如滔滔江水连绵不绝,数据结构太难了!真的很难吗?其实数据结构只是讲了三种:线性结构、树、图。到底难在哪里呢?通过调查了解大概有四个原因...

    rainchxy
  • 入门篇 | 学渣是如何自学数据结构的?

    -------------------------------------------

    小小詹同学
  • 入门篇|学渣是如何自学数据结构的?

    -------------------------------------------

    黄泽杰
  • 数据结构学习

    很久没有更新公众号了,为了后面的学习,最近一直在补基础,用了一个比较好的方法,用c把常见的几个数据结构都实现了一遍,两个方面都能同时得到锻炼。

    信安本原
  • 为何说数据结构是程序员最重要的基本功?

    之前我们在自己的用户群中做过一次调研,主要是1-5年编程经验的工程师,有应届生、有小厂的程序员,有大厂的程序员,也有经验不错的技术经理。

    区块链大本营

扫码关注云+社区

领取腾讯云代金券