Xiaojun Ren  •  Comment

背景

KNN，全称K-nearest-neighbour，是机器学习中最简单的一个分类算法，它的原理是通过对样本数据的学习，对于给定的新的数据，找出与其距离最近的K个样本数据，根据这K个最近样本数据的类别，来确定这个给定数据的类别。

Coolshell上有对这个算法的讲解，我的同事邱俊涛也写了一篇关于KNN算法python实现的文章。本文讲解一个KNN算法的ruby实现。

输入

程序输入格式如下：

x0,x1,x2,…xn|v0
y0,y1,y2,…yn|v1
z0,z1,z2,…zn|v2

每行为一个数据样本，以第一行为例，x0,x1…xn为一个向量，v0为该数据的类别。

学习

从给定文件加载样本数据:

def train file_path
  @samples = from_file(file_path)
end

@sample的格式如下：

[
	{:vector => [x0, x1, x2, …xn], :value => v0},
	{:vector => [y0, y1, y2, …yn], :value => v1},
	…
	{:vector => [z0, z1, z2, …zn], :value => vn},
]

分类

对于给定的数据，要判断其属于样本数据中的哪一类，需解决如下几个问题：

  1. 计算给定数据和样本数据之间的距离
  2. 找出与给定数据距离最小的K个样本数据
  3. 从这K个样本数据中找出样本多的那个分类，即为给定数据的分类。
1. 计算距离

给定两个向量[x0, x1,…xn]，[y0, y1,...yn]计算两个向量之间的距离如下：

(x0 - y0)^2 + (x1 - y1)^2 + … + (xn - yn)^2

因此，对于给定的两个向量a，b，其距离计算逻辑如下：

#a and b are two vectors
def distance_between a, b
  a.zip(b).map {|x| x[0] - x[1]}.inject(0){|sum, x| sum += x*x}
end
2. 找出与给定数据距离最小的K个样本数据

可以采用计算给定数据与所有样本数据的距离，然后采用最大堆来找出__top k__个样本数据。

def nearest_neighbours candidate, k
  heap = MaxHeap.new
  @samples.each do |sample|
    distance = distance_between(sample[:vector], candidate)
    heap.insert Node.new(distance, sample)
  end
  heap.take_top(k).compact.map(&:sample)
end
3. 从这K个样本数据中找出样本多的那个分类，即为给定数据的分类。

对得到的样本根据其类别进行分组，组内元素多的那个类别，即为该给定数据的分类

def value_with_max_vote xs
  value_with_votes = xs.group_by{|x| x[:value]}.map{|value, group| {:value => value, :votes => group.length}}
  value_with_votes.max_by{|x| x[:votes] }[:value]
end

综合上面的几个小任务，我们得到KNN分类算法的实现：

def categorize candidate, k
  neighbours = nearest_neighbours_for candidate, k
  value_with_max_vote neighbours
end

代码的完整版本可以在这里找到。

Xiaojun Ren  •  Comment

Note: 本文中的程序来自Martin Ordersky在www.coursea.org上所开设课程中的样例代码，文章主要目的是讲述我对此类问题解法及scala lazy evluation的理解。

问题描述

给你一个容量为9升的杯子和一个容量为4升的杯子，水不限使用，要求精确得到6升水。这就是“倒水问题”。我这里会讲述一个试用scala穷举法实现的一个例子。

建模

首先我们对这个问题进行建模。这个问题可以泛化为如下形式：

两个容量固定的杯子，可选的动作有：

  • 加满
  • 倒空
  • 从一个杯子倒入另一个杯子

初始状态为两个杯子都空，结束状态为其中一个杯子中的水量为所期望的结果。 从上面的描述中我们可以得到如下几个概念状态，动作，路径。

状态用于表述各个杯子中当前的水量，动作用来改变各个杯子中水量，路径用于表示到达某一状态的动作序列。

状态

我们可以用一个Vector[Int]来表述杯子的状态，下标为杯子编号，元素值为当前杯子中的水量，另外，我们还需要一个Vector[Int]表示杯子的容量，下标为杯子编号，元素值为杯子的容量。于是我们得到如下代码：

