高性能Node.js:来自LinkedIn Mobile的10条优化建议

上午在微博上看到@Python发烧友 转发了这篇来自LinkedIn团队的文章《Blazing fast node.js: 10 performance tips from LinkedIn Mobile》。看过后觉得非常有参考价值,于是午休后花了一点时间将它翻译成中文,希望能给不习惯英文阅读的朋友带来一定方便。
以前做翻译的经验较少,处理得不好的地方还望海涵。:-)

一、避免使用同步代码(Avoid synchronous code)
Node.js是单线程的。为了使单线程可以处理多个并发请求,我们不应该让线程来等待一个阻塞的、同步的或是长时间运行的操作。Node.js的一个突出的特性就是它被完全地设计并实现为异步的。这使得其可以非常好地适用于事件驱动的程序。

遗憾的是,我们仍然有可能使用到同步/阻塞的调用。例如,很多对文件系统的操作都提供了同步和异步的两个版本,就像writeFilewriteFileSync。有时即使我们没有在自己的代码中使用同步的方法,但仍然有可能在无意中使用了包含阻塞调用的某个外部库。当您使用到同步/阻塞调用时,对性能的影响是巨大的。

// Good: write files asynchronously
fs.writeFile('message.txt', 'Hello Node', function (err) {
  console.log("It's saved and the server remains responsive!");
});

// BAD: write files synchronously
fs.writeFileSync('message.txt', 'Hello Node');
console.log("It's saved, but you just blocked ALL requests!");

我们最初的日志系统的实现中,不慎使用了一个写磁盘的同步调用。直到我们做性能测试之前这个情况一直没有被我们注意到。当我们在开发环境中对一个单实例的Node.js程序作基准测试的时候,这个同步调用使得吞吐率(requests per second)从几千一下子下降到了几十!

二、关闭socket池(Turn off socket pooling)
Node.js的http client自动使用socket池:在默认情况下,主机能同时并发打开的socket数量被限制为5个。虽然socket的重用也许能控制资源消耗的增长,但当我们需要处理多个从同一主机获取数据的并发请求时,这将是一个严重的瓶颈。在这些情况下,好的解决方案是增加maxSockets或者完全禁用socket池:

// Disable socket pooling

var http = require('http');
var options = {.....};
options.agent = false;
var req = http.request(options)

三、不要用Node.js处理静态文件(Don’t use Node.js for static assets)
对于静态文件,例如CSS和图片,建议使用标准的webserver来处理而非Node.js。例如LinkedIn mobiles使用的是nginx。并且我们使用CDN,将静态文件复制到遍布于全世界的各个节点。以上这些将带来两个好处:1、可以减轻Node.js服务器的负载;2、借助于CDN使得静态文件可以从离用户更近的节点传输予之,从而降低时延。

四、将渲染放到客户端做(Render on the client-side)
让我们来简单地对在服务器端和在客户端渲染一个页面进行一个比较。如果我们使用Node.js在服务器端进行渲染,在每次请求中我们将返回以下的HTML页面:

<!-- An example of a simple webpage rendered entirely server side -->

<!DOCTYPE html>
<html>
  <head>
    <title>LinkedIn Mobile</title>
  </head>
  <body>
    <div class="header">
      <img src="http://mobile-cdn.linkedin.com/images/linkedin.png" alt="LinkedIn"/>
    </div>
    <div class="body">
      Hello John!
    </div>
  </body>
</html>

请注意到这个页面上除了用户的名称之外的所有东西都是静态的:也就是说,这些对于每个用户以及每次页面重载都是相同的。因此,一个更高效的做法是让Node.js以JSON格式只返回页面所需要的动态数据:

{"name": "John"}

页面的其余部分­——所有的静态HTML标记­——可以放入一个JavaScript模板(譬如一个underscore.js模板):

<!-- An example of a JavaScript template that can be rendered client side -->

<!DOCTYPE html>
<html>
  <head>
    <title>LinkedIn Mobile</title>
  </head>
  <body>
    <div class="header">
      <img src="http://mobile-cdn.linkedin.com/images/linkedin.png" alt="LinkedIn"/>
    </div>
    <div class="body">
      Hello <%= name %>!
    </div>
  </body>
</html>

这样做的性能提升来自前述的第三条建议,静态的JavaScript模板可以用我们的webserver(譬如nginx)来处理,甚至是使用CDN就更好了。此外,JavaScript模板可以被浏览器缓存或者保存在LocalStorage中。这样一来在页面第一次被加载后,需要发送给客户端的数据就只有动态的JSON了,极大地提升了效率。这个方法大大降低了Node.js的CPU、I/O消耗和负载。

五、使用gzip(Use gzip)
大多数的服务器和客户端程序都支持用gzip来压缩请求和响应。请确保无论是在发送响应到客户端还是向远程服务器发送请求时,您都充分地利用到了它。

六、并行化(Go parallel)
尝试着将类似请求远程服务器、调用数据库和访问文件系统等将会引致阻塞的操作并行地执行。这样做的好处是,可以将完成一系列阻塞操作的总时延减小到其中最慢的某项操作所需要的时间,否则其总时延将会是完成操作序列中所有操作需要等待的时间总和。为了保持回调和错误处理函数的结构明晰,我们使用了Step来做flow control。

七、去session化(Go session-free)
LinkedIn mobile使用Express框架来处理请求/响应周期(request/response cycle)。大多数express的示例代码中包括了以下的配置:

app.use(express.session({ secret: "keyboard cat" }));

在默认情况下session数据存储在内存中,在用户数量增加的时候这会显著地增加服务器的开销。我们可以转而使用一个外部的session存储方案,例如MongoDB或Redis,但此时每个请求将增加远程调用获取session数据带来的额外开销。有可能的话,最好的选择是完全不在服务器端存储状态信息。不进行上述的express配置,不保存session,这样可以获得更好的性能。

八、使用二进制的模块(Use binary modules)
请尽可能地使用编译后的二进制模块而非用JavaScript编写的模块。举个例子,当我们从一个用JavaScript编写的SHA模块切换到Node.js内置的编译版本后,我们看到了巨大的性能提升:

