数据结构之后缀数组
后缀数组是一种解决字符串问题的有力工具。相比于后缀树,它更易于实现且占用内存更少。在实际应用中,后缀数组经常用于解决字符串有关的复杂问题。
{关注大规模数据处理,包括Hadoop,YARN,Spark,Flink,Presto等}
后缀数组是一种解决字符串问题的有力工具。相比于后缀树,它更易于实现且占用内存更少。在实际应用中,后缀数组经常用于解决字符串有关的复杂问题。
AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。本文介绍了AVL树的设计思想和基本操作。
同splay tree一样,treap也是一个平衡二叉树,不过Treap会记录一个额外的数据,即优先级。Treap在以关键码构成二叉搜索树的同时,还按优先级来满足堆的性质。因而,Treap=tree+heap。这里需要注意的是,Treap并不是二叉堆,二叉堆必须是完全二叉树,而Treap可以并不一定是。
本文介绍了二叉查找树的一种改进数据结构–伸展树(Splay Tree)。它的主要特点是不会保证树一直是平衡的,但各种操作的平摊时间复杂度是O(log n),因而,从平摊复杂度上看,二叉查找树也是一种平衡二叉树。另外,相比于其他树状数据结构(如红黑树,AVL树等),伸展树的空间要求与编程复杂度要小得多。
本文介绍一种新的数据结构:块状链表,它将数组和链表的优点结合来,各种操作的时间复杂度均为O(sqrt(n))。
1. 概述 位图(bitmap)是一种非常常用的结构,在索引,数据压缩等方面有广泛应用。… 继续阅读 数据结构之位图
1TB排序通常用于衡量分布式数据处理框架的数据处理能力。Terasort是Hadoop中的的一个排序作业,在2008年,Hadoop在1TB排序基准评估中赢得第一名,耗时209秒。那么Terasort在Hadoop中是怎样实现的呢?本文主要从算法设计角度分析Terasort作业。
随着MapReduce的流行,其开源实现Hadoop也变得越来越受推崇。在Hadoop系统中,有一个组件非常重要,那就是调度器,它的作用是将系统中空闲的资源按一定策略分配给作业。在Hadoop中,调度器是一个可插拔的模块,用户可以根据自己的实际应用要求设计调度器。本文介绍了Hadoop中常见的三种调度器。