class Pouring(capacity: Vector[Int]) {
  //States
  val initialState = capacity map (x => 0)
}

capacity为杯子容量， intialState为问题初始状态。

动作

由上可知，解决这个问题可以有三种动作, Empty, Fill, Pour，每个动作都会导致状态发生变化，于是我们得到如下代码：

//Moves
trait Move {
  def change(state: Vector[Int]): Vector[Int] 
}
case class Empty(glass: Int) extends Move {
  def change(state: Vector[Int]): Vector[Int] = state updated (glass, 0)
}
case class Fill(glass: Int) extends Move {
    def change(state: Vector[Int]): Vector[Int] = state updated (glass, capacity(glass))
}
case class Pour(from: Int, to: Int) extends Move {
  def change(state: Vector[Int]): Vector[Int] = {
      val amount = state(from) min (capacity(to) - state(to))
      state updated (from, state(from) - amount) updated (to, state(to) + amount)
  }
}

注意因为要考虑杯子的容量和杯子中剩余的水量，Pour中的change方法稍微复杂了些。

路径

接下来到了最重要的路径部分了，路径是到达某一状态的动作序列，我们需要一个List[Move]表述动作序列，一个Vector[Int]表述结束状态。 还需要一个extend方法来扩展当前的动作序列，即在当前路径上，应用一个动作（Fill, Empty, Pour），得到一个新的路径。于是我们得到如下代码：

//Paths
class Path(history: List[Move], val endState: Vector[Int]) {
  def extend(move: Move) = new Path(move :: history, move change endState)
  override def toString = (history.reverse mkString " ") + " -->" + endState
}

算法

这里我们要采用的是穷举法：

穷举从初始状态出发所有可能的动作，以及可能达到的状态，再穷举从这些状态出发所有可能的动作以及可能达到的状态，如此反复，直到找到一个可能达到的状态满足期望，则到达这个状态所经历的所有动作组成的路径即为问题的解。

首先我们来穷举给定一组杯子可能的动作：

val glasses = 0 until capacity.length
val moves =
  (for (g <- glasses) yield Empty(g)) ++
  (for (g <- glasses) yield Fill(g)) ++
  (for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))

其次，在不进行任何动作时，动作列表为空，所达到的状态为初始状态，则：

val initialPath = new Path(List(), initialState)

接下来到最关键的部分了，穷举从初始状态出发的所有可能扩展出来的路径及其所达到的状态，由于从任何状态开始穷举，都会得到一个一组路径，而不是一个，于是我们首先定义一个从给定一组路径，穷举其可能扩展出来的的路径的方法：

def from(paths: Set[Path], explored: Set[Vector[Int]]): Stream[Set[Path]] = {
  if (paths.isEmpty) {
    Stream.empty
  } else {
    val more = for {
      path <- paths
      next <- moves map path.extend
      if !(explored contains next.endState)
    } yield next
    paths #:: from(more, explored ++ (more.map(_.endState)))
  }
}

paths为此次穷举的初始路径集合, explored用于记录已经穷举过的状态，以避免找出多条达到相同状态的路径，此方法通过穷举初始路径集合，在各个路径上扩展所有的动作，去掉那些达到状态已经被穷举过的路径，得到一组新的路径。

那么，从初始路径出发，其可能扩展出来的路径极其可能达到的状态如下：

val pathSets = from(Set(initialPath), Set(initialState))

对于给定的目标水量，遍历上述穷举结果路径找出endState包含目标水量的路径，如下：

  def solutions(target: Int): Stream[Path] = {
    for {
      pathSet <- pathSets
      path <- pathSet
      if path.endState contains target
    } yield path
  }

总结