// Use built in or binary modules
var crypto = require('crypto');
var hash = crypto.createHmac("sha1",key).update(signatureBase).digest("base64");

九、使用标准的V8 JavaScript而非客户端的库(Use standard V8 JavaScript instead of client-side libraries)
JavaScript的版本不统一,而大部分JavaScript库是提供给web浏览器使用的:例如一款浏览器或许支持类似forEach、map和reduce这样的函数,但其他浏览器并不支持。其结果是,客户端的库常常要用很多低效的代码来掩盖浏览器间的差异。另一方面,在使用Node.js时你确切地知道哪些JavaScript函数是可用的:驱动Node.js的V8 JavaScript引擎实现的是ECMAScript的ECMA-262,第五版。通过直接使用标准的V8函数,而不是客户端的库,您将会再一次体验到显著的性能提升。

十、保持代码精简、轻量(Keep your code small and light)
面向移动设备进行开发时,设备的速度更慢而且时延更高,这迫使我们保持代码精简、轻量。您同样也应该把这种思想带到服务器端代码的开发中。时不时地进行自省,并且问自己:“我们是否真的需要这个模块?”,“为什么我们要使用这个框架?它带来的开销是值得的吗?”,“我们能否用一种更简单的方法来实现?”。更精简,更轻量的代码通常也是更高效,更快的。

经典趣题:12个小球

前两天的《专家系统》课上,老师提到了那个经典的问题:
“有12个相同的小球,其中一个是次品,但不知道该次品是偏重还是偏轻。现给你一个天平,希望你只称量不超过三次,确定哪个小球是次品并判断它是偏重还是偏轻。”

这个推理题其实蛮老了,但题目出来后,仍然在同学们中引起了一阵思考和讨论。恰巧在高一的时候,同桌好友 @reecom 就已经问过我这个问题(并且是带有挑衅意味的~),下面分享一下我当时的解题思路。

为了方便接下来的表述,我们先将12个小球进行如下分组编号:
A(1, 2, 3, 4), B(1, 2, 3, 4), C(1, 2, 3, 4)

第一次称:取 A(1, 2, 3, 4) 和 B(1, 2, 3, 4) 作比较。
如果第一次称天平平衡,可判断次品在 C 组。
那么第二次称:取 A(1, 2, 3) 和 C(1, 2, 3) 比较。
如果平衡,则可确定次品为 C(4) 。此时我们第三次称:取 C(4) 和任意一个正常的小球做比较,确定次品的轻重。
如果不平衡, 则次品在 C(1, 2, 3) 中,且根据天平的倾斜情况可判断次品的轻重,我们这里假设是偏重。现在第三次称:取 C(1) 和 C(2) 比较,如果平衡,则次品为 C3 ;如果不平衡,按我们刚才的假设,偏重的一方则为次品。

如果第一次称的结果是不平衡,则次品存在于 A 组和 B 组,且 C 组全为正常。
那么此时第二次称的选取很关键:取 A(1), C(1, 2, 3) 和 B(1), A(2, 3, 4) 比较。

如果第二次称结果平衡,则可判断次品在 B(2, 3, 4) 中, 且根据第一次称天平的倾斜情况可以判断次品的轻重,同样我们这里假设偏重。下面第三次称:取 B(2) 和 B(3) 比较,如果平衡则次品为 B(4) ;如果不平衡,按我们刚才的假设,偏重的一方则为次品。

如果第二次称结果不平衡,则又有两种情况。
如果此时天平的倾斜情况较第一次称没有改变的话,则可以肯定次品为 A(1) 或 B(1) ,且可以得出他们的轻重情况。例如如果天平是倾向 A(1) 这一边的话,则必然是 A(1) 偏重或者 B(1) 偏轻,反之则必然是 A(1) 偏轻或者 B(1) 偏重。
于是第三次称:取 A(1) 与任意一个已确定的正常小球比较,如果平衡则次品为 B(1)。且根据第二次称时与 A(1) 的轻重比较可得出 B(1) 是偏重还是偏轻。如果不平衡那就很明显次品是 A(1) ,且轻重情况一目了然。

如果第二次称时天平的倾斜情况较第一次发生了改变,则可判断次品在 A(2, 3, 4) 中。且可得出是偏重还是偏轻,我们这里假设偏重。第三次称:取 A(2) 和 A(3) 比较,如果平衡则次品为 A(4) ;如果不平衡,按我们刚才的假设,偏重的一方则为次品。

Unix IO模型学习

学习中看到的好文,于是转了过来,分享给更多的朋友。
原文地址:http://www.zavakid.com/70

POSIX中对同步IO和异步IO的规定

  • 同步IO操作:引起进程的阻塞直到IO操作完成
  • 异步IO操作:IO操作不会引起进程阻塞

在UNIX下,有5中操作模型

  1. 阻塞IO (Blocking I/O Model)
  2. 非阻塞IO (Nonblocking I/O Model)
  3. IO复用 (I/O Multiplexing Model)
  4. 信号驱动IO (Signal-Driven I/O Model)
  5. 异步IO (Asynchronous I/O Model)

按照网络上的说法,前四种是属于同步IO,第五种才属于异步IO,对于这个结论,我的理解是根据用户进程是否阻塞来判断的(而不是内核进程)。关于同步和异步的一些讨论,可以参考http://bbs.chinaunix.net/viewthread.php?tid=947563

阻塞IO
这是我们熟悉的IO模型,一个进程在作IO操作时,非要等到数据从内核空间拷贝到用户进程空间,才会返回。这个模型的优点就是简单,而且在阻塞的时候,CPU还可以进行调度,去执行别的进程。

