Browsed by
分类:杂项资源

如何测试洗牌程序

如何测试洗牌程序

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

我们有一个程序,叫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);
    }
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 4.71 )
Loading...
TF-IDF模型的概率解释

TF-IDF模型的概率解释

(感谢 @猫叔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和其他文章区分开来。该模型主要包含了两个因素:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (16 人打了分,平均分: 4.56 )
Loading...
xkcd 神图“Click and Drag”

xkcd 神图“Click and Drag”

xkcd对于经常浏览国外网站的朋友一定不会陌生。不过,还是先让我来介绍一下xkcd(维基百科词条)。这是一个漫画网站,它主要是发布一些很简单的随手画的漫画,它主要有四种体裁——浪漫、讽刺、数学 和 语言。也会经常出现一些和IT有关的漫画,比如下面这个漫画—— (懂Unix的人一眼就看懂了,不懂的怎么看也看不懂)

本质上来说,xkcd是一种Geek文化,里面的东西都非常的Geek和晦涩,讽刺很辛辣,但很多只有特定人群可以看得懂。而且表达的形式自由到天马行空,飘忽不定。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (39 人打了分,平均分: 4.64 )
Loading...
Bret Victor – Learnable Programming

Bret Victor – Learnable Programming

大家是否还记得之前酷壳向大家介绍的苹果设计师Bret Victor一种可视编程的视频《Bret Victor – Inventing on Principle》,最近,他写了一篇文章—— Learnable Programming,写这篇文章的原因是因为“可汗学院(Khan Academy)”近期上线的一个在线编程环境,根据他的演讲提供了一堆基于Javascript的“实时编程”的环境,因为这个环境是引用了他的想法,所以,他有必要出来喷两句。

这篇文章的开头就是一个问题——“How do we get people to understand programming?”,我们怎么让人们懂得编程?

然后,他说了两条——

  • 编程是一种思考,而不是一种死记硬背的技能!你学会了“for循环”并不是说你就学会了编程,这就好像你知道有铅笔这个东西,但是你对绘画还是什么不懂。(对于这一条,正好这两天我在微博上和人辩论“基础算法面试题是否好”(还有微博一微博二),而且我以前也写过一篇《为什么我反对纯算法面试》,这里借用Bret的话再加强一下我的观点——“我们一方面在骂中国的应试教育毁了学生,另一方面我们又在把我们的面试变成“考八股文”式的考试!  你会qsort有什么用?你只不过是会用一支高级铅笔而已罢了。”)
  • 人只有看得见,才能理解。如果一个程序员不能看到他的程序在干什么,那么她就不能理解程序。(对于这一条,让我想到了Donald Knuth的话——“An algorithm must be seen to be believe!”)

所以,Bret 觉得编程软件的目标是——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 4.50 )
Loading...
对九个超级程序员的采访

对九个超级程序员的采访

原文:《Q&A With Nine Great Programmers》时间有限,我只能粗译,难免错误。

这篇访谈源自2006年,最先发布在波兰程序员 Jaroslaw “sztywny” Rzeszótko (AKA “Stiff”) 的博客上。但是这篇博文现在找不到了。非常感谢他能授权我重新发布这个博文。

在一个炎热无聊的下午,我突发奇想。我想通过电子邮件的方式对那些我非常感兴趣和非常敬重的程序员问10个问题。准备这10个问题我只花了5分钟,这些都是我个人想问他们的问题,所以,我基本上没想太多要问他们什么。最后两个问题和编程没有什么关系,我就是想问题这些人的一些兴趣爱好。另外,不是每一个人都想回答我的,这是我第一次做“访谈”,所以,我犯了一些错误,一些问题没有得到回答。不管怎么样,我得到了很多很有意思的内容,所以,这对我绝对是一次很有意义的经历。