我们知道，穷举是一个无穷无尽的过程，上面的程序是如何运行的呢？其实是scala中强大的lazy load发挥了作用。我们再来看from方法的返回值类型，是Stream[Set[Path]], Stream 用于表述元素序列，它的一个重要特点是，只有需要使用到其中的某个元素时，程序才会去计算这个元素。于是，在程序运行时，scala并不会一下子把所有可能的路径都计算出来。对于solutions方法，也是一样。因此，scala只有在从solutions的计算结果中获取满足条件的路径时，pathSet才会穷举可能的路径，并且在找到满足条件的路径后，计算会立即结束，不会再列举其余的可能。

Xiaojun Ren  •  Comment

注：感谢我的同事新宇想出的这个点子，没有他的这个点子，也就没有这篇文章。

引子

在开发过程中，你有没有碰到这样的场景：
“功能完成，该提交代码了。”
“Hold on，得先跑下local build。”，你的pair叫起来了。
“啊，是啊”，你恍然大悟。敲下bundle exec rake dev。
“local build一般至少得运行十分钟吧， 抽空看看邮件吧”。
5分钟过去了，你回过神来，看看测试跑得怎么样了。
啊，测试在第二分钟时就悄无声息地废了。白白浪费了3分钟时间。。。。
“要是测试在废掉的时候能够提醒一下我就好了。”你心想。

做为一名自诩动手能力很强的程序员，有什么理由不自己试一试呢？

要达到上述目标，我们需要解决以下几个问题：

  1. 如何判断local build是否成功？
  2. 如何播放声音提示？

我们首先来看第一个问题，bundle exec rake dev实际上是在执行一个shell命令，如何判断一个shell命令是否执行成功， google之，得知可以通过退出状态码(Exit Code)进行判断，非零退出状态码表示shell脚本执行失败。于是我们创建一个脚本run_test.sh,脚本内容如下：

	#!/bin/bash -e
	bundle exec rake dev
	if [ $? == 0 ]; then
		#TODO 播放成功声音
	else
		#TODO 播放失败声音
	fi

接下来我们来看第二个问题，Mac OSX自带了一个命令行工具say,可以把单词转换为语音输出，例如执行say "Hello World"，你就会听到Mac 说话了。 于是，我们的脚本就变成了：

	#!/bin/bash -e
	bundle exec rake dev
	if [ $? == 0 ]; then
		say "Good, build passed"
	else
		say "Boom, build failed"
	fi

俩问题都解决了，该伸个懒腰休息休息了吧。“Hold on”， 你的pair又说话了，“难道这么好用的功能，你只想用它来执行local build吗？能否让所有的rake task失败都有声音提示呢？” 。真是个难缠的pair。

不管怎样，第三个问题来了，如何使run_test.sh变得更加通用？ 把要被执行的命令做为参数传给这段脚本，然后在脚本中执行，恩，是个不错的选择。于是脚本变成如下的样子：

	#!/bin/bash -e
	$@
	if [ $? == 0 ]; then
		say "Good, build passed"
	else
		say "Boom, build failed"
	fi

执行sh ./run_test.sh bundle exec rake dev，当bundle exec rake dev执行成功时，你就可以听到悦耳的声音提示了。

还能再改进吗？每次都要敲这么长的命令，好烦啊。加个alias吧，编辑/.rvmrc，加入如下alias：

	alias be="sh ./script/run_test.sh bundle exec"

下次只要执行be rake dev，你就可以可以放心地看邮件了，等着听声音提示吧。

后记

mac也提供了另外一个命令行工具afplay，可以用来播放音频文件，我们选用了卡巴斯基那个惨绝人寰的杀猪声做为build失败提示音，够惊悚吧。下面是我的项目中这个脚本的最终版本。

	#!/bin/bash -e
	$@
	if [ $? == 0 ]; then
	  afplay fixture/success.wav
	else
	  afplay fixture/fail.wav
	fi

想说的话

上面的故事是从今天我和同事pair的场景里抽象提炼出来的，从提出点子到最后实现也就用来个把小时，代码量很小，难度也不大，然而带给每个team member的好处却是显而易见的。让平日里的工作变得有趣的正是这些点子，以及实现它的过程，更大的乐趣是把它分享给更多的人。我们已经分享了，你呢？

Xiaojun Ren  •  Comment

本文发表于infoq。

