您现在的位置：首页
--> 算法
天文学是第一个被测量误差困扰的学科，从古代至十八世纪天文学一直是应用数学最发达的领域， 到十八世纪，天文学的发展积累了大量的天文学数据需要分析计算，应该如何来处理数据中的观测误差成为一个很棘手的问题。 我们在数据处理中经常使用平均的常识性法则，千百来来的数据使用经验说明算术平均能够消除误差，提高精度。 平均有如此的魅力，道理何在，之前没有人做过理论上的证明。 算术平均的合理性问题在天文学的数据分析工作中被提出来讨论：测量中的随机误差服应该服从怎样的概率分布？ 算术平均的优良性和误差的分布有怎样的密切联系？
第二个故事的主角是欧拉(Euler), 拉普拉斯(Lapalace),勒让德Legendre) 和高斯(Gauss),故事发生的时间是十八世纪中到十九世纪初。十七、十八世纪是科学发展的黄金年代，微积分的发展和牛顿万有引力定律的建立，直接的推动了天文学和测地学的迅猛发展。当时的大科学家们都在考虑许多天文学上的问题。
其实一直就想做一个类似PageRank的东西来鉴别一个微博博主的“能量”。经常看到有些微博博主有50-100万左右的粉丝，但发出来的微博几乎无人问津（零转发、零评论），于是就动手做了这个。 首先，明确一点，这个玩意只是一个玩具，优点和缺点都很明显。别指望JavaScript能获取和判断太多信息。但仅作为玩具来看，也能看到一些有趣的现象。所以如果是想获得专业和客观的“微博粉丝互动频度”、“微博僵尸粉丝数量”数据，不要盲目参考。举个简单例子，方舟子（只是我做数据分析的客观结果，舟子老师的粉丝不要怪我）的微博后面很多人是在骂他，而这一部分数据JavaScript是无法辨别的，因此都计算到方舟子这个微博的Karma里了。 同样，由于采用了一个简单的平均数的算法，因此突然爆红的微博也会导致Karma过高。
• 代码执行的效率
在《性能调优攻略》里，我说过，要调优性需要找到程序中的Hotspot，也就是被调用最多的地方，这种地方，只要你能优化一点点，你的性能就会有质的提高。在这里我给大家举三个关于代码执行效率的例子（它们都来自于网上）
我在大学学习数理统计的时候，学习的过程都是先学习了正态分布，然后才学习中心极限定理。而学习到正态分布的时候，直接就描述了其概率密度的数学形式，虽然数学上很漂亮，但是当时很困惑数学家们是如何凭空就找到这个分布的。然而读了陈希孺的《数理统计学简史》之后，才发现正态分布的密度形式首次发现是在棣莫弗-拉普拉斯的中心极限定理中。数学家研究数学问题的进程很少是按照我们数学课本的安排顺序推进的，现代的数学课本都是按照数学内在的逻辑进行组织编排的，虽然逻辑结构上严谨优美，却把数学问题研究的历史痕迹抹得一干二净，我们难以在数学课本上看到数学家对数学问题是如何研究推进的。DNA 双螺旋结构的发现者之一 Waston 在他的名著《DNA 双螺旋》序言中说：“科学的发现很少会像门外汉所想象的一样，按照直接了当合乎逻辑的方式进行的。”
首先为什么要做这样的判断呢？ 当你要strcpy活着strcmp或者hash一个字符串的时候，传统的方法是每个byte进行比较。以strcpy为例，当一个字符串比较长，我们用32（或者64位）的字长进行copy的话，一次拷贝会拷贝4个byte，能节省很多时间（忽略内存对齐等情况）。 但是，使用32位的字长进行拷贝一个难点就是判断字符串的结尾，因为字符串长度不一定是4的整数倍，每次从内存中取4个byte，我们需要判断这4个byte中是否有某个byte是0，从而判断字符串是否结束。
用 Python 的着眼点主要是 VLOOKUP 公式太慢了，所以关键是要找到一种更高效的算法或数据结构定位数据。VLOOKUP 要求对列进行排序，内部应该是对列内数据进行二分查找，算法上不好再优化了，那就只好更换一种数据结构。搜索了一下，VBA 提供了 Scripting.Dictionary 这一词典结构，而且有文章说内部是哈希表实现，那就正是我要的东西了。
一个简单的程序，统计文本文档中的单词和汉字数，逆序排列（出现频率高的排在最前面
英语等以空白字符作为分隔符的语言，分词不是问题。中文分词，需要处理的细节太多。单就“真歧义”这一问题（简言之，如果没有上下文，连活生生的人也无法确定如何断句的歧义句）的处理方法而言，前辈们就已写出洋洋洒洒许多文字。不过这属于进阶题目。我想先实现一个最简单的分词程序。
人们总觉得这个搜索领域很多秘密，门槛如此之高，如此神秘。其实不是那么回事。基本的原理、流程理解了。就可以做到心中不慌。先了解机制，细节和具体才是难点，不要被难在开始！下面就结合实际经验积累，给出参考信息。不针对任何排序模型，只描述粗略内容。具体场景具体怎么高，私下交流。 提示：排序规则务必公开，否则会有非常多的诟病、诟骂。不要以为你的排序是机密， 包括自己的开发成员都含糊其辞的，这样只会增加排序的神秘性、恶意去钻空子等。 完全公开排序细则，明确排序导向什么、打击什么，只是一些得分因子、权重需要慎重， 是否全面公开，而排序算法是完全可以公开的。即使不公开，一帮外面的专业seo 很快就找到规律的，那时候就非常被动了。
Worker模式 想解决的问题 异步执行一些任务，有返回或无返回结果 使用动机 有些时候想执行一些异步任务，如异步网络通信、daemon任务，但又不想去管理这任务的生命周。这个时候可以使用Worker模式，它会帮您管理与执行任务，并能非常方便地获取结果 结构 很多人可能为觉得这与executor很像，但executor是多线程的，它的作用更像是一个规划中心。而Worker则只是个搬运工，它自己本身只有一个线程的。每个worker有自己的任务处理逻辑，为了实现这个目的，有两种方式 1. 建立一个抽象的AbstractWorker，不同逻辑的worker对其进行不同的实现； 2. 对worker新增一个TaskProcessor不同的任务传入不同的processor即可。 第二种方式worker的角色可以很方便地改变，而且可以随时更换processor，可以理解成可”刷机”的worker
单维度聚合分析，主要解决类似以下场景的问题 (1)同一个用户搜索输入关键词 (2)某个时间段内搜索词排行榜 (3)某些关键词联合出现情况 (4)IP\\位置 维度下的关键词聚合情况 (5)其他任何参与搜索的单维度搜索请求统计 (6)平均命中率、hits=0、查询平均响应时间 ...... (7)新词发现(8)输入提示 目录 1 单维度聚合分析 1.1 为什么选择搜索引擎 1.2 单维度聚合分析意义 1.3 陷阱 2 单维度聚合关键问题 2.1 维度的选择 2.2 格式化 3 单维度聚合实现样例 单维度聚合分析 为什么选择搜索引擎 单维度聚合分析应该是各种分析统计中最为简单、直接。 对于主动搜索、被动搜索一体的应用场景，有登录和无登陆等统一兼顾。并且提供接口服务，按需返回维度信息，并且可以复用。 无疑采取搜索引擎，依赖搜索引擎的facet统计功能，最为直接、快捷、有效、低沉本。
在做一些web相关的工作的时候，我们往往可能需要做一些对url的处理，其中包括对相似的url的识别和处理。这就需要计算两个url的相似度。 那么怎么进行url相似度的计算的？我首先想到的是把一个url看作是一个字符串，这样就简化成两个字符串相似度的计算。字符串相似度计算有很多已经比较成熟的算法，比如“编辑距离算法”，该算法描述了两个字符串之间转换需要的最小的编辑次数；还有一些其他的比如“最长公共字串”等方法。但这些方法对于url相似度的计算来说是不是够了呢？
在blogspot上看到一个十分有趣的字符串算法题目，原文在这里。作者讲述了自己面试google的一次经历。本文不理会这个故事，只来讨论一下里面着个有趣的算法。 算法题目：有两个字符串由不同的字母组成，一长一短，长的为A短的为B。设计一个算法，如果所有在B中出现的字符都在A中出现，则返回true，否则返回false。例子： 如下字符串： 字符串A: abddfdioegdddffsfagj 字符串B: dofsjadg 字符串B中每个字符都在A中出现，返回true。 如下字符串： 字符串A: aaaabbbbbbdddddd 字符串B: acc 字符串B中有字符没在A中出现，返回false。
熟悉c的人都知道，sizeof是一个关键字而不是一个宏或者库函数什么的，他的值是在编译时确定的，如果这个不了解，可以现看看这篇文章和这篇文章。 既然如此，让我们先看下面几个小例子： sizeof(int); sizeof(char); sizeof(double); 上面三行sizeof的值是多少呢？这里我们假定在32位的x86系统下。我们会得到答案：4，1，8。这个没什么吧，大多数人都应该知道。那么，下面这个： sizeof(int); sizeof(long); 在32位x86下，这两个是多少呢？4，8？实际上，答案是4，4。我们需要注意，long类型在32位系统下是32位的。那么，64位下结果又如何呢？8，8？其实答案是4，8。另一个需要注意的是，64位下的int是32位的。
treap 是一个很有意思的数据结构，从名字也能看得出来，它是 tree 和 heap 的混合产物。为什么会有这么一个数据结构还得从二叉树(BST)说起。 我们都知道，普通的二叉树是不平衡的，在某些情况下进行插入删除操作可以导致时间复杂度从 O(logN) 下降到 O(N)。为了解决平衡的问题，有很多新的二叉树被引入，比如大家熟知的一些：Linux 内核中 CFS 使用到的红黑树(Red-black tree)，数据结构课上都会讲到的 AVL 树。这些树都因为要进行复杂的旋转操作而不容易实现。 那么有没有一个实现容易的平衡二叉树呢？Treap 就是一个。普通的二叉树节点只有 key，而 treap 又多了一个 priority，这里的 priority 就是 heap (优先队列)中的 priority。这样， treap 既可以利用二叉树的特性，又可以利用 heap 的特性了。
平时一直都在用非常简单的表达式，匹配位置的时候，用几个元字符就够了。当今天不得不从别人的C源代码中取出一个特定宏的定义时候，终于觉得我要用零宽断言来匹配位置了。用的是python的 re模块，开始半天都匹配不上，因为是GUI程序，竟然也没有仔细看控制台的输出。后来仔细看了一下，又google了一下，看到两个匹配要取出字符串前面的零宽断言都必须是定长的时候……才明白怎么回事。
• 空指针的解引用
空指针解引用是否导致异常应该是硬件设备和OS组合决定的。以前在VXwork下工作，空指针也可以解引用，可以访问内存0地址，还可以修改内容。这种情况下，为了便于程序员debug，印象中我们大概是采用了对于0地址内容监控，如果内容有改动则报告或者crash。
• 聊聊如何检测素数
最近看到一则颇为有趣的新闻，说北大一名大一新生，以素数为标准选手机号，受到广大网友膜拜。其实素数的检测算法是很有趣的，并且会涉及到数论、概率算法等诸多内容，一直觉得素数探测算法是了解概率算法很好的入口。本文和大家简单聊聊如何确定一个数是素数。
近3天十大热文
-
[55] Oracle MTS模式下 进程地址与会话信 -
[55] IOS安全–浅谈关于IOS加固的几种方法
-
[54] 如何拿下简短的域名
-
[53] 图书馆的世界纪录
-
[53] android 开发入门
-
[52] Go Reflect 性能
-
[49] 【社会化设计】自我（self）部分――欢迎区
-
[49] 读书笔记-壹百度:百度十年千倍的29条法则
-
[38] 程序员技术练级攻略
-
[32] 视觉调整－设计师 vs. 逻辑
赞助商广告