并不是每一个人都回了我的邮件,也并不是每一个人都同意回答我的这些问题,也许在我发布这篇文章后我会得到那些回答,但是我已经迫不及待想把这些东西发布了,所以,我可能会更新这篇文章(更新:2006年3月8日,我收到了Bjarne Stroustrup的回信

— Jaroslaw

介绍

  • Dave Thomas – “Pragmatic Programmer”(注:douban) 和 “Programming Ruby”(注:douban) 以及其它一些优秀书籍的作者。 你可以在 这里 读读他对编程的一些想法。
  • Steve Yegge – 他可能并不那么知名,但是他给了很多有意思的回答。他有一个很火的关于编程的 blog,他也是游戏 “Wyvern” 的作者。(陈皓注:他最火的是去年在google+上对google和amazon的吐槽,06年他应该在google了)
好烂啊有点差凑合看看还不错很精彩 (21 人打了分,平均分: 4.57 )
Loading...
“单元测试要做多细?”

“单元测试要做多细?”

这篇文章主要来源是StackOverflow上的一个回答——“How deep are your unit tests?”。一个有13.8K的分的人(John Nolan)问了个关于TDD的问题,这个问题并不新鲜,最亮的是这个问题的Best Answer,这个问题是——

“TDD需要花时间写测试,而我们一般多少会写一些代码,而第一个测试是测试我的构造函数有没有把这个类的变量都设置对了,这会不会太过分了?那么,我们写单元测试的这个单元的粒度到底是什么样的?并且,是不是我们的测试测试得多了点?”

答案

StackOverflow上,这个问题的答案是这样的——

“I get paid for code that works, not for tests, so my philosophy is to test as little as possible to reach a given level of confidence (I suspect this level of confidence is high compared to industry standards, but that could just be hubris). If I don’t typically make a kind of mistake (like setting the wrong variables in a constructor), I don’t test for it. I do tend to make sense of test errors, so I’m extra careful when I have logic with complicated conditionals. When coding on a team, I modify my strategy to carefully test code that we, collectively, tend to get wrong.”

老板为我的代码付报酬,而不是测试,所以,我对此的价值观是——测试越少越好,少到你对你的代码质量达到了某种自信(我觉得这种的自信标准应该要高于业内的标准,当然,这种自信也可能是种自大)。如果我的编码生涯中不会犯这种典型的错误(如:在构造函数中设了个错误的值),那我就不会测试它。我倾向于去对那些有意义的错误做测试,所以,我对一些比较复杂的条件逻辑会异常地小心。当在一个团队中,我会非常小心的测试那些会让团队容易出错的代码。

这个回答对TDD似乎有一种否定,最亮的是这个问题是由Kent Beck,Kent是XP和TDD的创造者,是敏捷开发实践方法的奠基人。以致于还有人调侃到——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (19 人打了分,平均分: 4.47 )
Loading...
一次Ajax查错的经历

一次Ajax查错的经历

先说故事,再说想法吧。

我有一朋友做网站,用jQuery的Ajax方法从后端载入一段HTML代码然后动态插入到网页的Div元件中。这个东西太普遍了。jQuery强大的load方法可以完成这个事情。朋友的代码是这么写的:

var tab = jQuery("#dynamic_tab");
var url = "/list_ajax/";
tab.load(url);

简单到不能再简单了。在Chrome,Firefox,Safari下运行一点问题也没有,只有IE不行,不管是IE7,IE8,还是IE9。问题的症壮是,使用IE访问那个Ajax的链接,没有问题,但是在jQuery的Ajax方法返回了“undefined”的respons对象。没有任何报错!

怎么搞也搞不定,只好Google了一下——“jQuery load IE”,一看,很多人都在问这个问题。于是开始了散弹枪编程方式

排在第一的就是StackOverflow被浏览了33K次的这个问题:jQuery’s .load() not working in IE – but fine in Firefox, Chrome and Safari,答案没有被打勾(不靠谱),StackOverflow还有很多人问相似的问题,不过都没有答案。不管三七二十一,先试了一下,散弹枪嘛。试了半天都没有用。

然后上Google查,又看到有人说的IE缓存的问题,什么,要把cache设置成false,或是用下面的方法来解决:

var tab = jQuery("#dynamic_tab");
var fuckie = Math.random();
var url = "/list_ajax/"+"?fuckie="+fuckie;
tab.load(url);

反正还是一样,统统不Work,几乎所有的都试了,都不Work。搞了一天的朋友恼怒道:“Microsoft应该快点倒闭吧,产品太烂了”。IE的确是太烂了。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 4.55 )
Loading...
GCC 用 C++ 来编译

GCC 用 C++ 来编译