什么是BDD？

BDD在wikipedia上定义如下：

BDD是第二代的、由外及内的、基于拉(pull)的、多方利益相关者的(stakeholder)、多种可扩展的、高自动化的敏捷方法。它描述了一个交互循环，可以具有带有良好定义的输出（即工作中交付的结果）：已测试过的软件。

简单一点地说，BDD，即行为驱动开发，是通过与产品经理沟通需求，定义出满足这些需求的软件需具备的行为(Behaviour)，再以这些行为为驱动(Driven)，编写产品代码来实现这些行为。(Development)。BDD的出现，是为了解决测试驱动开发中常遇到的问题，比如：从哪里开始测试，应该测试什么，不应该测试什么，等等。想了解更多可参见Dan North的introducing BDD。

BDD实践所面临的问题

进行BDD实践首先要解决如下几个问题：

  • 如何实现一个能够描述系统行为（业务价值）、非技术人员可读的测试？
  • 如何让这个测试变得可执行？

业界对这些问题已经有了答案，JBehave, Cucumber，Concordian等BDD框架的出现，解决了这个问题。 这些BDD框架各自提供了一套DSL（Domain-Specific-Language），开发人员可以使用DSL描述业务需求，例如，

前置条件： 用户A账户余额1000元 用户B账户余额200元
场景：
	用户A登录系统
	向用户B转账500元
	用户A账户余额应为500元
	用户B庄户余额应为700元

同时，这些框架都依赖于Webdriver（如selenium-webdriver，watir-webdriver），BDD框架通过webdriver调用浏览器的接口，模拟用户输入，读取浏览器页面上显示的内容用于验证。

下面我们通过一个完整的例子来看看如何使用这些工具进行BDD实践的。

Cucumber与业务价值

在Behaviour Driven Development中，第一步就是把需求细分为多个任务，拿最常见的用户登录功能为例，可以划分为以下几个任务：

  • 用户名密码匹配，登录成功
  • 用户名或密码不匹配，登录失败

BDD强调“每一个测试需要体现出业务价值”，因此，可以把上述两个任务实现为两个场景：

Feature: User login
Background: There is a user with the following login detail:
	|    email      | password|
	| my@example.com|   test  |
	
Scenario: Login succeed
Given the user login with the following detail:
	|    email      | password|
	| my@example.com|   test  |
Then the user should login succeed

Scenario: Login failed
Given the user login with the following detail:
	|    email      |     password     |
	| my@example.com|   wrongpassword  |
Then the user should login failed 实际上，上面的这段代码就是使用cucumber的DSL描述的测试场景，几乎就是遵循了一定格式的英语，即使看不懂代码的产品经理、业务分析师也能够通过此文档和开发人员顺畅地交流。用Cucumber把一个需求的不同场景描述出来，也是从不同角度阐述了这个需求的业务价值。__Cucumber的目标就是书写可执行的，能够表述业务价值文档。__ 与之类似的框架还有Concordian，JBehave等。

紧接而来的问题是：如何让文档执行起来？Cucumber提供了把业务逻辑转换为可执行代码的机制——”step definition”。请看下面的例子：

Given /^the user login with the following detail:$/ do |detail|
	#omitting code…
end 这个step definition会匹配下面这个step：

Given the user login with the following detail:
	|    email      | password|
	| my@example.com|   test  |

当Cucumber feature被执行的时候，这个step definition中的代码会被执行。那么，接下来的问题就是：如何象真实用户那样打开浏览器，输入用户名密码，点击提交按钮，验证登录是否成功。这时候，该Webdriver出场了。

Web Driver与页面交互

先来看下面一段代码：

require 'watir-webdriver'
b = Watir::Browser.new
b.goto 'http://localhost:3000/login'
b.text_field(:id => 'email').set 'my@example.com'
b.text_field(:id => 'password').set 'password'
b.button(:name => 'submit').click
b.text.include? 'Login succeed'

这段代码会做如下事情：