非阻塞IO
一开始我看是非阻塞IO,觉得应该要比阻塞IO模型先进,可是当我一看使用方法的时候,就知道这个模型是不会被实际使用的,仅仅只能作为理论上存在的IO模型。这个模型的观点是:进行IO操作的时候,不阻塞,如果没有数据准备好,就直接返回错误码(或者是别的代码)。因此,使用者就只能不断进行轮询来调用IO函数。这样的后果就是,不仅在宏观上形成了与阻塞IO一共的“阻塞”效果,而且在微观上,CPU一直被用来轮询,造成了CPU的浪费。所以,这个模型还不如阻塞IO模型实用。

IO复用
对于IO复用,我的理解有三点:

  1. 在一次系统调用中,实现了询问多个描述符的IO准备情况 —— 根据事件通知
  2. 为了实现第一点,就需要把阻塞的地方进行转移。把一次系统调用,分为两次系统调用。第一次系统调用可以询问多个描述符的IO准备情况,在这个地方进行阻塞;而第二次系统调用,是针对已经准备好IO的描述符进行调用,此时,理论上(按照我的理解),也是会发生阻塞的,只不过是此时内核已经把数据准备好了,阻塞的时间可以忽略不计罢了。
  3. 本质上,还是阻塞的。

信号IO
我们都知道,信号是UNIX提供了进程间进行通信的一种方式。我们常用的 kill -9 命令(kill是向进程传递信号量,9只是众多信号中的一个代号),或者是 Ctrl + C 的时候,就是向某个进程发出终止的信号,这样进程就退出了。

而对于信号IO的模型,我是这么理解的:进程在发起IO操作,系统调用之后,直接访问,内核会在IO数据准备好之后,以某个信号通知发起IO操作的进程,从而使得该进程的信号处理函数可以读取IO数据的操作。

本质上,这也是阻塞的IO模型,因为在信号处理函数中,同样也是要进行阻塞的,只是在在这个时候发起系统系统,内核已经把数据准备好了。

异步IO
这是真正的异步IO了。实现的机制是:用户在发起异步IO的系统调用时,会把相应的数据处理函数作为回调函数,等到IO数据准备好,内核会主动调用此回调函数。可以看出,用户进程在这种模型下,只调用了一次系统调用,而且是立即返回的,因此,就不会出现让进程阻塞的情况,也就符合了POSIX中异步IO的定义。

其实我理解起来,思路是和信号IO差不多的,唯一不同的地方,对于IO数据的操作,异步IO是由内核主动发起的,而信号IO是由用户进程发起的。

在排序数组中找出给定数字的出现次数

在排序数组中,找出给定数字的出现次数。比如:{1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9}中2出现的次数是3次。
当然你可以选择直接遍历整个数组,但是这样会让你在计算机系的MM面前抬不起头来。
我能想到的是借助二分查找的思想,先找到给定数开始和结束位置。这样在最坏的情况下,时间复杂度为O(logN)。

int getUpper(int *a, int n, int x)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while(low < high)
	{
		mid = (low + high + 1) / 2;
		if(a[mid] <= x)
		{
			low = mid;
		}
		else
		{
			high = mid - 1;
		}
	}
	return low;
}

int getLower(int *a, int n, int x)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while(low < high)
	{
		mid = (low + high) / 2;
		if(a[mid] >= x)
		{
			high = mid;
		}
		else
		{
			low = mid + 1;
		}
	}
	return high;
}

一道小题

今天被问到一个题:
1 2 3 4 5 6 7=91,在中间填入“+”或“-”让等式成立,求出所有成立的情况。

记得以前在成功的Blog上看到过一个类似的问题,当时没有仔细琢磨,今天居然又被问到了,看来这个题的出镜率挺高。
拿到这个题后,5分钟就写出了一个深搜的算法。
不就是穷举一下两种情况么,不是加就是减。写一个递归函数,简单而有效~

1秒钟后,我发现了一个大问题。即便是1+2+3+4+5+6+7也不能等于91啊?!
回过头来再仔细审一遍题,发现居然理解错意思了。并不是每个空都要填的,比如“1”和“2”之间如果不填的话就是“12”。

于是陷入一阵沉思,居然会犯这种错误。看来我这个老毛病一直没能改掉:每次做事都过于浮躁。
无论是考试还是在平时解决问题的过程中,常常没有审清题意、没有理清需求就开始动手。这样的结果,轻则无法把问题考虑周全,严重的时候可能完全曲解了题意。
想到自己还经常在自以为正确的道路上,因为异常的顺利而自信心爆棚,一路高歌前进。以至于直到最后才发现原来全盘皆错。
从小到大,因为这个坏毛病没少走弯路。还记得一位老师告诉过我,算法在心中还没来得及推敲就开始敲键盘,乃是程序员最不好的习惯之一。
今天这件事情,给我重重地敲响了一次警钟啊!

最后,再经过一番思考,将代码改成了如下可用的版本。我们依然是采用递归的写法,用中间变量构造每一种可能的情况。
运行后可得如下的答案:
123-45+6+7=91
12+3+4+5+67=91
1+23+4+56+7=91
但是似乎这个算法的效率不是那么理想,每一种情况都要全部遍历到底。在回溯的过程中我们应该可以剪枝的。

#include <stdio.h>
// 1 2 3 4 5 6 7 = 91

bool validate(char opt[])
{
	int sum = 0, lastNum = 1, curNum = 2;
	char lastOpt = '+';
	for(int i = 0; i <= 5; i++)
	{
		if(opt[i] == ' ') // 为空格则合并成一个数
		{
			lastNum = lastNum * 10 + curNum;
		}
		else
		{
			sum = (lastOpt == '+') ? (sum + lastNum) : (sum - lastNum);
			lastNum = curNum;
			lastOpt = opt[i];
		}
		curNum++;
	}
	sum = (lastOpt == '+') ? (sum + lastNum) : (sum - lastNum);
	if(sum == 91)
	{
		return true;
	}
	return false;

}

