web analytics

存档

文章标签 ‘Algorithm’

二维码的生成细节和原理

2013年10月29日 没有评论 172 人阅读    

二维码又称QR Code,QR全称Quick Response,是一个近几年来移动设备上超流行的一种编码方式,它比传统的Bar Code条形码能存更多的信息,也能表示更多的数据类型:比如:字符,数字,日文,中文等等。这两天学习了一下二维码图片生成的相关细节,觉得这个玩意就是一个密码算法,在此写一这篇文章 ,揭露一下。供好学的人一同学习之。

关于QR Code Specification,可参看这个PDF:http://raidenii.net/files/datasheets/misc/qr_code.pdf 

基础知识

首先,我们先说一下二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵,Version 2是 25 x 25的矩阵,Version 3是29的尺寸,每增加一个version,就会增加4的尺寸,公式是:(V-1)*4 + 21(V是版本号) 最高Version 40,(40-1)*4+21 = 177,所以最高是177 x 177 的正方形。

下面我们看看一个二维码的样例:

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (1 人打了分,平均分: 5.00 )
Loading ... Loading ...

伙伴分配器的一个极简实现

2013年10月9日 31 条评论 7,618 人阅读    

(感谢网友 @我的上铺叫路遥 投稿)

提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当于分离出若干个块大小一致的空闲链表,搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并(O(logN)时间复杂度)以及低外部碎片(最佳适配best-fit);其缺点是内部碎片,因为按2的幂划分块,如果碰上66单位大小,那么必须划分128单位大小的块。但若需求本身就按2的幂分配,比如可以先分配若干个内存池,在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述,大体如是:

分配内存:

1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂,比如需要27,实际分配32)

1.如果找到了,分配给应用程序。
2.如果没找到,分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度,分配这个大小。
3.回溯到步骤1(寻找合适大小的块)
4.重复该步骤直到一个合适的块

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (9 人打了分,平均分: 4.78 )
Loading ... Loading ...

二叉树迭代器算法

2013年7月14日 33 条评论 11,830 人阅读    

(感谢 @文艺复兴记(todd) 投递此文)

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (10 人打了分,平均分: 4.90 )
Loading ... Loading ...

程序算法与人生选择

2012年12月28日 170 条评论 68,532 人阅读    

每年一到要找工作的时候,我就能收到很多人给我发来的邮件,总是问我怎么选择他们的offer,去腾讯还是去豆瓣,去外企还是去国内的企业,去创业还是去考研,来北京还是回老家,该不该去创新工场?该不该去thoughtworks?……等等,等等。今年从7月份到现在,我收到并回复了60多封这样的邮件。我更多帮他们整理思路,帮他们明白自己最想要的是什么。(注:我以后不再回复类似的邮件了)。

我深深地发现,对于我国这样从小被父母和老师安排各种事情长大的人,当有一天,父母和老师都跟不上的时候,我们几乎完全不知道怎么去做选择。而我最近也离开了亚马逊,换了一个工作。又正值年底,就像去年的那篇《三个故事和三个问题》一样,让我想到写一篇这样的文章。

几个例子

当我们在面对各种对选择的影响因子的时候,如:城市,公司规模,公司性质,薪水,项目,户口,技术,方向,眼界…… 你总会发现,你会在几个公司中纠结一些东西,举几个例子:

  • 某网友和我说,他们去上海腾讯,因为腾讯的规模很大,但却发现薪水待遇没有豆瓣高(低的还不是一点),如果以后要换工作的话,起薪点直接关系到了以后的高工资。我说那就去豆瓣吧,他说豆瓣在北京,污染那么严重,又没有户口,生存环境不好。我说去腾讯吧,他说腾讯最近组织调整,不稳定。我说那就去豆瓣吧,慢公司,发展很稳当。他说,豆瓣的盈利不清楚,而且用Python,自己不喜欢。我说,那就去腾讯吧,……
  • 还有一网友和我说,他想回老家,因为老家的人脉关系比较好,能混得好。但又想留在大城市,因为大城市可以开眼界。

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (111 人打了分,平均分: 4.94 )
Loading ... Loading ...

