w1100n
This site is best viewed in Google Chrome
6/28/2015 12:02

http://www.leexiang.com/cache-algorithm   缓存算法 发表于2011-10-28 原文:http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html 翻译:http://www.zavakid.com/25 引言 我们都听过 cache,当你问他们是什么是缓存的时候,他们会给你一个完美的答案,可是他们不知道缓存是怎么构建的,或者没有告诉你应该采用什么标准去选择缓存框架。在这边文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。 面试 “缓存就是存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。” 这就是 programmer one (programmer one 是一个面试者)在面试中的回答(一个月前,他向公司提交了简历,想要应聘要求在缓存,缓存框架,大规模数据操作有着丰富经验的 java 开发职位)。 programmer one 通过 hash table 实现了他自己的缓存,但是他知道的只是他的缓存和他那存储着150条记录的 hash table,这就是他认为的大规模数据(缓存 = hashtable,只需要在 hash table 查找就好了),所以,让我们来看看面试的过程吧。 面试官:你选择的缓存方案,是基于什么标准的? programmer one:呃,(想了5分钟)嗯,基于,基于,基于数据(咳嗽……) 面试官:excese me ! 能不能重复一下? programmer … Continue reading

11/27/2012 23:28

KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦! 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。 其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢?笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为? 说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢??琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。 下面贴上一位兄弟写的算法总结,很简单(建议KMP部分就不用看了,看了费脑子)。 参见:http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html 趁着做Presentation的功夫,顺便做一个总结 字符串匹配: —willamette 在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring) -: Brute Force(BF或蛮力搜索) 算法: 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢? 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢? 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 -: KMP算法 首先介绍的就是KMP 算法。 原始论文:Knuth D.E., Morris J.H., and Pratt … Continue reading

辽ICP备14012896