void backtrack(char *opt, int currentIndex)
{
	if(currentIndex > 5)
	{
		if(validate(opt))
		{
			// 打印出答案
			for(int i = 0; i < currentIndex; i++)
			{
				printf("%d%c", i + 1, opt[i]);
			}
			printf("7=91\n");
		}
		return;
	}
	// 穷举三种可能的情况
	opt[currentIndex] = ' ';
	backtrack(opt, currentIndex + 1);
	opt[currentIndex] = '+';
	backtrack(opt, currentIndex + 1);
	opt[currentIndex] = '-';
	backtrack(opt, currentIndex + 1);
	return;
}

int main()
{
	char opt[6];
	backtrack(opt, 0);
	return 0;
}

基于物品的协作型过滤

在之前的利用皮尔逊相关度系数构建一个简单的推荐系统一文中,我们一起构建了一个简单的电影推荐系统。
在那篇文章中我们使用基于用户的协作型过滤(user-based collaborative filtering)技术,利用来自以往每一位用户对电影的评价来构造样本数据集,然后借助皮尔逊相关度系数对新用户作出推荐。
在文章的末尾我们提到,这种方法对于一个小型的应用是完全没有问题的,但当站点的规模逐渐扩大的时候,我们也许将会需要一些更为智慧的解决方案。
那么,在本文中让我们一起来讨论利用基于物品的协作型过滤(item-based collaborative filtering)技术来改进我们的推荐系统。

在这里我们还将沿用之前文章中使用的样本数据。基于物品的协作型过滤的总体思路是对每件物品预先计算出与其最为相近的其他物品(在我们的示例中是电影),当我们需要为某位用户提供推荐时,就可以查看他曾经评分过的物品,并从中选出该用户比较喜好的,最后构造出一个列表,其中包含了与这些选中物品最为相近的其他物品。

此种方法的优越性在于,虽然我们同样需要检查所有的物品数据,但是物品间的比较不会像用户间的比较那么频繁变化。这也就是说,我们通常不需要不停地计算与每件物品最相近的其他物品。我们可以把这项任务放在网络流量不是那么大的时候进行,或者是在独立于主应用之外的另一台机器上单独执行。

下面我们就开始着手改进之前构建的推荐系统。
首先,我们要定义一个函数 transformPrefs,这个函数的作用是对我们使用的样本数据数组进行倒置处理,从而得到一个有关物品及其用户评价的数组。在具体的实现过程中,我们仅需要将样本数据中的用户与物品对换即可,这样就可以复用以前所写的方法了。

function transformPrefs($prefs)
{
	$result = array();
	foreach ($prefs as $person => $items)
	{
		foreach ($items as $item => $rating)
		{
			// 将物品和人员对调
			$result[$item][$person] = $rating;
		}
	}
	return $result;
}

现在,调用我们在之前文章中已经定义过的 topMatches 函数,可以得到一组与《阿凡达》最为相近的影片:

print_r(topMatches(transformPrefs($critics), '阿凡达'));

可以得到如下结果:

Array
(
    [在云端] => 0.65795169495977
    [盗梦空间] => 0.48795003647427
    [阿甘正传] => 0.11180339887499
    [人在囧途] => -0.17984719479905
    [线人] => -0.42289003161103
)

在本例中,可能存在着一些相关评价值为负的情况,例如上述结果中的《人在囧途》和《线人》,这表明那些喜欢《阿凡达》的用户,存在不喜欢《人在囧途》和《线人》的倾向(当然,这仅仅是个示例而已,我选用的样本数据也都是我臆造的:P)。

第二步我们构造一个包含相近物品的完整数据集,我们使用到下面的函数。
再次强调,这项工作无须在每次向用户提供推荐的时候都重复一次,在构建完一次数据集后我们可以在需要的时候重复使用之。

function calculateSimilarItems($pref)
{
	// 建立数组,存储这些物品最为相近的所有其他物品
	$result = array();

	// 以物品为中心对偏好矩阵实施倒置处理
	$itemPrefs = transformPrefs($pref);
	foreach ($itemPrefs as $item => $ratings)
	{
		// 寻找最为相近的物品
		$scores = topMatches($itemPrefs, $item);
		$result[$item] = $scores;
	}
	return $result;
}

该函数首先利用了第一步定义过的 transformPrefs 函数,获得有关物品及其用户评价的数组。然后我们在一个循环中遍历每项物品,并将用户对各物品评价的数组传入 topMatches 函数中,求得最为相近的物品及其相似度评价值。最后,该函数返回一个包含物品及其最相近物品列表的数组。
我们可以通过运行以下代码测试一下我们的程序:

print_r(calculateSimilarItems($critics));

得到类似于这样的返回信息:

Array
(
    [盗梦空间] => Array
        (
            [阿甘正传] => 0.76376261582598
            [阿凡达] => 0.48795003647427
            [在云端] => 0.33333333333333
            [人在囧途] => -0.61237243569579
            [线人] => -0.94491118252307
        )

    [阿甘正传] => Array
        (
            [盗梦空间] => 0.76376261582598
            [阿凡达] => 0.11180339887499
            [线人] => -0.33333333333333
            [人在囧途] => -0.56635211395485
            [在云端] => -0.6454972243679
        )

    ... ...

    [人在囧途] => Array
        (
            [线人] => 0.55555555555556
            [阿凡达] => -0.17984719479905
            [在云端] => -0.25
            [阿甘正传] => -0.56635211395485
            [盗梦空间] => -0.61237243569579
        )

)

虽然不需要在每次向用户提供推荐的时候都运行一次这个函数,但我们仍然需要及时执行该函数以确保物品的相似度不至于过期。通常我们需要在用户基数和评分数量还不是很大的时候频繁执行这一函数,而随着用户数量的不断增长,物品间的相似度评价值通常会越来越趋向稳定。

现在,我们已经可以在不遍历整个样本数据集的情况下,利用反映物品相似度的数组来给出推荐了。我们先取到用户评价过的所有物品,找出其相近物品,再根据相似度对其进行加权。我们可以很容易地根据物品数组来得到相似度。