如何测试洗牌程序

2012年11月20日 112 条评论 21,489 人阅读    

我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。

我们有一个程序,叫ShuffleArray(),是用来洗牌的,我见过N多千变万化的ShuffleArray(),但是似乎从来没人去想过怎么去测试这个算法。所以,我在面试中我经常会问应聘者如何测试ShuffleArray(),没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题,其实,测试程序可能比算法更难写,代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗?》中我所推崇的——开发人员更适合做测试的观点。

我们先来看几个算法(第一个用递归二分随机抽牌,第二个比较偷机取巧,第三个比较通俗易懂

递归二分随机抽牌

有一次是有一个朋友做了一个网页版的扑克游戏,他用到的算法就是想模拟平时我们玩牌时用手洗牌的方式,是用递归+二分法,我说这个程序恐怕不对吧。他觉得挺对的,说测试了没有问题。他的程序大致如下(原来的是用Javascript写的,我在这里凭记忆用C复现一下):

//递归二分方法
const size_t MAXLEN = 10;
const char TestArr[MAXLEN] = {'A','B','C','D','E','F','G','H','I','J'};

static char RecurArr[MAXLEN]={0};
static int cnt = 0;
void ShuffleArray_Recursive_Tmp(char* arr, int len)
{
    if(cnt > MAXLEN || len <=0){
        return;
    }

    int pos = rand() % len;
    RecurArr[cnt++] = arr[pos];
    if (len==1) return;
    ShuffleArray_Recursive_Tmp(arr, pos);
    ShuffleArray_Recursive_Tmp(arr+pos+1, len-pos-1);
}

void ShuffleArray_Recursive(char* arr, int len)
{
    memset(RecurArr, 0, sizeof(RecurArr));
    cnt=0;
    ShuffleArray_Recursive_Tmp(arr, len);
    memcpy(arr, RecurArr, len);
}

void main()
{
    char temp[MAXLEN]={0};
    for(int i=0; i<5; i++) {
        strncpy(temp, TestArr, MAXLEN);
        ShuffleArray_Recursive((char*)temp, MAXLEN);
    }
}

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (19 人打了分,平均分: 4.89 )
Loading ... Loading ...

TF-IDF模型的概率解释

2012年10月24日 34 条评论 12,280 人阅读    

(感谢 @猫叔shiro(以前的todd) 投递此文)

信息检索概述

信息检索是当前应用十分广泛的一种技术,论文检索、搜索引擎都属于信息检索的范畴。通常,人们把信息检索问题抽象为:在文档集合D上,对于由关键词w[1] … w[k]组成的查询串q,返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D’。

对于这一问题,先后出现了布尔模型、向量模型等各种经典的信息检索模型,它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础,查询效率高,但模型过于简单,无法有效地对不同文档进行排序,查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量,而文档与查询的相关性即对应于向量间的夹角。不过,由于通常词的数量巨大,向量维度非常高,而大量的维度都是0,计算向量夹角的效果并不好。另外,庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前,真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是:如果词w在一篇文档d中出现的频率高,并且在其他文档中很少出现,则认为词w具有很好的区分能力,适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素:

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (15 人打了分,平均分: 4.80 )
Loading ... Loading ...

无锁队列的实现

2012年9月7日 82 条评论 39,558 人阅读    

关于无锁队列的实现,网上有很多文章,虽然本文可能和那些文章有所重复,但是我还是想以我自己的方式把这些文章中的重要的知识点串起来和大家讲一讲这个技术。下面开始正文。

关于CAS等原子操作

在开始说无锁队列之前,我们需要知道一个很重要的技术就是CAS操作——Compare & Set,或是 Compare & Swap,现在几乎所有的CPU指令都支持CAS的原子操作,X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作,我们就可以用其来实现各种无锁(lock free)的数据结构。

这个操作用C语言来描述就是下面这个样子:(代码来自Wikipedia的Compare And Swap词条)意思就是说,看一看内存*reg里的值是不是oldval,如果是的话,则对其赋值newval。

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  return old_reg_val;
}

