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

好烂啊有点差凑合看看还不错很精彩 (30 人打了分,平均分: 4.10 )
Loading...
Go 语言简介(下)— 特性

Go 语言简介(下)— 特性

希望你看到这篇文章的时候还是在公交车和地铁上正在上下班的时间,我希望我的这篇文章可以让你利用这段时间了解一门语言。当然,希望你不会因为看我的文章而错过站。呵呵。

如果你还不了解Go语言的语法,还请你移步先看一下上篇——《Go语言简介(上):语法

goroutine

GoRoutine主要是使用go关键字来调用函数,你还可以使用匿名函数,如下所示:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (34 人打了分,平均分: 4.24 )
Loading...
Go 语言简介(上)— 语法

Go 语言简介(上)— 语法

周末天气不好,只能宅在家里,于是就顺便看了一下Go语言,觉得比较有意思,所以写篇文章介绍一下。我想写一篇你可以在乘坐地铁或公交车上下班时就可以初步了解一门语言的文章。所以,下面的文章主要是以代码和注释为主。只需要你对C语言,Unix,Python有一点基础,我相信你会在30分钟左右读完并对Go语言有一些初步了解的。

Hello World

//文件名:hello.go
package main //声明本文件的package名

import "fmt" //import语言的fmt库——用于输出

func main() {
    fmt.Println("hello world")
}

阅读全文 Read More

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

xkcd 神图“Click and Drag”

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (43 人打了分,平均分: 4.30 )
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

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 3.92 )
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了)
好烂啊有点差凑合看看还不错很精彩 (27 人打了分,平均分: 4.04 )
Loading...
无锁队列的实现

无锁队列的实现

————注:本文于2019年11月4日更新————

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

关于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;
}

我们可以看到,old_reg_val 总是返回,于是,我们可以在 compare_and_swap 操作之后对其进行测试,以查看它是否与 oldval相匹配,因为它可能有所不同,这意味着另一个并发线程已成功地竞争到 compare_and_swap 并成功将 reg 值从 oldval 更改为别的值了。

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

bool compare_and_swap (int *addr, int oldval, int newval)
{
  if ( *addr != oldval ) {
      return false;
  }
  *addr = newval;
  return true;
}

与CAS相似的还有下面的原子操作:(这些东西大家自己看Wikipedia,也没什么复杂的)

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (53 人打了分,平均分: 4.21 )
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

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

一次Ajax查错的经历

先说故事,再说想法吧。

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

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

简单到不能再简单了。在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,或是用下面的方法来解决:

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (32 人打了分,平均分: 3.88 )
Loading...
为什么我反对纯算法面试题

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

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

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

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

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

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

功能性需求分析

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

阅读全文 Read More

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