影片 评分 人在囧途 评分x人在囧途 盗梦空间 评分x盗梦空间 线人 评分x线人
阿甘正传 4.5 -0.566 -2.547 0.764 3.438 -0.333 -1.4985
阿凡达 4.0 -0.18 -0.72 0.488 1.952 -0.423 -1.692
在云端 1.0 -0.25 -0.25 0.333 0.333 -0.486 -0.486
总计 -0.996 -3.517 1.585 5.723 -1.242 -3.6765
归一化结果 3.531 3.610 2.960

表格的每一行都列出的一部用户曾经评价过的影片,以及对该片的具体评分。对于每一部该用户尚未看过的影片,相应有一列指出其与已观看影片的相近程度。例如:影片《阿凡达》和《人在囧途》之间的相似度评价值为 -0.18。以“评分x”开头的列给出了用户对影片的评价值乘以相似度之后的结果,由于该用户对《阿凡达》的评分是 4.0,所以“人在囧途”的最后一列对应取值为:4.0×-0.18=-0.72。
总计一行给出了每部影片相似度评价值的总计值及其“评分x”列的总计值。为了预测用户对每部影片的评分情况,只要将“评分x”列的总计值除以相似度一列的总计值即可。用户对影片《人在囧途》的评分情况为:-3.517/-0.996=3.531。

通过下面的代码,可以实现上述功能:

function getRecommendedItems($prefs, $itemMatch, $user)
{
	$userRatings = $prefs[$user];
	$scores = array();
	$totalSim = array();

	// 循环遍历由当前用户评分的物品
	foreach ($userRatings as $item => $rating)
	{
		// 循环遍历与当前物品相近的物品
		foreach ($itemMatch[$item] as $item2 => $similarity)
		{
			// 如果该用户已经对当前物品做过评价,则将其忽略
			if (array_key_exists($item2, $userRatings))
			{
				continue;
			}

			// 评价与相似度的加权之和
			$scores[$item2] = isset($scores[$item2]) ? $scores[$item2] : 0;
			$scores[$item2] += $similarity * $rating;

			// 全部相似度之和
			$totalSim[$item2] = isset($totalSim[$item2]) ? $totalSim[$item2] : 0;
			$totalSim[$item2] += $similarity;
		}
	}
	// 将每个合计值除以加权和,求出平均值
	foreach ($scores as $item => $score)
	{
		$rankings[$item] = ($totalSim[$item] != 0) ? $score / $totalSim[$item] : 0;
	}

	// 按从高到低排序并返回评分结果
	arsort($rankings);
	return $rankings;
}

我们可以测试一下这个函数,向其传入以前构造好的相似度数据集,在这里我们为 rock 提供一个新的推荐结果:

$itemsim = calculateSimilarItems($critics);
print_r(getRecommendedItems($critics, $itemsim, 'rock'));

运行结果如下:

Array
(
    [盗梦空间] => 3.6100310668022
    [人在囧途] => 3.531395034186
    [线人] => 2.9609998607243
)

之前文章中得到的推荐相比,《盗梦空间》和《人在囧途》的排列位置有了些许变化,但他们仍然排在《线人》的前面。而且更为重要的是,在调用 getRecommendedItems 函数时,我们不必再为所有其他评论者计算相似度评价值,因为物品相似度数据集已经事先构造好了。

在针对大规模的样本数据集进行推荐时,基于物品进行过滤的方式明显要比基于用户的过滤更快,不过它却有维护物品相似度列表的额外开销。同时,这种方法根据数据集“稀疏”程度上的不同也存在精准度上的差异。对于稀疏数据集,基于物品的过滤方法通常要优于基于用户的过滤方法,而对于密集数据集而言,两者的效果几乎是一样的。

总结2010,展望2011

不得不说时间过得真快。
2010年的一切,都跟做梦一样,每个月都跟做梦一样。2010年又是神奇的一年。

一月那会儿我们大二的学生还必须要学校指定的教室去上自习。
那段时间在玩新浪微博也开始正式关注微博这个东西。但我也同时玩人人、豆瓣以及QQ。于是常常出现这样的情况:有什么想说的话,我得先更新到QQ签名,然后再复制粘贴到其他地方。
后来的一天自习中,我想到与我一样喜欢流连于各个社交网络的朋友一定也不少。我觉得我是一个程序员,我应该要想个办法减少这些机械劳动。于是我发了一条短信给Colin,跟他大概地说了我的想法之后很快得到了鼓励的答复。接下来我就开始做了。

起初我给这个产品制作了一个简单的界面,还找李婉洁帮我画了一个很给力的插图。
但很快我发现我做的那个界面有点儿太丑了,而且我感觉这个产品还是挺酷的,那么它应该有个同样酷酷的用户体验,可怜我写过的JavaScript代码至今加起来可能都不到10行。

于是我找到了Aluan,他是我在大学里的学长,同时也是一名前端工程师。我和Aluan一起给我们的产品取名“微博通”,并买下了weiboto.com这个域名。

整个二月到三月,基本上都在进行微博通的开发。
当时正好是放寒假,那个寒假几乎都没怎么出门。甚至连以前同学的聚会都没怎么参加,直接导致大家都开始抱怨我“不合群”。
我记得在大年三十的晚上,我在外婆家和亲人过完年回到家之后,还打开电脑给微博通添加了一个功能。
那段时间每天工作到很晚,很疯狂,但也充满着乐趣。

付出肯定是能换来回报的,微博通访问量的第一次激增是在我们被腾讯科技报导了之后。
http://tech.qq.com/a/20100302/000370.htm

随着用户量的不断增长,我们的程序暴露出来的问题也慢慢展露出来。
于是在不断的补Bug、加功能中,新的一个学期开始了。

当时,我和Aluan已经开始觉得有点儿力不从心了。于是经Aluan介绍,我们迎来了三名新成员:杨煌、青龙和小黑。至此,微博通团队就正式形成了。

杨煌现在是微博通的主程,他是一个很强悍的程序员,功力非常深厚,执行力也超强。
青龙现在在新浪微博做teamleader,我平时常麻烦他,向他请教过不少技术上的问题。
小黑对新产品有很敏锐的嗅觉,时常会有新的想法,同时也有强大的执行力。
在和他们一起开发微博通的过程中,我收获到了很多技术上的知识和更多的技术之外的东西。