这个操作可以变种为返回bool值的形式(返回 bool值的好处在于,可以调用者知道有没有更新成功):

bool compare_and_swap (int *accum, int *dest, int newval)
{
  if ( *accum == *dest ) {
      *dest = newval;
      return true;
  }
  return false;
}

与CAS相似的还有下面的原子操作:(这些东西大家自己看Wikipedia吧)

注:在实际的C/C++程序中,CAS的各种实现版本如下:

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (16 人打了分,平均分: 4.88 )
Loading ... Loading ...

为什么我反对纯算法面试题

2012年8月22日 123 条评论 43,452 人阅读    

算法面试可能是微软搞出来的面试方法,现在很多公司都在效仿,而且我们的程序员也乐于解算法题,我个人以为,这是应试教育的毒瘤!我在《再谈“我是怎么招程序员”》中比较保守地说过,“问难的算法题并没有错,错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”,今天,我想加强一下这个观点——我反对纯算法题面试!(注意,我说的是纯算法题)

图片源Wikipedia(点击图片查看词条)

我再次引用我以前的一个观点——

能解算法题并不意味着这个人就有能力就能在工作中解决问题,你可以想想,小学奥数题可能比这些题更难,但并不意味着那些奥数能手就能解决实际问题。

好了,让我们来看一个示例(这个示例是昨天在微博上的一个讨论),这个题是——“找出无序数组中第2大的数”,几乎所有的人都用了O(n)的算法,我相信对于我们这些应试教育出来的人来说,不用排序用O(n)算法是很正常的事,连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了,这是我国教育最悲哀的地方。(广义的洗脑就是让你的意识依赖于某个标准答案,然后通过给你标准答案让你不会思考而控制你)

功能性需求分析

试想,如果我们在实际工作中得到这样一个题 我们会怎么做?我一定会分析这个需求,因为我害怕需求未来会改变,今天你叫我找一个第2大的数,明天你找我找一个第4大的数,后天叫我找一个第100大的数,我不搞死了。需求变化是很正常的事。分析完这个需求后,我会很自然地去写找第K大数的算法——难度一下子就增大了。

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (37 人打了分,平均分: 4.81 )
Loading ... Loading ...

K Nearest Neighbor 算法

2012年8月17日 22 条评论 13,545 人阅读    

K Nearest Neighbor算法又叫KNN算法,这个算法是机器学习里面一个比较经典的算法, 总体来说KNN算法是相对比较容易理解的算法。其中的K表示最接近自己的K个数据样本。KNN算法和K-Means算法不同的是,K-Means算法用来聚类,用来判断哪些东西是一个比较相近的类型,而KNN算法是用来做归类的,也就是说,有一个样本空间里的样本分成很几个类型,然后,给定一个待分类的数据,通过计算接近自己最近的K个样本来判断这个待分类数据属于哪个分类。你可以简单的理解为由那离自己最近的K个点来投票决定待分类数据归为哪一类

Wikipedia上的KNN词条中有一个比较经典的图如下:

从上图中我们可以看到,图中的有两个类型的样本数据,一类是蓝色的正方形,另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。

  • 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
  • 如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。

我们可以看到,机器学习的本质——是基于一种数据统计的方法!那么,这个算法有什么用呢?我们来看几个示例。

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.57 )
Loading ... Loading ...

K-Means 算法

2012年6月29日 28 条评论 25,147 人阅读    

最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家。

在数据挖掘中, k-Means 算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。

问题

K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,我们用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了我们的K-Means算法(Wikipedia链接

K-Means 要解决的问题

算法概要

这个算法其实很简单,如下图所示:

阅读全文…

好烂啊有点差凑合看看还不错很精彩 (10 人打了分,平均分: 5.00 )
Loading ... Loading ...