GCC在2012年8月15日的时候,merge了一个patch – Merge from cxx-conversion branch,这意味着,以后在GCC的编译只能用C++的编译器了,也意味着,gcc的实现代码开始转向C++了。

你可能会有两个问题,

  • 一个问题是为什么GCC要转成C++的实现?
  • 没有C++的编译器,我怎么编译C++编译器的代码?这不是“鸡生蛋还是蛋生鸡”的问题么?

那,我们来看一看吧。

为什么要用C++

GNU的C++ Conversion文档中,我们可以在Background中看到这样的描述:

Whether we use C or C++, we need to try to ensure that interfaces are easy to understand, that the code is reasonably modular, that the internal documentation corresponds to the code, that it is possible for new developers to write new passes and to fix bugs. Those are the important issues for us to consider. The C++ features which are not present in C — features which are well documented in many books and many web sites — are not an important issue.

这句话的意思可以理解为,今天GCC在用C语言的实现已经有点hold不住了,因为,开发人员觉得,不管我们用C或C++,都需要努力确保接口是容易理解的,这样我们的代码是想当理性地被模块化的,这样内部文档和代码一致,这样可以更好地组织代码,这样有利于新人了fix-bug。而C++正好可以让他们更好的完成这些东西。

GNU还给出了下面这些理由:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.12 )
Loading...
K Nearest Neighbor 算法

K Nearest Neighbor 算法

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个点投票,于是绿色的这个待分类点属于蓝色的正方形。

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (18 人打了分,平均分: 4.61 )
Loading...
对技术的态度

对技术的态度

最近人品爆发,图灵社区,InfoQ,51CTO相继对我做了采访,前两天我把InfoQ对我的采访张贴了出来,今天,图灵社区和51CTO对我的采访发布了(图灵的访谈 ,51CTO的访谈),我是一个有技术焦虑症的人,我的经历比较特殊,对大家来说可能也没有什么意思,这两个采都有一些重叠的部分,不过有些观点我想再加强一些,并放在这里和大家一起分享一下。

对于日新月异的新技术,你是什么态度?

遇到新技术我会去了解,但不会把很大的精力放在这些技术(如:NoSQL,Node.js,等)。这些技术尚不成熟,只需要跟得住就可以了。技术十年以上可能是一个门槛。有人说技术更新换代很快,我一点儿都不觉得是这样想。虽然有不成熟的技术不断地涌出,但是成熟的技术,比如Unix,40多年,C,40多年,C++,30多年,TCP/IP,20多年,Java也有将近20年了……,所以,如果你着眼成熟的技术,其实并不多。

我的观点是——要了解技术就一定需要了解整个计算机的技术历史发展和进化路线。(这个观点,我在《程序员练级攻略》和《C++的坑多吗?》中提到过多次了。)因为,你要朝着球运动的轨迹去,而不是朝着球的位置去,要知道球的运动轨迹,你就需要知道它历史上是怎么跑的

如果要捋一个技术的脉络,70年代Unix的出现,是软件发展方面的一个里程碑,那个时期的C语言,也是语言方面的里程碑。(当时)所有的项目都在Unix/C上,全世界人都在用这两样东西写软件。Linux跟随的是Unix, Windows下的开发也是 C/C++。这时候出现的C++很自然就被大家接受了,企业级的系统很自然就会迁移到这上面,C++虽然接过了C的接力棒,但是它的问题是它没有一个企业方面的架构,而且太随意了,否则也不会有今天的Java。C++和C非常接近,它只不过是C的一个扩展,长年没有一个企业架构的框架。而Java在被发明后,被IBM把企业架构这部分的需求接了过来,J2EE的出现让C/C++捉襟见肘了,在语言进化上,还有Python/Ruby,后面还有了.NET,但可惜的是这只局限在Windows平台上。这些就是企业级软件方面语言层面就是C -> C++ -> Java这条主干,操作系统是Unix -> Linux/Windows这条主干,软件开发中需要了解的网络知识就是Ethernet -> IP -> TCP/UDP 这条主干。另外一条脉络就是互联网方面的(HTML/CSS/JS/LAMP…)。我是一个有技术忧虑症的人,这几条软件开发的主线一定不能放弃。

另外,从架构上来说,我们可以看到,

阅读全文 Read More

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