有了新鲜血液的注入,微博通展现出了更强劲的生命力。此时已经开始有一些投资者与我们接触,而我们也开始思考微博通发展的方向。在那一段时间,每天微博通都能收到来自用户的赞扬与建议,同时也因为微博通让我结识了不少业界内的朋友,结识了太多的优秀的人脉。于我而言,开发微博通以来收获的最大的财富,这要算是其中重要的一项。

在五月底,我参加了国家软考(全国计算机技术与软件专业技术资格考试)。本来参加软考是被我写入了2010年年度目标的,但由于那段时间一直在忙碌于微博通,最后只抽出了约莫半个月时间系统地把书看了一遍。5月22日进了考场,考完之后感觉还不错,再然后出来的成绩也还不错。11月顺利拿到了软件设计师证书,完成了我的一个年度目标。

经过与不少有意投资和咨询合作的朋友接触和沟通,在六月微博通正式确立和迈奔灵动建立合作关系。于是我们又进行了一次架构上的大调整,与此同时微博通也开始由一个业余项目,慢慢走上正规化的道路了。

如火一般的七月到八月,我回到了湘潭。
八月我母亲要做一个胆囊切除手术。之前我在网络上查阅了很多资料,了解到这个手术已经发展得比较成熟,成功几率非常大。但那几个日日夜夜我还是无法克制地非常焦虑,以至于失眠。我只能刻意让自己编程到深夜,才能防止我在床上翻来覆去地乱想。
我是那么的害怕母亲会就此离开我,我终于能够体会到以前只能在电视中见到的那种担心亲人生命受到伤害的情感。当母亲在术前跟我说害怕手术出问题的时候,我只能故作坚强地给母亲支持。

手术是在8月18日,幸好,手术很成功。当母亲躺在手术床上被护士推出手术室的那一刹那我心中的喜悦简直是难以言喻!要不是顾虑到医院的特殊环境,我真想对天怒吼一嗓子。

九月回到学校,开始评定奖学金。终于,一年的努力再次换来回报。我完成了又一个年度目标:拿到了学校二等奖学金。同样是在九月,我完成了对《新概念2》第三遍背诵的年度目标,但依然没能做到真正的脱口而出,对此我表示很不满意。

十月Aluan和杨煌代表微博通接受了腾讯网的专访,明显看出Aluan面对镜头紧张了啊,哈哈哈。
http://tech.qq.com/a/20101021/000330.htm

十月底开始准备参加安徽省第一届计算机程序设计竞赛。一直以来,我是很喜欢参加这种算法竞赛的,在这种高压力、高强度下编程能给我们带来的绝不仅仅是技术上的提升。我和朱先明以及杨凯帆组成一支队伍,由于准备的时间比较短,所以那一个月我们每天所做的就是疯狂地在北大OJ上AC各种题目、总结各种题目和算法、看ACM竞赛牛人们的博客和解题报告。

十二月初到合肥参赛,最后我们拿到了比赛的一等奖。
当我们作为唯一一支来自二本学校的队伍,和那些牛B哄哄的一本学校的选手一起领奖的时候,我对自己说,我再一次用行动验证了我的座右铭:每一份私下的努力都会有加倍的回报。

作为给自己一年来的犒劳,十二月我再次到了杭州。一来是散散心,二来是参加由淘宝网主办的D2前端论坛。虽然我并不是一名前端开发者,但我一直对前端开发和有关UED方面的工作抱有一种敬仰之情。借用一句在会场听到的话:前端的工作就是将枯燥的数据用优雅的方法展现出来。在会场还见到了在网上相识一年之久的小爝,他今年入职了淘宝网,本人的相貌果然和我想象中的相差无几哈。

这篇文章我从2010年写到2011年,但它仍然还没有写完。
随后我将附上我为自己设立的2011年十大年度目标,希望朋友们一起来监督我把它们变成现实!

2010年是充满惊喜、刺激和挑战的一年,而2011年将会是更加至关重要的一年。从现在开始立即行动,2011,创造奇迹!

每个人都应该掌握图形表达能力

身处于现代化竞争,我们应该知道如何更有效地传达我们的思想。已经有很多的研究和实践表明,插图或者是图形化的文字有助于给读者或观众留下更深刻的记忆,带来更好的体验。但很遗憾的是目前还是有不少人仍然在创建仅包含文字的内容。

我始终认为每个人都有必要至少掌握一些基本的图形表达常识,这点在我最近的工作和学习中感触尤为深刻。当我们在做presentation的时候,在做各种产品设计、课程设计、程序设计的时候,简洁、美观而有效的图形表达能帮助我们更胜一筹。在某些时候它们的功效甚至超过了口头的语言和书面的文字。

创建具有艺术体验的插图不是那么简单,这点对于广大理工男来说似乎更是如此。于是我们需要借助工具,从石器时代开始人类就擅长于使用各种工具不是吗?如果您正在创建某个Word文档,那么我会推荐您使用SmartArt,自从Office2007以来它就被整合进了Office,使用起来非常方便。但是今天我并不打算详细介绍它。

今天我们要聊的是在Web开发中可以使用到的图表绘制工具,它是由Google提供的图表API(Google Chart API)。

值得一提的是,在这里我无意教您学会Google Chart API详细的使用方法。我所希望的是能够通过传达一些视觉上的效果,让每位朋友都意识到图形表达的重要性,也许就是我们所说的“抛砖引玉”。未来的学习不难,重要的是行动起来。

要使用Google Chart API非常简单,不信的话你可以在浏览器中直接打开下面的URL:

http://chart.apis.google.com/chart?cht=p3&chd=t:40,35,25&chs=460×220&chl=行动|智慧|激情

如果您也充满好奇心的话,那么您可以尝试修改上面URL中的部分参数,与此同时您会感叹:“啊哈,太给力了!”