1. 打开浏览器，访问h地址 “http://localhost:3000/login”
2. 在邮件输入框输入 “my@example.com”
3. 在密码输入框输入 “password”
4. 点击 提交按钮
5. 验证结果页面是否包含“Login succeed”字样 这就是webdriver所提供的能力，web driver通过调用浏览器的支持自动化的API，模拟真实用户在浏览器上的操作。把这段代码被放在上面的step definition中，当cucumber测试运行的时候，这段代码就会运行，完成登录操作。这个例子是使用[Watir webdriver](http://watirwebdriver.com/)实现的，另外一个比较流行的webdriver是[Selenium webdriver](http://seleniumhq.org/projects/webdriver/)。

不同Webdriver提供的API也不尽相同，而Capybara则致力于封装多种web driver之间的差异。同时，Capybara提供了一些更聪明的特性，例如，等待页面加载完成再执行下一个步骤，这对于开发人员来说非常重要，否则，就需要自己判断写代码页面加载完成，代码丑陋，测试脆弱，那将是开发人员的噩梦。

Page Model与页面建模

至此，一个可执行的描述用户登录的测试用例就编写完毕，当我们执行这个测试用例时，就会看到：

浏览器打开
访问登录页面
在页面上输入用户名
密码
点击登录按钮
登录成功
测试通过 上述所有操作都是自动完成，一切都很完美，但前提是只在这样的一个小示例里。在一个实际的项目里，我们经常会遇到下面几个问题：

1.当越来越多的与页面交互的代码出现在step definition中时，页面交互，结果验证的代码混杂在一起，代码的可读性急剧下降。
2.因为webdriver与浏览器交互时依赖于页面元素的id、name等属性，对页面元素的任何小的修改都可能会导致测试失败。
3.在多个step definition与同一个页面交互时，可能会有冗余代码。

而page model的出现就是为了解决上述问题，通过对页面的属性，交互动作进行抽象，封装以达到功能重用，隔离变化的目的。请看下面的例子：

Page model定义
class PageWithLogin
	def url
		#omitting code…
	end
	
	def login email, password
		#omitting code…
	end
end

class PageWithLoginResult
	def login_succeed?
		#omitting code…
	end
end
Step定义
Given /^the user login with the following detail:$/ do |detail|
	on_page_with :login do |page|
		visit page.url		
		page.login(detail["email"], detail["password"]) 
	end
end

Given /^the user should login succeed$/ do |detail|
	on_page_with :login_result do |page|
		page.login_succeed?.should == true
	end
end

如上，把login，login_succeed?功能封装到PageWithLogin, PageWithLoginResult这两个page model中，当”登录页面”，“登录成功页面”的页面结构发生变化时，只需要修改page model中的实现即可，step 定义无需任何变化。关于page model，我的同事徐昊曾经专门写过一篇文章。

结论

BDD框架通过提供DSL，帮助业务人员，测试人员，开发人员定义需求的验收标准，共同得到一个明确的需求完成的定义。通过和webdriver集成，使这个验收标准变得可执行，大大减少了手工验证的压力，当软件通过了这个验收标准，则意味着这个需求已经开发完成。

注解与参考

  1. The truth about BDD Robert C Marting
  2. introducting BDD Dan North
  3. BDD on Wikipedia

感谢张凯峰对本文的审校。

Xiaojun Ren

Character encoding

ASCII

  • encoding in 7-bit.
  • 32 -> 127 representing characters.
  • 0 -> 31 representing control characters.
  • 128 -> 255 was called OEM characters, many company has their own idea about how to use these charaters.

ANSI:

  • lower 127 characters is same with ASCII.
  • higher 127 characters were divided into different “code pages”

Unicode:

  • Code point: In Unicode, a letter maps to something called a code point which is still just a theoretical concept.
  • Encoding: Unicode Byte Order Mark: indicating encoding order is ‘high-endian’ or ‘low-endian’

UTF8: Every code point from 0-127 is stored in a single byte. Only code points 128 and above are stored using 2, 3, in fact, up to 6 bytes.

The Most Important thing:

  It does not make sense to have a string without knowing what encoding it uses.