木西笔记

个人博客

算法探秘系列之数据结构篇——树（2）

B+树

概诉概诉 B+ 树的定义关于B树的阶数和度数已经在上一篇算法探秘系列之数据结构篇——树（1）除此之外B+树还有以下的要求。 1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。 2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中...

Posted by Jason Lee on 2019-06-26

算法数据结构树

算法探秘系列之概率随机算法(1)

布隆过滤器

什么是布隆过滤器本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。实现原理 HashMap 的问题讲述布隆过滤器的原理...

Posted by Jason Lee on 2019-06-25

算法 Redis 概率随机算法

算法探秘系列之数据结构篇——树（1）

B树

注意：首先需要说明的一点是：B-树就是B树，没有所谓的B减树引言我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ，众所周知ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只...

Posted by Jason Lee on 2019-06-24

算法数据结构树

Redis系列之分布式锁实现

基于Redis的单点和基于集群的Redlock的分析

概述在大多数的情况下，我们需要对一个共享资源进行写操作，在分布式的环境下，对于资源的写操作的互斥性就显得尤为重要。由于生产环境对redis有很多依赖，所以最近在分布式锁的实现上进行了一些调研。对于锁的安全性，一直是分布式领域不可逃避的话题，一个分布式锁的实现在网上所以下，就会发现，这些文章的思路大体相近，给出的实现算法也看似合乎逻辑，但当我们着手去实现它们的时候，却发现如果你越是仔细推敲...

Posted by Jason Lee on 2019-05-30

分布式 Redis

算法探秘系列之动态规划（2）

背包问题

背包问题有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。问题分类 01背包问题如果N个物品每个物品只能使用一次，则成为01背包问题完全背包问题如果NN个物品每个物品可以使用无限次，则为完全背包问题问题的解法暴力搜索解法（递归解法）动态规划解法优化后的动态规划（滚动数组，自下而上） 01背包问题 ...

Posted by Jason Lee on 2019-05-30

算法动态规划

算法探秘系列之动态规划（1）

动态规划介绍

概述态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划一般可分为线性动规区域动规树形动规背包动规四类。举例：线性动规：拦截导弹(最大递减数列)，合唱队形，挖地雷，建学校，剑客决斗等；区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵等；树形动规...

Posted by Jason Lee on 2019-05-26

算法动态规划

Redis系列之数据结构篇(3)

跳表和压缩表

本文转自 redis 的设计与实现跳表 – 跳表的结构跳跃表（skiplist）是一种随机化的数据，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。以下是个典型的跳跃表例子（图片来自维基百科）：从图中可以看到，跳跃表主要由以下部分构成：表头（hea...

Posted by Jason Lee on 2019-05-26

分布式 Redis

大数据算法之空间亚线性算法（二）

Misra-Gries 算法（数据流中最频繁的的数字）

概诉水库抽样算法样算法虽然是抽样算法却不是近似算法。本节分享一下有限内存利用近似解求数据流中最频繁的元素。 Misra-Gries算法是频繁项挖掘中一个著名的算法。频繁项就是那些在数据流中出现频率最高的数据项。频繁项挖掘，这个看似简单的任务却是很多复杂算法的基础，同时也有着广泛的应用。对于频繁项挖掘而言，一个简单的想法是，为所有的数据项分配计数器，当一个数据项到达，我们即增加相应计数器...

Posted by Jason Lee on 2019-05-24

大数据空间亚线性算法大数据算法篇

大数据算法之空间亚线性算法(一)

水库抽样算法

问题描述输入：一组数据，大小未知输出：这组数据的K个均匀抽取要求：仅扫描一次总体要求：从N个元素中随机的抽取k个元素，其中N无法确定，保证每个元素抽到的概率相同问题难点首先明确什么叫均匀抽样，就是每个数据被等概率抽取呗。即当样本总体为n 时候，每个样本被抽取的概率为1/n,如果要抽取k个元素，那么每个样本被抽到的概率为k/n。但是我们实现不知道总体的数量n。如果就只有n=K个...

Posted by Jason Lee on 2019-05-23

大数据空间亚线性算法大数据算法篇

Redis系列之数据结构篇(4)

对象简介

本文转自 redis 的设计与实现简介我们陆续介绍了 Redis 用到的所有主要数据结构，比如简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合，等等。 Redis 并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前...

Posted by Jason Lee on 2019-05-19

分布式 Redis