次优二叉搜索树

缘起

【1】中我们介绍了最优二叉搜索树. 并给出了算导中的算法实现. 但是它最大的弊病就在于令人尴尬的建树的O(n^3)的复杂度上. 所以【2】的9.1节提出了近似解决方案——次优二叉搜索树. 也就是确定根节点的算法并不像【1】中那样严格的根据dp公式得到最佳分割点，而是只要两边的权重之差达到最小即可(具体公式可以参见【2】，已经写的很清晰了).

大量实践证明，次优比最优在查找性能上的损失不会超过3%, 一般都在 %1和%2左右，但是次优建树的算法复杂度是O(nlogn)的，远比最优的O(n^3)来的可行性高. 所以实际中人们使用的都是次优查找树. 顺便说一句，次优和最优都是静态查找树.

顺便说一下，相比 SecondOptimal-BST 这种名词，我更喜欢 NearlyOptimal-BST.

本文就来实现这一算法.

Read More

最优二叉搜索树

缘起

具体的缘起就是设计一款英文翻译到中文的程序软件, 希望每次输入英文搜索次数的期望是最小的. 以前介绍过的AVL、红黑树等结构未必能给出最优解是因为他们假定的是每个节点被搜的概率是相等的. 但实际上，英文单词与英文单词之间出现的概率是不一样的. 所以最优解未必长成之前的平衡二叉树的样子.

我们定义最优二叉搜索树为

1
2
1. 是一棵bst
2. 使得搜索的期望次数（不论是搜到或者没搜到）最小, 搜索期望次数的定义详见【1】的公式15.11

详细背景和算法参见【1】的15.5小节. 关于最优二叉搜索树（Optimal-BST, 下简称opt-bst）的算法，算导上已经将的异常清晰了. 不想拷贝经典.

Read More

跳表(SkipList)

缘起

数组和链表各有所长——前者便于静态查找， 但动态维护成本较高； 后者便于增量式的动态维护， 但只能支持顺序查找。为结合二者的优点， 同时弥补其不足，才逐步引入了二叉树、平衡二叉搜索树，其查找、插入和删除操作均可在O(logn)时间内完成。尽管如此，这些结构的相关算法往往较为复杂，代码实现和调试的难度较大，其正
确性、鲁棒性和可维护性也很难保证。设计并引入跳表（skip list） 结构的初衷，正是在于试图找到另外一种简便直观的方式，来完成这一任务。具体地，跳转表是一种高效的词典结构，它的定义与实现完全基于（多层）有序链表结构，其查询和维护操作在平均的意义下均仅需O(logn)时间。

跳表的性能上与红黑树(例如c++ STL中的set与map都是用红黑树实现的)、AVL（绝对平衡的结构，红黑树是稍差一些的平衡）等等匹敌,但是缺点是跳表比较吃内存(原因也很直观——红黑树、AVL中是没有重复的元素的(有人对平衡类型的动态查找树只进行惰性删除，但是主流实现不是),但是跳表有很多重复元素)

但因为其简单性、易维护性，所以很多开源软件，如Redis 和 LevelDB 都有用到它.

Read More

字符串匹配算法之kmp

缘起

大家都使用过word吧? 如果要在整篇文档中搜索一个单词，比如就叫”word”,你会怎么搜索呢? 肯定是匹配咯~ 怎么匹配呢? 一种朴（bao）素（li）的算法就是指针指向整篇文档的第一个字符，然后和”word”进行匹配，至多最坏需要匹配4次，所以如果文档的字符个数是N，而搜索的单词的字符数是M的话，暴力算法（下简称BF算法，brute force）的复杂度将是O(NM)。 N,M比较小还好，如果一旦比较大的话，则这是程序不能忍受的. 其实你仔细想想，从整篇文档的第一个字符开始比较发现不匹配之后，其实匹配的过程中已经留下信息了，但是暴力算法没有有效利用或者维护起这种信息来导致复杂度过高. 因此KMP算法诞生——三位大神发明的. 以其首字母命名此算法为KMP。

Read More

事务、锁 小结

缘起

天下大乱久矣！！！百姓望廓清轮宇久矣！！！

遂花了25块钱买了【1】的mysql小册仔细阅读（非安利，这真是一本好书，至少让只会连接mysql进行CRUD的java程序员对mysql的理解上一个台阶，不夸张的~）, 阅读完毕，感觉已经到了廓清轮宇的时候了. 于是今天来写这篇文章, 来彻底明晰一下mysql（只以mysql为例，博主在电商，用的就是mysql，本文所有的讨论都是基于mysql5.7.23）的事务和锁中的相关概念，原先其实看过很多文章，但是比较凌乱，而且不知道这些概念是否有交叉，也不知道所谓的事务和锁在底层到底是个什么东西. 所以一直迷迷糊糊的~ 个人非常、极度讨厌这种不在掌控中的东西！！！

而且这里我吐槽一下——极度厌恶以及鄙视网上那种为了应付面试写的什么”sql索引优化军规36条”这种没营养的文章. 妈的，说难听点不就是死记硬背么~ 不明白底层原理， 有卵用? 闲话不多说，进入正题.

Read More