我们可以把这个URL嵌入到任何一个<img>标签中,如此以来这个由Google Chart API为您创建的图表便以图片的形式成为了你网页中的一部分,就像下面那样。

当然,除了饼状图以外你还有更多选择,例如折线图、Sparkline图、韦恩图,甚至是地图等等。Google也支持您对于图表的自定义,您完全可以按照自己的喜好设定图表的配色、尺寸等信息。

如果您已经决定在您的应用中使用这个工具了,我建议您在阅读完本文后移步Google Chart API的主页获取更详尽的资料。

http://code.google.com/apis/chart/index.html

也许简单的图片尚不能满足您的需求,如果您希望获得更酷,更富有互动性的图表,那么您可以使用Google Visualization API。它作为一段JavaScript代码插入您的页面中,使用起来同样不难,在这里我们不再赘述,大家可以自行体验一番。

最后,祝各位中秋节快乐哈~

利用皮尔逊相关度系数构建一个简单的推荐系统

伴随着Web2.0概念的普及,我们正在广泛地享受推荐系统给我们带来的便利。

现代的电子商务、SNS社区等应用大量地使用了推荐系统。通过推荐系统,人人网帮我们找到多年未见的老友,亚马逊总能知道我们偏好什么样的商品,而豆瓣网更是将算法和产品完美结合的最佳典范之一。

通过大量的用户数据和充满智慧的推荐系统,豆瓣网已经成为了我寻找读物、电影和志趣相投的朋友的不二场所。

最近我阅读了《集体智慧编程》一书,开始接触到一点推荐系统的算法。于是在这里我便把一些我学到的东西分享给大家。

在下面的算法里,我们利用一组如下所示的输入数据,它们是用PHP代码描述的。这组数据保存了7位用户以及他们对若干部电影的评价。所有的评价值都介于1到5之间,这有点像我们常常见到的1至5颗星的评价方式。这种数据组织的方式是很贴近于我们现实的应用的。

$critics = array(
					'arale'		=>	array(
											'盗梦空间'	=>	2.5,
											'阿甘正传'	=>	3.5,
											'线人'	    =>	3.0,
											'阿凡达'		=>	3.5,
											'在云端'		=>	2.5,
											'人在囧途'	=>  3.0),
					'johnson'	=>	array(
											'盗梦空间'	=>	3.0,
											'阿甘正传'	=>	3.5,
											'线人'		=>	1.5,
											'阿凡达'		=>	5.0,
											'人在囧途'	=>	3.0,
											'在云端'		=>	3.5),
					'white'		=>	array(
											'盗梦空间'	=>	2.5,
											'阿甘正传'	=>	3.0,
											'阿凡达'		=>	3.5,
											'人在囧途'	=>	4.0),
					'richard'	=>	array(
											'阿甘正传'	=>	3.5,
											'线人'		=>	3.0,
											'人在囧途'	=>	4.5,
											'阿凡达'		=>	4.0,
											'在云端'		=>	2.5),
					'hillary'	=>	array(
											'盗梦空间'	=>	3.0,
											'阿甘正传'	=>	4.0,
											'线人'		=>	2.0,
											'阿凡达'		=>	3.0,
											'人在囧途'	=>	3.0,
											'在云端'		=>	2.0),
					'colin'		=>	array(
											'盗梦空间'	=>	3.0,
											'阿甘正传'	=>	4.0,
											'人在囧途'	=>	3.0,
											'阿凡达'		=>	5.0,
											'在云端'		=>	3.5),
					'rock'		=>	array(
											'阿甘正传'	=>	4.5,
											'在云端'		=>	1.0,
											'阿凡达'		=>	4.0));

在推荐系统算法的实现中,我们要用到皮尔逊相关度系数这一方法来利用已有的数据计算两位用户或者是两件产品之间的相关程度。皮尔逊相关度系数是一个介于1到-1之间的值,其中,1表示两个变量完全正相关,0表示无关而-1则表示完全负相关。下面我们给出皮尔逊相关度系数的计算公式。有关皮尔逊相关度系数更详细的数学原理,大家可以Google到很多资料。

Pearson

用PHP代码可以很容易地描述出皮尔逊系数的实现。

function getPearson($prefs, $person1, $person2)
{
	if (!is_array($prefs)) {
		return false;
	}

	// 得到双方都评价过的物品列表
	$similar = array();
	foreach ($prefs[$person1] as $item => $value)
	{
		if (array_key_exists($item, $prefs[$person2]))
		{
			$similar[$item] = 1;
		}
	}

	// 计算列表元素的个数
	$nums = count($similar);
	if ($nums <= 0) {
		return 0;
	}

	// 对所有的偏好求和
	$sum1 = getSum($similar, $prefs[$person1]);
	$sum2 = getSum($similar, $prefs[$person2]);

	// 求平方和
	$sum1Sq = getSum($similar, $prefs[$person1], 2);
	$sum2Sq = getSum($similar, $prefs[$person2], 2);

	// 求乘积之和
	$pSum = getSum($similar, $prefs[$person1], 1, $prefs[$person2]);

	// 计算皮尔逊评价值
	$numerator = $pSum - ($sum1 * $sum2 / $nums); // 分子
	$denominator = sqrt(($sum1Sq - pow($sum1, 2) / $nums) * ($sum2Sq - pow($sum2, 2) / $nums)); // 分母
	if ($denominator == 0) {
		return 0;
	}
	return $numerator / $denominator;
}

其中用到的getSum()函数描述如下。

function getSum($similar, $person, $power = 1, $person2 = null)
{
	if (!is_array($similar) || !is_array($person) || $power < 0)
	{
		return false;
	}
	$sum = 0;
	foreach ($similar as $item => $value)
	{
		if (is_array($person2))
		{
			$sum += $person[$item] * $person2[$item];
		}
		else
		{
			$sum += pow($person[$item], $power);
		}
	}
	return $sum;
}

如此以来,我们便可以使用皮尔逊相关度系数,计算出与我趣味相投的朋友。在这里我们再构建一个topMatches()函数,我们向它传入之前那组数据,然后指定一位用户。topMatches()函数能为我们逐个计算其余用户与该用户之间的相关度,并保存到一个数组中返回。

