您现在的位置：首页
--> 算法
记得有个大家记歌词的节目，很火爆，通过旋律快速找到歌曲，旋律搜索有多少用处呢？我们常常会遭遇到这样的尴尬：在大街小巷邂逅一段熟悉的旋律，无奈又听不清歌词。遗憾也许这辈子就这样失之交臂了。不必懊恼，Shazam 是一款能够识别音乐讯号的应用。相信不少朋友对它并不陌生。它在 iPhone 和 Andriod 手机里出现的频率很高，诺基亚的某些手机甚至预装了这样一款软件。它的基本原理就是通过采集十几秒的声音样本，通过网络将音乐...
JSON全称为JavaScript Object Notation，原本作为JavaScript语言中用于表示对象结构的文本形式。不过目前JSON成功地脱离了JavaScript语言，它已经成为一种运用十分广泛的数据交换格式。从表面看来，目前用于某个对象与JSON格式之间相互转化的解决方案已经有了许多种，例如在.NET平台上，我们可以使用ASP.NET AJAX中引入的JavaScriptSerializer，WCF中引入的DataContractJsonSerializer，亦或是Json.NET。但是，最近我忽然发现这些...
在之前的《浅谈》一文中，我提到《Automated Padding Oracle Attacks with PadBuster》一文对理解Padding Oracle Attack非常有帮助，并打算将其翻译出来。现在我便来实现承诺了。《Automated》一文其实是在介绍PadBuster这个自动攻击工具，不过其中也通过实例加配图详细介绍了Padding Oracle Attack的原理――这也是我会翻译的部分。这篇文章写的非常通俗易懂，您只需要了解一点点关于加密的基础概念即可，不需要对加密算法或其证...
上图的拍摄者一定是个桌游达人，五种正多面体骰子的全家福竟然都能被他搞出来。我们自然会想到一个有趣的问题：还有别的形状的骰子吗？或者更“数学”一些的说法，在凸多面体的每个面上都标一个数字，能用来当骰子的就只有这五种吗？看上去似乎是这样：只有正多面体才能保证这颗骰子是“公平”的。呃・・・・・・是吗？ 事实上，对于骰子来说， 正多面体不是...
经常有公司问这样的面试题. 这个问题非常基础，很多面试的人，都知道String对象是不可变的，在说原因的时候没说清，其实看看String源码就知道了 在new String的时候，String 中的3个成员变量value，count，offset都是final的，当然String类也是final的，所以一旦初始化后不能修改的。 StringBuffer，与StringBuilder都实现了相同的接口，而且都继承相同的父类，不同的是，StringBuffer的大部分方法都是同步的，所以是线程安全，Str...
我们正在开发的类数据库系统有一个内存模块，出现了一个疑似”内存泄露”问题，现象如下：内存模块的内存释放以后没有归还操作系统，比如内存模块占用的内存为10GB，释放内存以后，通过TOP命令或者/proc/pid/status查看占用的内存有时仍然为10G，有时为5G，有时为3G, etc，内存释放的行为不确定。 首先说一下内存模块的内存管理机制。我们的内存管理很简单，使用全局的定长内存池，每一个内存块为64KB，如果申请的内存小...
常用的数据结构包括：数组，队列，堆栈，链表，树（平衡二叉树，B树，Trie树，堆），哈希表，图，后缀数组，等等。其中，堆，图结构，Trie树及后缀数组解决特定问题，其它数据结构解决通用的查找，更新，删除操作。 查找，更新和删除操作一般是O(1)，O(logN)或者O(N)，通用的数据结果大致可分为如下三种： 1, 极端型；某些操作的算法复杂度为O(1)，另外一些算法复杂度为O(N)，比如有序链表查找复杂度为O(N)，更新和删除为O(1)； 2,...
需求来自于，我希望可以对 lua 虚拟机中的内容做持久化，却又不希望 stop the world 。这需要利用 os 的功能，对内存做一个快照。简单的 fork 就可以达到快照的要求，但是 fork 会快照整个进程的地址空间，这不是我想要的。这两天和几位同学讨论了各种方案，比如 memcpy ，比如 fork+exec 传递 shm_open 的 fd ， fork 后 munmap 不用的区域等等。最后我认为如下方案相对更满意一些。我并没有实现出来， 写 blog 只是做个记录。
本想先找本算法和数据结构的书参考一下，但转念一想：不如考考自己的总结和逻辑表达能力。 loop、iterate、traversal和recursion这几个词是计算机技术书中经常会出现的几个词汇。众所周知，这几个词分别翻译为：循环、迭代、遍历和递归。乍一看，这几个词好像都与重复（repeat）有关，但有的又好像不完全是重复的意思。那么这几个词到底各是什么含义，有什么区别和联系呢？下面就试着解释一下。 循环（loop），指的是在满足条件的...
最近有一个server在重启的时候总要花费5分钟左右来加载配置文件，导致外网服务不可用，今天和几个同事一起研究了一下，总算找到了问题所在.
最近在做网站测试时，遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为，不由想到了一个有趣的问题：为了输入一定数量的字符，最少需要按多少个键？ 大家最常用的策略或许是， 先输一些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到一个新的数量级，如此反复。注意到进入全选状态（并且复制后），第一次粘贴将...
这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就...
HUFFMAN主要有两个问题，一是需要扫描两遍输入数据，二是树状结构编解码慢。对于第一个问题，基于统计信息的熵编码都很难解决这个问题，可以设计成自适应的，根据统计数据不停地改变调整码树，这会比较麻烦。对于第二个问题，这跟硬件有关系，二叉树的编码、解码都是O(1)的，复杂度上不能更优了，但是计算机硬件的特性，会使得树状结构遍历过程中CACHE MISS比较严重，如果码树比较小的话，可以都放在一级CACHE，性能会好很多，...
对原题的误读，有时竟会产生一些更有意思的问题。果壳问答上，网友 qxx 提问说：一个房间里面有很多人，我想让房间里面任意两个人的生日相同的概率是 50% 的话那房间里面应该最少有多少人？ 当然，几乎可以肯定，提问人原本是想说“至少两个人”的，而问题的答案就是 23 ――生日悖论带来的惊人的答案。不过，如果把“至少两个人”误说成“任意两个人”，题目意思就完全变了，并...
最多能在平面上找出多少个点，使得它们两两之间的距离都是整数？当然，我们忽略最平凡的解――所有点都在一条直线上。 三个点的解显然是存在的，只需要构造一个边长为 1 的等边三角形即可。事实上，满足任意两数之和大于第三数的一组整数都可以成为一个三角形的三条边。寻找含有四个点的解也并不困难，一个长为 4 宽为 3 的矩形就能满足要求。不过，我们还有更小一些的解。最小的...
从北大打车到四惠，我一定会选择走四环。虽然从北京城中间直穿过去看上去很诱人，但考虑到北京道路几乎总是正南正北的方向，不会真有人认为这样能抄近路吧。在城市中，我们估算两点之间的距离时，往往不会直接去测量两点之间的直线距离，而会去考虑它们相距多少个街区。在理想模型中，假设每条道路都是水平或者竖直的，那么只要你朝着目标走（不故意绕远路），不管你怎样走，花费的路程都是一样的。
有一根不均匀的绳子，烧完正好需要 1 个小时。如何用这根绳子测出半个小时的时间呢？答案很巧妙：把这根绳子的两头同时点燃，绳子烧完时正好就过了半个小时。更妙的是下面这个加强版：如何用两根这样的绳子来计时 45 分钟？答案是，把其中一根绳子的两头都点燃，同时点燃另一根绳子的其中一头；待到前一根绳子烧完之后，再把第二根绳子的另一头也点燃，于是便能测出 30 + 15 = 45 分钟了。
近3天十大热文
-
[493] Go Reflect 性能 -
[31] 正态分布的前世今生(一)
-
[19] Linux Used内存到底哪里去了？
-
[17] 基于HTTP缓存轻松实现客户端应用的离线支持
-
[16] 公钥私钥加密解密数字证书数字签名详解
-
[16] osx平台上lol英雄联盟launcher启
-
[15] 在JavaScript中什么时候使用==是正
-
[14] Linux内存中的Cache真的能被回收么？
-
[14] Joomla反序列化漏洞的查漏补缺
-
[13] rsync同步的艺术
赞助商广告
