Menu Sidebar
Menu

Algorithm

TimSort

TimSort其实就是插入排序和合并排序的综合体. 首先切分数组, 然后利用插入排序对小数组的优势, 先sort小数组, 然后再merge几个小数组. code我是直接抄github的

ComboSort

Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.

Bitonic Sort双调排序

这个排序的名字很好玩, Bi是双的意思 tonic是音乐的元音. 所以叫双调, 就是两个调性(递增 递减). 具体的操作可以看 https://en.wikipedia.org/wiki/Bitonic_sorter 我主要讲讲下面这个例子: [5,2,1,7,3,8,6,4], len = 8 第一步先临近的两个元素比大小, 比如[5,2]变成[2,5], [1,7]变成[7,1], 数组变为 [2,5], [7,1], [3,8], [6,4] 此时序列为[2,5,7,1,3,8,6,4] 这样就是递增, 递减, 递增 递减的两对儿双调.然后就是合并两个双调. 合并的方法是用的wiki中的batcher理论. 显示四个为一组合并, 然后是两个为一组合并. 四个为一组: [2,1,7,5] ([2,5]和[7,1]合并的结果) [6,8,3,4] ([3,8]和[6,4]合并的结果) 此时的序列为[2,1,7,5,6,8,3,4] 此时, 并不是双调序列, 还需要进行两个为一组的合并. [2,1,7,5] 变成 [1,2,5,7] 递增 [6,8,3,4] 变成 [8,6,4,3] 递减, 此时序列为[1,2,5,7,8,6,4,3] 最后要进行八个一组的合并, 然后是四个一组, 然后是两个一组. 八个一组后: [1,2,4,3,8,6,5,7] 四个一组后: [1,2,4,3,5,6,8,7] 两个一组后: […]

BeadSort重力排序

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求. 上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子. 然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好. 上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落 代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数. 最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了

Understanding LSTM Networks

链接: https://colah.github.io/posts/2015-08-Understanding-LSTMs/ LSTM比其他Neural Networks有更好的上下文能力. RNN的上下文能力, 来自于loop. 需要处理上下文中word之间的gap. 比如猜测” I grew up in France… I speak fluent French. “最后一个字French, 需要直到France, 但是France和French之间有gap. 这种gap如果一直存在, 影响随着loop会越来越明显. 虽然理论上不会有这种问题, 但是实际上是经常存在的. LSTM就是用来解决上面这个问题的. LSTM最大的优势是, 他不只是一个单层的网络结构, 而是四层. LSTM使用了gate的概念, gate决定是否让一个information传递到下一个神经元. LSTM通常有3个gates. 使用forget gate layer (sigmoid) 来遗忘不重要的数据, 0表示完全遗忘, 1表示完全传递. 使用input gate layer(sigmoid+tanh)来决定记住那些数据, sigmoid用来判断那个需要update, tanh来决定update多少. 最后通过一层的filter layer(tanh)来决定h 一个变种是添加了一个peephole(探孔)来让gate有”全局观”, 数学上就是把上次的参数加入这次的gate的计算中. 另一个变种是让forget gate和input gate之间产生联系. 还有一种变种结合了forget和input, 变成了update gate, 这种方法叫GRU.

读 Computing the nearest common ancestor

原文地址: http://codinggorilla.com/?p=91&cpage=1 这篇文章介绍了两种算法, Alstrup-Gavoille-Kaplan-Rauhe(AGKR) 和 Schieber-Vishkin. 他们是用来解决 Nearest Common Ancestor (NCA) 或者 Lowest common ancestor (LCA) 问题的. 首先, 文章给出了NCA/LCA问题的定义, 即在树状结构下, 求解任意两个node的最近公用node. 如上图中, node e和 node m 的公用node是a. 这个问题是 Alfred Aho教授提出的, 就是那个ac自动机匹配的那个a.. 文章给出了一个最简单的算法 这个算法是利用两个node的parent信息, 通过两个stack存储node的路径, 进而找到公用node. 这种解法的时间和空间复杂度是o(n). 最坏情况就是刚才的满树下的最左和最右. Schieber-Vishkin算法是由Baruch Schieber 和 Uzi Vishkin 通过简化 Harel and Tarjan的算法得来的. 它的复杂度包含了两个部分, o(n)的preprocessing(预处理)阶段和o(1)的query(解答)阶段. 在预处理阶段, Schieber-Vishkin算法需要重新编码整颗树: 首先假设一棵树是满树时, 对一棵树做inorder traverse. 并且加一个数字计数器, 便有下图: […]

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

August 2020
M T W T F S S
 12
3456789
10111213141516
17181920212223
24252627282930
31