function topMatches($prefs, $person)
{
	$scores = array();
	foreach ($prefs as $other => $subArry)
	{
		if ($other != $person)
		{
			$scores[$other] = getPearson($prefs, $person, $other);
		}
	}
	arsort($scores);
	return $scores;
}

如果我们写下如下这样一段代码的话,我们要找到跟rock最相近的用户:

print_r(topMatches($critics, 'rock'));

就可以得到如下的输出:

Array
(
    [arale] => 0.99124070716193
    [hillary] => 0.9244734516419
    [richard] => 0.89340514744156
    [colin] => 0.66284898035987
    [johnson] => 0.38124642583151
    [white] => -1
)

数组每个项的值就是该用户和rock之间的相似度。
这就有点类似我们在SNS社区或者是微博系统中常见的“你可能感兴趣的人”这一功能。
当然,如果是电子商务网站的话,可能更希望向用户推荐用户感兴趣的商品而不是拥有同样喜好的其他用户。

那么我们可以实现下面这样一个函数。

function getRecommendations($prefs, $person)
{
	$totals = array();
	$simSums = array();

	foreach ($prefs as $other => $subArry)
	{
		// 不要和自己做比较
		if ($other == $person)
		{
			continue;
		}
		$sim = getPearson($prefs, $person, $other);

		// 忽略评价值为零或小于零的情况
		if ($sim < 0)
		{
			continue;
		}
		foreach ($prefs[$other] as $item => $rating)
		{
			// 只对自己还未曾看过的影片进行评价
			if (!array_key_exists($item, $prefs[$person]) || $prefs[$person][$item] == 0)
			{
				// 相似度 * 评价值;
				$totals[$item] = isset($totals[$item]) ? $totals[$item] : 0;
				$totals[$item] += $rating * $sim;

				// 相似度之和
				$simSums[$item] = isset($simSums[$item]) ? $simSums[$item] : 0;
				$simSums[$item] += $sim;
			}
		}
	}

	// 建立一个归一化的列表
	$rankings = array();
	foreach ($totals as $item => $total)
	{
		$rankings[$item] = $total / $simSums[$item];
	}

	arsort($rankings);
	return $rankings;
}

同样,我们写下这么一条语句,我们要向rock推荐电影:

print_r(getRecommendations($critics, 'rock'));

我们可以得到下面这样的输出:

Array
(
    [人在囧途] => 3.3477895267131
    [盗梦空间] => 2.8325499182642
    [线人] => 2.5309807037656
)

大家肯定已经猜到了那一串串数字就是程序计算得到的rock对该电影可能的喜好程度。
这样,一个简单的推荐系统就构建完成了。

但是,富有经验的程序员马上会提出质疑,咱们这个程序效率太低下了!
这种方法对于一个小型的应用完全是没有问题的,但如果是类似于豆瓣这种动辄几千万用户的应用来说,将一个用户和其他所有用户进行比较,然后再对每位用户评分过的商品进行比较,你会发现我们的系统已经不给力了。

在下一篇文章中,我们来讨论另外一种解决方案,在拥有大量数据的情况下,那种方法可以表现得更好。

数独游戏

最近喜欢上了“数独(Sudoku)”游戏。

每天的课间或者午餐后我都会乐此不疲地驰骋于这小小的九宫格中。在我看来,“数独”游戏不仅仅是一种智力的博弈,更是对耐力的挑战。

在游戏之余,我想到用深度优先搜索的话,很容易在计算机上写出一个解决“数独”游戏的小程序。于是便有了下面的代码。

输入数据的格式为:

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

其中的0代表代填的空格子。

#include <iostream>
#include <fstream>
using namespace std;

bool flag = false;
int sudoku[9][9];

bool isAvailable(int val, int x, int y)
{
	int i, j;
	// 检查行
	for(i = 0; i < 9; i++)
		if(sudoku[x][i] == val)
			return false;

	// 检查列
	for(i = 0; i < 9; i++)
		if(sudoku[i][y] == val)
			return false;

	// 检查小方格
	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
			if(sudoku[x / 3 * 3 + i][y / 3 * 3 + j] == val)
				return false;
	// 符合要求
	return true;
}

void dfsSearch(int x, int y)
{
	if(flag)
		return;

	// 全部符合
	if(x > 8)
	{
		flag = true;
		return;
	}

	// 本行结束,开始下一行
	if(y > 8)
		dfsSearch(x + 1, 0);

	if(sudoku[x][y] != 0)
		dfsSearch(x, y + 1); // 不是空格,则考虑下一个格子
	else
	{
		// 是空格,则枚举数字1~9测试是否满足条件
		for(int i = 1; i <= 9; i++)
		{
			if(isAvailable(i, x, y))
			{
				sudoku[x][y] = i;
				dfsSearch(x, y + 1);
				if(!flag)
					sudoku[x][y] = 0; // 构造数独不成功,则还原当前格
			} // isAvailable IF

		} // i FOR
	}
} // dfsSearch FUNCTION

int main()
{
	// ifstream cin("D:\\input.txt");
	int i, j;
	char tmp;
	memset(sudoku, 0, sizeof(sudoku));

	// 读入数据
	for(i = 0; i < 9; i++)
	{
		for(int j = 0; j < 9; j++)
		{
			cin >> tmp;
			sudoku[i][j] = tmp - '0';
		}
	}

	dfsSearch(0, 0);

	// 输出数据
	for(i = 1; i <= 9; i++)
	{
		for( j = 1; j <= 9; j++)
		{
			cout << sudoku[i - 1][j - 1] << " ";
			if(j % 3 == 0)
				cout << " ";
		}
		cout << endl;
		if(i % 3 == 0)
			cout << endl;
	}

	return 0;
}

最后,推荐一个可以在线玩数独的网站给大家。

http://www.websudoku.com/

有兴趣的朋友们去挑战一下吧~