[7.14实习笔记] Maven入门

今天主要学习了Maven。整理记录一下。

Maven 是 Java 项目的一个构建工具,阿里内部使用Maven 2.2.1作为项目构建工具。

【Tips】关于Maven和后面WebX的学习,建议参照WebX提供的样例petstore进行对照理解。petstore的Github仓库地址为:https://github.com/webx/citrus-sample/tree/master/petstore

安装配置

安装

安装过程在上一篇博客中已经写过了:

[7.11实习笔记] 环境搭建 JDK+IDEA+MAVEN+JBOSS+HSF+SVN

配置

首先,我们要介绍一下仓库的概念。

在不用Maven的时候,比如说以前我们用Ant构建项目,在项目目录下,往往会看到一个名为/lib的子目录,那里存放着各类第三方依赖jar文件,如log4j.jar,junit.jar等等。每建立一个项目,你都需要建立这样的一个/lib目录,然后复制一对jar文件,这是很明显的重复。重复永远是噩梦的起点,多个项目不共用相同的jar文件,不仅会造成磁盘资源的浪费,也使得版本的一致性管理变得困难。此外,如果你使用版本管理工具,如SVN,你需要将大量的jar文件提交到代码库里,可是版本管理工具在处理二进制文件方面并不出色。

Maven仓库就是放置所有JAR文件(WAR,ZIP,POM等等)的地方,所有Maven项目可以从同一个Maven仓库中获取自己所需要的依赖JAR,这节省了磁盘资源。此外,由于Maven仓库中所有的JAR都有其自己的坐标(坐标的概念将在下面提到),该坐标告诉Maven它的组ID,构件ID,版本,打包方式等等,因此Maven项目可以方便的进行依赖版本管理。你也不再需要提交JAR文件到SCM仓库中,你可以建立一个组织层次的Maven仓库,供所有成员使用。

简言之,Maven仓库能帮助我们管理构件(主要是JAR)。

Maven的仓库分为本地仓库远程仓库。运行Maven的时候,Maven所需要的任何构件都是直接从本地仓库获取的。如果本地仓库没有,它会首先尝试从远程仓库下载构件至本地仓库,然后再使用本地仓库的构件。

关于仓库的 详细介绍,可参见:http://juvenshun.iteye.com/blog/359256

为什么要谈到这个概念呢?因为它是Maven的配置文件settings.xml的很重要的一部分。这个配置文件一般存在在两个地方,分别是用户目录下的.m2目录里,以及maven安装目录的conf目录中。

打开这个配置文件,我们主要关注下面几项内容:

<localrepository>:这一项指定了本地仓库的存储目录。

<mirrors>:这一项指定了远程仓库的镜像地址。如果你的地理位置附近有一个速度更快的central镜像,或者你想覆盖central仓库配置,或者你想为所有POM使用唯一的一个远程仓库(这个远程仓库代理的所有必要的其它仓库),你可以使用这项配置。

<profiles>:profile可以让我们定义一系列的配置信息,然后指定其激活条件。这样我们就可以定义多个profile,然后每个profile对应不同的激活条件和配置信息,从而达到不同环境使用不同配置信息的效果。比如说,我们可以通过profile定义在jdk1.5以上使用一套配置信息,在jdk1.5以下使用另外一套配置信息;或者有时候我们可以通过操作系统的不同来使用不同的配置信息,比如windows下是一套信息,linux下又是另外一套信息,等等。关于profile的具体使用可参见:http://haohaoxuexi.iteye.com/blog/1900568

IntelliJ IDEA中配置Maven

在IntelliJ IDEA中使用Maven,可以在File→Settings→Project Settings→Maven中进行设置。

其中可以在Runner项下设置vm options: -Xmx512m -XX:MaxPermSize=1024m

项目结构

Maven的项目使用一个统一的约定的标准目录结构(Standard Directory Layout)。如下所示:

my-app
|-- pom.xml
`-- src
    |-- main
    |   `-- java
    |       `-- com
    |           `-- mycompany
    |               `-- app
    |                   `-- App.java
    `-- test
        `-- java
            `-- com
                `-- mycompany
                    `-- app
                        `-- AppTest.java

这是一个典型的项目目录结构。

目录结构最顶层,是一个POM文件pom.xml(关于POM会在下面详细讲)。另外也可以有README.txt,LICENSE.txt等说明性文本。

子目录只有两种,src和target。其中target主要是存储build出来的东西的,src是存储所有的源代码的。它可以有这几种子目录:main(存放主要的构建代码);test(存放单元测试代码和资源),site,等。

在存储源代码的目录下(main,test等),有java(存放java代码),webapp(存放网络应用程序代码)和resource(存放资源)等目录。

src/main/java 应用程序/库的源代码
src/main/resources 应用程序/库的资源
src/main/filters 资源过滤文件
src/main/config 配置文件
src/main/scripts 应用程序/库的脚本
src/main/webapp 网络应用程序源代码
src/test/java 测试源代码
src/test/resources 测试资源
src/test/filters 测试资源过滤文件
src/it 集成测试(主要用于插件)
src/assembly 装配说明
src/site 站点
LICENSE.txt 项目许可协议
NOTICE.txt 项目所依赖的库所要求的说明和权限
README.txt 项目自述文件

POM

现在进入了Maven很重要的一个概念:POM(Project Object Model)。POM是Maven的核心,它以XML格式描述了所有与项目有关的信息。

首先介绍一个概念:坐标

坐标是指项目的唯一标识,以 GAV(groupId,artifactId 和 version)区分,这里我们可以将 groupId 理解为某某公司的 xxx 组或者产品线,开发了某一个项目,对应的版本为 XXX。这里 groupId 包含公司和内部组(或产品线)的信息,如 org.apache.commons,表示 Apache
软件组织下的 Java Commponents 产品线;ArtifactId 则表示项目的名称,如 commons-io,表示项目名称,Version 则表示某一 Artifact 的版本,如 1.3.2,1.3.3-SNAPSHOT 等。

当我们打开一个POM文件,首先看到的是一段描述我们正在建立的artifact信息:

[xml]
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
<modelVersion>4.0.0</modelVersion>
[/xml]

这是强制性的开端部分。接下来是一组坐标。描述了当前项目的groupId, artifactId, version和name。

下面是<properties>。我们可以把properties理解为一组自定义的变量。我们可以在下面定义的依赖中使用这些变量,这样未来在我们需要升级包版本等场景时,可以通过修改变量的值来方便的实现。大家可以参照petstore的pom.xml文件来理解。

而后是依赖管理的部分。

[xml]
<dependencies>
<dependency>
<groupId>jdbm</groupId>
<artifactId>jdbm</artifactId>
<version>1.0</version>
</dependency>
[/xml]

这是一个获取jdbm的简单依赖。默认情况下,Maven通过访问http://www.ibibio.ort/maven2/来获得依赖,如果你查看jdbm/jdbm/1.0/目录,就会发现jdbm-1.0.jar文件,Maven将恢复它;以及一个简短的jdbm pom.xml文件,它列举artifact本身拥有的任何依赖。你可以手动浏览ibibio贮藏库或使用MVN Registry这样的网站来搜索贮藏库。

下一个要讨论的依赖是dwr,但你在ibibio贮藏库中找不到它。你必须将它安装到我们自己的本地贮藏库中。

[xml]
<dependency>
<groupId>dwr</groupId>
<artifactId>dwr</artifactId>
<version>2.0M3</version>
</dependency>
[/xml]

下一个依赖为Java Servlet API。在ibibio库中可以找到它,但我们只有在建立项目的时候才需要它;因为当我们配置一台网络服务器时,servlet API已经存在。

[xml]
<dependency>
<groupId>javax.servlet</groupId>
<artifactId>servlet-api</artifactId>
<version>2.4-20040521</version>
<scope>provided</scope>
</dependency>
[/xml]

scope说明何时需要这个artifact,因此“provided”说明artifact由运行时间环境提供。另一个scope类型为“test”,它说明只有在测试时需要artifact。例如,我们这样包括Junit:

[xml]
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>3.8.1</version>
<scope>test</scope>
</dependency>
</dependencies>
[/xml]

那么,我们如果想引入一个依赖,应该怎么写这个dependency呢?其实我们可以通过远程仓库来搜索每个构建对应的XML描述。

常用的搜索页面有:maven.oschina.net,以及search.maven.org。我们在其中搜索一个构建,便可以得到它对应的XML描述。

现在,POM还剩最后一块内容:插件。

[xml]
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>2.0</version>
<configuration>
<source>1.5</source>
<target>1.5</target>
</configuration>
</plugin>
[/xml]

Maven本质上是一个插件框架,它的核心并不执行任何具体的构建任务,所有这些任务都交给插件来完成,例如编译源代码是由maven-compiler-plugin完成的。进一步说,每个任务对应了一个插件目标(goal),每个插件会有一个或者多个目标,例如maven-compiler-plugin的compile目标用来编译位于src/main/java/目录下的主源码,testCompile目标用来编译位于src/test/java/目录下的测试源码。

生命周期

Maven强大的一个重要的原因是它有一个十分完善的生命周期模型(lifecycle),这个生命周期可以从两方面来理解,第一,顾名思义,运行Maven的每个步骤都由它来定义的,这种预定义的默认行为使得我们使用Maven变得简单,相比而言,Ant的每个步骤都要你手工去定义。第二,这个模型是一种标准,在不同的项目中,使用Maven的接口是一样的,这样就不用去仔细理解每个项目的构建了,一般情况下,mvn clean install 这样的命令是通用的。

Maven有三套相互独立的生命周期,请注意这里说的是“三套”,而且“相互独立”,初学者容易将Maven的生命周期看成一个整体,其实不然。这三套生命周期分别是:

  • Clean Lifecycle 在进行真正的构建之前进行一些清理工作。
  • Default Lifecycle 构建的核心部分,编译,测试,打包,部署等等。
  • Site Lifecycle 生成项目报告,站点,发布站点。

我再次强调一下它们是相互独立的,你可以仅仅调用clean来清理工作目录,仅仅调用site来生成站点。当然你也可以直接运行 mvn clean install site 运行所有这三套生命周期。

知道了每套生命周期的大概用途和相互关系以后,来逐个详细看一下每套生命周期,Clean和Site相对比较简单,先解释一下。

每套生命周期都由一组阶段(Phase)组成,我们平时在命令行输入的命令总会对应于一个特定的阶段。比如,运行mvn clean ,这个的clean是Clean生命周期的一个阶段。有点绕?要知道有Clean生命周期,也有clean阶段。Clean生命周期一共包含了三个阶段:

  • pre-clean  执行一些需要在clean之前完成的工作
  • clean  移除所有上一次构建生成的文件
  • post-clean  执行一些需要在clean之后立刻完成的工作

mvn clean 中的clean就是上面的clean,在一个生命周期中,运行某个阶段的时候,它之前的所有阶段都会被运行,也就是说,mvn clean 等同于 mvn pre-clean clean ,如果我们运行 mvn post-clean ,那么 pre-clean,clean 都会被运行。这是Maven很重要的一个规则,可以大大简化命令行的输入。

下面看一下Site生命周期的各个阶段:

  • pre-site     执行一些需要在生成站点文档之前完成的工作
  • site    生成项目的站点文档
  • post-site     执行一些需要在生成站点文档之后完成的工作,并且为部署做准备
  • site-deploy     将生成的站点文档部署到特定的服务器上

这里经常用到的是site阶段和site-deploy阶段,用以生成和发布Maven站点,这可是Maven相当强大的功能,Manager比较喜欢,文档及统计数据自动生成,很好看。

最后,来看一下Maven的最重要的Default生命周期,绝大部分工作都发生在这个生命周期中,这里只解释一些比较重要和常用的阶段:

  • validate
  • generate-sources
  • process-sources
  • generate-resources
  • process-resources     复制并处理资源文件,至目标目录,准备打包。
  • compile     编译项目的源代码。
  • process-classes
  • generate-test-sources 
  • process-test-sources 
  • generate-test-resources
  • process-test-resources     复制并处理资源文件,至目标测试目录。
  • test-compile     编译测试源代码。
  • process-test-classes
  • test     使用合适的单元测试框架运行测试。这些测试代码不会被打包或部署。
  • prepare-package
  • package     接受编译好的代码,打包成可发布的格式,如 JAR 。
  • pre-integration-test
  • integration-test
  • post-integration-test
  • verify
  • install     将包安装至本地仓库,以让其它项目依赖。
  • deploy     将最终的包复制到远程的仓库,以让其它开发人员与项目共享。

基本上,根据名称我们就能猜出每个阶段的用途,关于其它阶段的解释,请参考 http://maven.apache.org/guides/introduction/introduction-to-the-lifecycle.html

记住,运行任何一个阶段的时候,它前面的所有阶段都会被运行,这也就是为什么我们运行mvn install 的时候,代码会被编译,测试,打包。

骨架

Maven约定的项目目录结构,如果手动创建,每个工程的重复工作非常多。为此,Maven提供了Archetype以帮助我们快速勾勒出项目骨架。

在IntelliJ IDEA中,使用Maven的骨架创建项目非常简单。我们只需选择File→New Project→Maven,勾选Create from archetype,然后在下方选择所需要使用的骨架(例如maven-archetype-webapp),点击Next按照向导提示操作即可。在选择骨架时,也可以直接输入关键词查找相应的骨架。

资料推荐

一些maven书籍介绍和一些maven视频介绍:
http://pan.baidu.com/s/1hq00qLA

国外非常不错的学习材料网站,集成了介绍、快速引导,书籍推荐等:
http://www.tutorialspoint.com/maven/index.htm

maven官网:
http://maven.apache.org/

官网介绍什么是maven:
http://maven.apache.org/what-is-maven.html

maven2和maven3的区别(目前主流是maven3):
http://tech.it168.com/a2010/1108/1123/000001123274_all.shtml
http://www.infoq.com/cn/news/2011/07/xxb-maven-10-time-to-update

maven下载:
http://maven.apache.org/download.cgi
windows需要下载的文件:apache-maven-版本号-bin.zip

maven官网5分钟速成:
http://maven.apache.org/guides/getting-started/maven-in-five-minutes.html

maven官网入门指南:
http://maven.apache.org/guides/getting-started/index.html

FAQ英文官网:
http://maven.apache.org/general.html

FAQ英文非官网:
http://docs.codehaus.org/display/MAVENUSER/FAQs-1

maven一些插件列表:
http://maven.apache.org/plugins

Maven 的41种骨架功能介绍:
http://www.cnblogs.com/iusmile/archive/2012/11/14/2770118.html
http://docs.codehaus.org/display/MAVENUSER/Archetypes+List

[7.11实习笔记] 环境搭建 JDK+IDEA+MAVEN+JBOSS+HSF+SVN

7月11日流水

今天上午领了工牌和PC。排了一个多小时的队。本来8点半到想着能早点领,没想到排PC的队排了半天突然工作人员一句“实习入职跟我来”,队伍全乱了……好不容易领了机子到IT临时服务点配置了一下,出来都快11点了。无力吐槽。

webwxgetmsgimg (3)

回到工位就把工牌和支付宝绑定了。这样在园区各个地方都不用带钱包,食堂超市直接刷工牌。还是比较方便的。

webwxgetmsgimg (4)

下午就是根据师姐给的内部百科链接(叫翔哥的师兄写的文档),以及一个Taobao_Developer_Cookbook的文档开始搭建工作环境。具体的笔记在下面会写。第一次搭这些环境还是比较蛋疼的。记录下来也好以后备查。

7月11日笔记

首先,明确需要搭建的环境:

  1. JDK 1.6.0_43
  2. IntelliJ IDEA 13.1.3(社区版)
  3. Maven 2.2.1
  4. JBoss 4.2.2.GA
  5. HSF 2.1.0.6
  6. TortoiseSVN 1.8

其次,阿里统一将这些环境安装在D:java_tools目录下。

为何要规划安装目录? 

开发人员之间经常会进行一些交流或者协助排查问题,最常见的几句话?“你的 Java 安装在哪里?”;“JBoss 安装在哪个目录下?我要改一下设置!”。“Eclipse 安装在哪个目录下,打开一下!”。如果不想让你的同事费心做这些事情,那最好将这些开发用的软件安装在指定的目录下,这样大家的环境都一样,排查问题就方便很多。还有 Java 软件最忌安装在有空格或者中文的目录下,这个一定需要注意一下。

为何要使用旧版的环境? 

版本还是挺重要的,有些高版本会导致一些莫名其妙的错误。师兄曾遇到过Maven版本的问题,总提示日志系统不存在。

接下来就可以依次搭建这些环境啦~

JDK 1.6.0_43

软件环境:Windows版,64位

下载地址:http://dl1.cr173.com//soft1/jdk-6.zip

安装配置:

  1. 下载并解压ZIP包。执行其中的jdk-6u43-windows-x64.exe,根据提示完成安装
  2. 配置环境变量:计算机→属性→高级系统设置→高级→环境变量
  3. 系统变量→新建JAVA_HOME变量。值为JDK安装目录。
  4. 系统变量→寻找PATH变量→编辑。在值的末尾加上JDK安装路径下bin目录,以及jre的bin目录(目录间以;分隔)
  5. 系统变量→新建CLASSPATH变量,值为 .; 以及JDK目录下lib目录,以及这个lib目录下的tools.jar
  6. 测试是否安装成功:启动cmd,输入java –version。如果显示版本号则安装成功。

IntelliJ IDEA 13.1.3(社区版)

软件环境:Windows 社区版(这是商业软件,是付费的。但社区版是免费的。)

下载地址:http://download-cf.jetbrains.com/idea/ideaIC-13.1.3.exe

安装配置:

  1. 下载并执行安装程序,根据提示完成安装
  2. 修改IDE外观与字体:File→Settings→IDE Settings→Appearance 在这里选择喜欢的Theme,以及Override default fonts by的字体和字号;
  3. 修改代码字体:File→Settings→IDE Settings→Editor→Colors & Fonts→Font 先在Scheme name处点Save As,输入自己的配置的名字;然后设置自己喜欢的字体字号和间距。个人比较喜欢Source Code Pro,看着很舒服。
  4. 解决中文乱码:在上一步把Show only monospaced fonts的勾去掉,Primary font选自己喜欢的英文字体,勾选Secondary font并选择一个中文字体。我选的是微软雅黑(Microsoft YaHei UI)。
  5. 显示行号:File→Settings→IDE Settings→Editor→Appearance,勾选Show line numbers以显示行号。

更多技巧:http://www.cnblogs.com/sky100/archive/2009/01/22/1379949.html

插件使用:

  1. 插件安装的方法:
    1. File→SettingsIDE Settings→Plugins 点击Browse repositories按钮。
    2. 在搜索框直接搜索想要的插件
    3. 点击右边的install plugin按钮就可以了。
  2. 常用插件:
    1. Identifier Highlighter 高亮显示选中变量插件
    2. Key Promoter 快捷键提示插件
    3. Jrebel 热部署插件(需破解。破解方法:http://my.oschina.net/lujianing/blog/178578#OSC_h2_3
    4. FindBugs for IntelliJ IDEA
    5. TabSwitch 通过ctrl+tab在文件、各个面板间切换。
    6. Mybatis
    7. EncodingPlugin 可按项目指定其默认编码,非常有用

(更多插件请参阅http://blog.csdn.net/sunny243788557/article/details/26556967

Maven 2.2.1

下载地址:http://dxdown1.onlinedown.net/down/apache-maven-2.2.1-bin.tar.zip

安装配置:

  1. 下载并解压ZIP包。将其解压到安装路径。
  2. 下载 http://baike.corp.taobao.com/images/9/96/Maven_Settings.xml 这个配置文件,并覆盖到mavenconf目录中。
  3. 设置系统环境变量(同上文JDK的方法),将安装目录下bin目录添加到PATH环境变量值中。
  4. 新建系统环境变量M2_HOME,设置值为maven安装目录。
  5. 测试是否安装成功:启动cmd,输入mvn –version。如果显示版本号则安装成功。
  6. 执行mvn help:system进行mvn的初始化工作,主要是检查artifact是否能正确下载,初始化Maven本地仓库等。

JBoss 4.2.2.GA

软件环境:我们这里要使用的是阿里修改过的JBoss线上通用版本,和官方版本不一样,修改了classloader双亲委派。

下载地址:http://hsf.taobao.net/software/jboss-4.2.2.GA.zip

安装配置:

  1. 下载并解压ZIP包。将其解压到安装路径。
  2. 新建系统环境变量JBOSS_HOME,设置值为JBoss安装路径。
  3. 测试是否安装成功:运行Jboss安装目录下bin目录中的run.bat,若窗口中没有出现异常,且出现10:16:19,765 INFO [Server] JBoss (MX MicroKernel) [4.2.1.GA (build: SVNTag=JBoss_4_2_1_GA date=200707131605)] Started in 30s:828ms字样,则表示安装成功。
  4. 我们可以通过访问 http://localhost进入JBoss的欢迎界面

HSF 2.1.0.6

下载地址:http://hsf.taobao.net/hsfversion/hsf2.1.0.6/taobao-hsf.tgz

安装配置:

  1. 下载tgz包。
  2. 将其解压到JBoss目录下的serverdefaultdeploy目录下即可。

TortoiseSVN 1.8

软件环境:Windows 64位版

下载地址:http://cqindex.newhua.com/down/TortoiseSVN-1.8.7.25475-x64-svn-1.8.9.zip

安装配置:

  1. 下载并解压ZIP包,执行其中的安装程序。
  2. 根据提示进行安装。在组件选择的一步,记得勾选command line client tools(默认是不安装这个部分的)。没装的话,IDEA可能会报错,提示执行svn命令出错。

至此,基本的开发环境搭建就完成了。后面就要开始学习啦~

[7.10实习笔记] 入职手续与培训

决定在博客里记录下每天的实习生活。可能是日常流水,也会有学习笔记。

7月10日流水

7月10日上午起早转公交到海创园。早早来到二层大厅等待领自己的材料。大概9点多领到了一个文件夹和一个文具袋。文件夹里是一大叠卖身契,文具袋里是工牌套、各种笔和本子。然后就进会场坐着等待开始了。

webwxgetmsgimg (1)

一上午的主要任务就是讲解一堆卖身契的签法,以及上交了一张一寸照用于办理工牌。(坑爹的是,按照后来发下来的工牌情况看,乖乖交照片的都是扫描制作的,照片普遍都偏色严重;而因为没带照片交电子版的反而幸免于难…- -#)

中午在海创园挤到爆的食堂吃了饭。只有1小时用餐时间,很赶。

下午是行政,财务,IT,薪酬福利培训。比较冗长。就不多说了。主要槽点在于男性25岁以上就算晚婚了可以享受15天带薪婚假哦~ 唉,首先,我得在25岁前找到妹纸……

结束培训突降暴雨。我们在海创园等到暴雨过去后,终于来到园区了。园区倒是非常漂亮的~ 天猫事业部在4号楼。终于见到了亲爱的师兄师姐们。

webwxgetmsgimg

惊喜的发现隔壁工位刚入职的师姐,也是福建人~口音太亲切了哈哈。因为工牌还没发下来,所以蹭了师姐一顿晚饭。感觉团队还是很融洽的~

对即将开始的实习生活充满了期待啊。

webwxgetmsgimg (2)

实习应聘记(二)——阿里,总结

上一篇博文写了简历撰写,去哪儿笔试和360电面。这篇主要写写阿里的三轮电面(主要是技术面,HR面是第四轮还没接到…),以及自己这段时间的一些总结吧。

阿里一面

一个学姐给的内推机会,我选的岗位是研发工程师。被分到的部门是天猫事业部。

3月6日在线投递简历,没想到3月7日周五下午就接到了一面电话。当时是下午2点多,我正迷迷糊糊准备上床小睡一会儿,突然来了个0571的固话号码,我也没多想就接了起来。对方说是天猫的,看到了我的简历,打电话来“简单聊一聊”。我突然意识到,我去,电话面试。

面试官可能为了打开话题,先问我最近在忙啥。我脑子正糊,说最近在忙着投简历呢,不是各大公司都开始校招了嘛……面试官笑了下,呵呵。突然脑子清醒过来,靠对方想问的应该是学术上在干啥好继续深入问技术问题吧。赶忙说除此之外也在做一个什么什么项目,跟着老师研究什么什么课题云云。我说到了我的可视化项目,对方表现出了一些兴趣,我赶忙趁热打铁说这个项目有在线演示的地址,您是否有兴趣看看?面试官说好,我就把URL报给了他。开始边介绍操作边解释项目(可见,有可能的话,最好能在面试前把能够展示的项目都搭到网上,特别是这种电话面试,隔空交流本就不如当面顺畅,如果能让对方直观的看到项目效果,沟通效果会好很多)。 

面试官问,这个项目遇到了什么难点?我说,是数据库的瓶颈。我们使用的是MySQL,目前三四百个点的规模查询效率还好,但上千个点的情况,查询时间可能达到十几秒。面试官问什么样的查询,我描述了下先是根据输入的关键字找到ID,再根据ID找出直接相关的ID,这样构成一个ID集合,最后查找集合内两两ID是否存在连接,过程类似点→树→图,每个请求要经过这三步查询。  

于是面试官问数据库查询做了哪些优化。我就说了下我是怎么设计的数据库,分了几个表,用类似邻接表的结构来存整个复杂网络,如何建的索引,然后提到了,有一个字段是一个枚举量,只有{“PersonProfile”,”OrgProfile”,”LocationProfile”}三种取值,因此我把类似这种的量直接数值化存储然后建索引,提高了查询效率。

面试官抓住这个,问我为什么字符串数值化后能够提高查询效率?从数据库存储引擎的角度解释……我就懵了,因为我对数据库内部存储的原理并不了解,只停留在使用的层面上。只能猜测:数值和字符串相比,比较与排序的时间都短得多?

显然这不是面试官想要的答案,他提示我,数据库存储引擎用B树或B+数作为存储结构。又是一箭穿膝盖……我对B树和B+树也不了解啊!只好老实说并不是非常清楚B树和B+树……

面试官还不放弃!(或许这就是阿里的面试风格吧… )他继续提示我,就简单把B树或B+数想象成一颗自平衡二叉排序树,结点存索引,叶子要么指向磁盘中存数据的地址,要么直接指向一块存数据的空间(当然这并不是B树或B+树的正确定义,面试官只是想短时间引导我继续思考,大家有兴趣可以去网上查阅B树,B+树,B*树等相关知识的文章 )。我只好猜,数值化后数据小,可以存在直接指向的空间,而不需要频繁磁盘IO?

最后面试官告诉我,和磁盘每次取一个512K的block有关。数据小,一次能拿出的数据就多。字符串有可能一个block只存的下一两个。

而后就是一些常规问题,何时毕业,何时实习,有什么问题想要问他。我问了他天猫对于海量真实用户数据做了哪些挖掘?他大概给我讲了下天猫的挖掘过程:先将用户分类,而后分析同类用户购买商品,而后把这些商品反过来推荐给该用户,这样一个推荐过程。然后就告诉我如果有消息他的同事会和我进一步联系。结束了面试。整个过程大约二十分钟。   

阿里二面

一面结束后,不久就有消息说通过后一周之内会接到二面,而且二面传闻还是视频面试……于是3月10日到16日一整周时间我都过得提心吊胆……真是“又期待又怕受伤害”……可是这周过得风平浪静波澜不惊。就在我都不知道还会不会有二面的时候,3月17日周一上午计算机硬件实验上机,突然来了个0571…于是…二面来了。

本以为电话是约视频面试的时间,没想到又是直接说“聊聊”,看来又是一轮电话面试。跟面试官说给2分钟换一个安静的地方,然后就跑回教室拿上简历又跑到空无一人的楼梯间(电面高发期随身携带简历还是很必要的)。两分钟后面试官的电话就又来了。

这一轮的面试,纯技术问题并不多。面试官上来第一个问题,居然是“说说在大学阶段做过的印象最深的事”。当时又傻了一下(我发现我在电面过程中老是会被面试官问傻…唉…),之前都在准备技术问题,从来没想过会来这一出…我就问是技术相关还是非技术相关的?对方说都行。我想了想就说是校学生会的经历吧,我相信,重要的并不是你加入了哪些牛逼的组织,而是你的加入对它产生了什么改变。在我加入科技部之前,科技部在学生会的地位并不高,属于实打实的辅助型部门。任部长期间我和另外两位部长努力将它由幕后转向台前,在校会历史上第一次成功联合各大院级学生会合办了视频大赛。面试官问,在这个过程中遇到了什么难点,如何解决。我说难点主要在于和院会沟通吧。因为并不是所有院会都乐于与校会合作。解决方法就是清楚的分析利弊,说明他们有我们所没有的资源——能够拉外联,能更好的煽动本院学生参与;而我们有更成熟完善的活动举办经验,更高的活动规格(校级)。合作是一种双赢。解释清楚后大部分学院还是愿意合作的。

又聊到“目前受到的比较大的挫折”,我犹豫了下,回答可能高考算一个吧。当时因为一些个人失误发挥的并不好,对我和我家人都是比较大的打击。面试官问如何恢复。我说当时最紧要要面临的抉择就是是否复读。我父亲是极力反对我复读的。因为他也是一名高中教师,他说复读能够有大幅提分的情况非常少。最后我没有复读,来了西邮。当然我现在回头来看,我不后悔当时的选择。因为首先我读的是我喜欢的计算机专业,其次我有幸进入了西邮Linux兴趣小组,结识了一帮志同道合的朋友,在这个积极上进的圈子里共同努力共同奋斗。现在想来,大学的好坏,甚至师资的好坏,都不是决定性的因素。真正重要的是个人的努力。面试官评价说在我的年龄能有这个想法的不多(心里窃喜一下,觉得应该问题不大了~)。

后来说到项目,面试官问我用C++做了什么项目,我说完全用C++实现的就是简历上第三个项目,用的C++ MFC。面试官问是团队项目还是个人项目?我说是4人团队,我是负责人。于是面试官问我如何分工。我就大概阐述了下因为开发周期只有20天比较紧,所以没有同时分工开发客户端和服务端,而是先集中力量一起攻破客户端,再一起攻破服务端。每个阶段再根据客户端和服务端的模块划分任务。这样遇到技术问题也好沟通。 

后面面试官又问了个很“奇怪”的问题:有没用自己的技术赚过外快。我说因为我对计算机各个方面都挺感兴趣,所以也会一些网页前后端,视频音频处理之类的。之前在导师介绍下帮陕西省互联网大会制作了开场视频;也曾经帮一家物流公司制作了网站前端。当时对方要求网站符合RWD(响应式网页设计)而我不会,所以我咨询了一些学长,选用了bootstrap框架完成,这个框架原生支持RWD。(我说这段其实是想有意展现快速学习能力,不知道面试官有没理解…)面试官问,那些核心技能呢?C++,C之类的。我说没有用它们赚过外快,基本都是用它们在校内做一些项目,并没有用来盈利……

再后来面试官问我,看我的简历应该很有可能是能拿到保研的(简历写得有点…美化自己…大家懂…),对未来是什么规划。我说因为本校并不是很好的学校,保研也只能保本校而我不大愿意在本校读研。如果能有幸拿到贵公司的实习机会并参与工作,可能会选择就业;如果没能够进入贵公司,我最近也在准备托福,可能会选择出去读研,香港等地…… 

而后问我实习希望做哪方面工作。我回答我对数据挖掘挺有兴趣,虽然了解不多。而我知道天猫掌握着海量的用户真实数据,恰好我一面也有向面试官询问天猫的数据挖掘,其实我还挺希望能够在实习阶段接触到相关的业务,不知道有没有机会。面试官说他不能确定但会帮我在评价中注明。紧接着面试官就反问我,如果由我来做天猫推荐算法,我会如何给用户进行分类。这个问题恰好我以前有想过,但并没有验证过正确性,于是我就阐述了下我的思路:首先作为一个电商网站,用户间最大的差异应该在于消费能力。因此先根据消费能力(近期月均消费额等数据)进行分类。然后是性别,再然后是年龄,最后是地域。因为众所周知的“南北差异”等原因我认为地域也会对消费习惯造成影响。这就是我对于分类方法和优先级的想法。

面试过程就差不多结束了,随后就是例行的“何时来实习”,“有什么问题想问我”。这次我问了阿里系各个垂直产品是独立进行开发,还是共用同一个底层架构在上层拉分支?面试官回答是后者。支付宝、天猫、淘宝、阿里巴巴等,底层其实是使用同一套技术。然后就告诉我有进一步消息会有人和我联系。结束了二面。全过程约半小时。

总体感觉,二面并不是技术型面试,更多的是对综合能力和思维模式的考察。尽量在每一个问题上展现自己的闪光点和独特之处就好。

阿里三面

二面结束后,下午我随手打开阿里校招网站,看到我的状态已经从“应聘中”变成了“应聘成功”,顿时非常兴奋!但又不敢确定,难道两轮面试就有结果了?后来内推的学姐在Q上恭喜我终面通过,我一下放松下来,觉得世界都是美好的~

可是……事实证明,我还是Too young too simple。兴奋期还没过,周二晚上在实验室和同学写一个项目的需求分析,突然来了一个010的电话。我想,是不是去哪儿的笔试结果出来了呢?出门接电话,是一个自称北京阿里的工程师打来的。和我预约面试时间。当时我就懵了(对,又一次),因为之前都是杭州的号码(天猫在杭州),于是我问,我已经参加过阿里的面试,请问您是哪个部门?对方反问我参加的是哪个部门的面试,我说是天猫,对方说他也是。他不知道具体流程,HR安排的。我只好和他商量了下,约在3月20日周四晚8点,进行第三轮面试。

因为他自称是工程师,所以我明白,这次一定是一场实打实的技术面没跑了。本来彻底放松的神经又开始紧张,甚至更甚于前,紧张到全身发抖。为何后台显示通过却又加面一轮?是和往年一样借此刷人?还是其他原因?会问什么技术问题? ……这些都没有答案,我能做的也就只有尽力准备了。

周三满课。周四直到晚7点前,我把我的简历过了一遍又一遍,想象他会在哪几个点下挖;准备了自我介绍的稿子;把树和图的常用算法以及时空复杂度快速过了一遍;看了小组群共享里张瑞上传的《十道海量数据处理面试题与十个方法大总结》。这里向大家强烈推荐这篇文章!不长的篇幅能让大家快速掌握海量数据处理面试题的大概套路和可选路线。(膜拜JULY大神!)而事实证明,我在三面中碰到两道里面的类似题目!实战亲身验证效果!

晚上8点15,电话来了……这次的面试官比较常规。首先让我做自我介绍。我大概说了一下事先准备的稿子。因为在自我介绍中提到项目里使用了很多开源软件,因而对开源精神有一种推崇和向往。他就问我,具体用过哪些开源的东西。我说,底层来说,Linux,Apache,MySQL之类的一套;上层的话,做可视化用到了D3.js这个开源库,前端用Bootstrap开源框架,还有一些XML,JSON协议解析也用到了开源的库。他就问,在配置过程中有遇到什么问题吗?我说基本遇到的问题也都通过官方文档或论坛社区解决了,没有遇到什么特别难的问题。

然后他说,看我的简历,技能主要的点在于1、CC++JAVA 2、数据结构和算法 3、数据库 是吗?我说我对JAVA不能算熟练,只是项目有用到,知道语法而已。更多的是用C和C++。于是他问我,C++的STL有用过吗。我非常惭愧的说只用过map之类简单的…他继续问,知不知道智能指针。我就不出所料的被问倒了。只好说不是很了解。面试官就知趣的往下问了。

然后是数据结构与算法4连杀!

第一个问题:给千万级规模整数数组做去重。我一听问题就乐了,和360那个问题简直如出一辙嘛~bitmap搞定。

第二个问题:如何从M个数中找出前N大的数。这个问题在我上面说的那篇十道海量数据处理面试题的博文里有详细解答。主要就是构建一个N个结点的小顶堆,而后将后面的每一个数和堆顶比较,比堆顶大则替换,然后维护堆。这样遍历一次以后就得到了前N大的数。时间复杂度O(M log N)。

第三个问题:给定一个整数数组,找出一段连续区间使得区间内元素和最大。这道题把我卡住了,虽然记得明明是见过的一道水题但就是想不起来方程。我只好先说,最朴素的做法是枚举区间起始点和终点,复杂度O(N^2)。优化方法是动态规划,不好意思有点紧张,让我想一下方程……过了一会儿实在紧张的没思路,只好问能否给些提示。于是面试官说,每个区间都有终点,我反应过来,状态是用区间尾表示。最终在面试官提示下写出了动归方程f(n)=max{f(n-1)+a(n), a(n)}。其中f(n)表示以n位置为区间尾的区间最大和。它有两种情况,要么是f(n-1)连上当前元素,要么是从当前元素重新开始。面试官问时间复杂度和空间复杂度。我说都是O(n)。

第四个问题:第三个问题的加强版。如果第三题是循环数组,怎么处理。这个问题比较简单,我说直接把原数组复制一份接在原数组后面,再用相同的方法做就可以了。时空复杂度不变。

到这里技术面试的部分就差不多了。又问了我是否有参加过ACM竞赛,我说我们学校没有组织组队和集训,所以我只能和同学组队报名参加一些邀请赛。

后面就进入闲聊模式。面试官和我聊学校,聊未来打算,聊出国就业,劝我不要去香港读研要去就去美国云云…总之聊得挺投机。最后例行公事“有没什么要问我的问题”,我之前准备的问题都是关于天猫的,无奈面试官表示他是支付宝的,也在阿里云呆了几年。对天猫并不了解。 面试也就差不多结束了。技术部分大约15~20分钟,非技术闲聊了十来分钟。全程大约半小时出头。

面试结束后感觉不错。第二天也果然接到了经理的电话,告知我3面技术面试都通过了。还有一轮HR不过以他对我的认识他认为问题不大(我才知道好像二面那轮就是这位经理面的),如果也通过就是去杭州天猫他的部门。后面的校园宣讲就不用参加了。听到这里我才终于如释重负……这段经历也算接近尾声。

总结

这段经历让我非常充分的感觉到,平日的积累真的很重要。人品也真的很重要(问到的问题差不多刚好在我的能力范围内,不大擅长的LINUX底层都没问)。如果正面临面试,已经没有过多时间做深入积累或者积攒人品,那就做好能做的所有准备:自我介绍,简历所有可能被问的技能和技术点,数据结构和算法(树非常爱考!然后就是动归!),以及海量数据处理题。 除此之外,在每个面试过程中,尽量在回答每一个问题时能扯到展现出自己的某一个闪光点,并且联系实际例子来证明。 最后,千万千万放平心态,不要紧张。有时候,打败自己的不是难题,而是失常发挥。另外,千万不要轻易放弃任何一个问题而直接说不知道,可以问面试官“能否给一些提示?”只要在他的引导下大概能回答个六七成,留下的印象也会大大改观。而且保不准对方一提示就想出来了呢~

最后,相信大家都会找到理想的实习,所以我也就祝大家早点达成这个成就啦~加油!  

实习应聘记(一)——简历撰写,去哪儿,360

从开始准备简历撰写,到现在基本确定实习岗位,晃晃忽忽过了大半个月。半个月说长不长,说短不短,但绝对是我这20年来最难忘的历程之一。其中经历的心态上的大起大落,只有当自己真的置身其中,才能有所体会。写下这篇博客,一来记录自己第一次应聘岗位的心路历程,二来也是想记录下几轮笔试面试的题目,希望能对各位小伙伴们准备后续面试有所帮助。

简历

我大约从3月1日开始准备简历,当时李力通知3月7号交第一稿,给实验室的学长学姐们修改。开始的几天,完全没有头绪,不知道该从哪里开始下笔。最后胡乱挑了WORD上的一个看着还顺眼的联机模板拿来改。 于是有了现在看来不堪入目的第一稿……(每稿简历的修改我都保留了备份,现在回头看来也算感慨颇多)

简历第一稿

这稿简历当时自认为还算简洁,但却被学长学姐挑出了一堆毛病,才知道原来自己有那么多细节没有注意:

  1. 留白过多,字体太小,颜色难看,不满两页。(简历要么一页写完,要么撑满两页,忌一页半。)
  2. 名字下方的信息,内容不显眼,排版不清晰。HR看到一份简历时,希望能够快速定位到手机和邮箱两个联系方式,应当前置。尤其是手机,应当用连字符分隔(形如:130-1234-5678),避免HR拨错号码,与职位失之交臂。
  3. “目标”改为“求职意向”更妥。
  4. 教育经历前置,将奖学金与专业排名等信息调整到“个人荣誉”中,HR关心的信息是何时毕业。这才是重点。
  5. “技能”中,程度副词由高到低依次是精通,熟练,熟悉,了解。因此简历中尽量使用熟练”和“熟悉”不要使用“了解”。同时,技能应当根据所应聘职位的要求,内容和顺序做针对性调整。忌同一份简历海投所有公司。当然,上面说的“求职意向”也是同理。
  6. “项目”中,把每个项目使用到的技术点前置,单独列出,有助于面试官快速了解项目。 
  7. “个人荣誉”部分,分为竞赛、奖学金、德育三块,把时间、项目、奖项分三列对齐列出,并按时间倒序排列。

大体要点就是这些,都是些容易忽略的细节。在学长学姐帮助下修改了若干稿后,得到了我在后续投递中使用的终稿:

简历2

简历是职位的敲门砖,还是需要花时间反复修改推敲的。我相信这份反复修改的简历在我的整个应聘过程中,起到了很大的作用。

去哪儿

其实严格按时间顺序,我是先接到了阿里的电话一面,然后才参加的去哪儿网笔试。但为了逻辑清晰,还是把去哪儿的笔试提到前面来写吧。

去哪儿网的简历网投其实开始的挺早,但需要在中华英才网上填一个巨繁琐的表格……我当时其实算是相当早开始填写的,但特别逗比的拖到了截止当天下午6点才提交(该死的拖延症),而后来发现去哪儿下午6点20就在官微上发布了“笔试邀请函发放完毕”的微博。于是我妥妥的没有收到邀请……

怎么办?果断霸笔呗!

去哪儿要求携带学生证和笔试邀请邮件打印稿前往西安交大笔试。因为我的确有提交简历,所以也有了一个“简历编号”。于是果断把小伙伴们的笔试邀请邮件拿来,“稍作修改”,自己给自己发的邀请函就火热出炉啦。早上10点,实验室小伙伴们结伴向交大进发。

印象非常深刻当天是3月8日妇女节。恰逢周末,路上堵得不行(中国人总是有把任何节日过成情人节的能力)。 经过一小时的士上的颠簸,即将晕车吐出来的时候,我们终于到了……找到笔试教室,发现门口一堆霸笔的人被拦下HR不让入场。但HR只会对照打印的邀请函,根本没有签到表或联网查询编号来验真伪,于是成功凭借伪造的邀请函混了进去!

当天笔试是开发与测试同一份卷子,开发做1,2,5三题,测试做3,4,5三题。题目并不能算难。

1、要求实现一个函数,对于给定有序整型数组以及一个给定整数,若整数存在于数组中,输出其位置;否则输出其应被插入的位置。例:

[1,2,3,4,5] 4 –> 3

[1,2,3,4,5] 6 –> 5

[1,2,4,5] 2 –> 1

[1,2,4,5] 3 –> 2

这道题就是一个简单的二分查找,时间复杂度O(log N)。当然一般的顺序查找也可以但O(N)解法对于这道题目来说有点太水了。我当时懒得写循环,直接4行递归写完了查找函数,然后再用要求实现的函数调用自己写的查找函数。唯一一点棘手的,是题目给的函数声明并不包含数组长度。如果是java,可以很方便的用.length()方法获取数组长度,但C就无能为力。其实去哪儿内部大量采用JAVA,因此笔试暗示用JAVA解题也不无道理。但因为自己对JAVA并不熟练所以整套卷子仍然用C答。这里我只好随意声明了个长度变量,随意用sizeof赋了个值(当然肯定是没用的)。当时只希望改卷的人不要纠结这种细节。

2、给定两个文件,格式如下:

1.txt

学号  科目  成绩

1001  数据结构  79

1002  编译原理  85

……

2.txt

学号  学院  专业  姓名

1001  计算机学院  软件工程  张三

……

要求输出每个专业总分排名第一的人的姓名,有挂科的不算。

这道题目是三道题目中最为麻烦的一道。我当时的想法是这样的,两个文件以学号为单位交叉比对每一个人并求出总分,需要M*N^2(假定N人M科),显然过于麻烦。因此首先按行读入第一个文件,将学号进行哈希(当时时间紧张直接注释这一思路并直接用f(x)=x作为哈希函数)把成绩加到哈希后总分数组相应元素中。至于挂科,我的处理是碰到<60的单科分数直接把总分减去INT_MAX来将其排出。

而后读入第二个文件,因为输出的是专业排名第一,所以学院信息直接忽略。同样哈希学号来得到每个学号对应的姓名和专业名。而后根据专业(第一关键字)和总分(第二关键字)进行双关键字的快排(只需重写compare函数就可以了,优先比较专业,相同专业比较总分)。这样得到按专业排序,同专业分数递减的结果。输出只需遍历一遍,专业名和前一个人不同的输出姓名,否则continue。求总分O(N*M),映射姓名和专业O(N),排序O(N log N)。因此总时间复杂度为O(N*M)和O(N log N)中的最大值,小于朴素的O(N*M^2)。

C语言实现的代码,整整写了正反两面A4纸……最后时间紧张还把快排失误写错了一点。 

3、给第一题写测试用例。

因为没有专门研究过测试方法,我就按我的思路分了几类:

  • 数组元素数量为奇数
  •     查找数存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  •     查找数不存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  • 数组元素数量为偶数
  •     查找数存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  •     查找数不存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾

共3级12类测试用例。

90分钟,我掐着点做完交卷。 当时感觉还行,至少把能展现的能力都尽量展现了。而后来也成功接到了笔试通过,等待电话通知面试安排的短信,说明结果也是不错的。这场笔试为我树立了比较大的自信。 也让我对霸笔霸面不再有那么强的紧张感。

360

360的职位是实验室学姐帮助内推的,系统部,负责360的底层技术和大数据平台。 当时是在一堂“跨文化交流”课上,突然来了一个010开头的电话,一看来显猜测是360的电面就赶忙出来接了。

这是我整个应聘过程中感觉发挥的最差的一场,以至于面完后我一度认为自己没有通过的希望。

面试官是典型的按简历一条一条向下过的面试思路。他注意到我的获奖经历中有提到ACM-ICPC(虽然只是一个水水的Honorable Mention,可见企业对于ACM竞赛经历是多少看重 ),技能中又提到了算法与数据结构,因此直接从数据结构开始问。

第一个问题,描述一下如何建立一棵二叉树

这个问题我就有点蒙,建立一棵树,这怎么说啊?我回答这要看具体的问题需求还有输入数据的格式,可以按照线性存,用2n和2n+1存左右孩子;也可以按链式存,节点以指针相连建树。

第二个问题,非递归遍历二叉树

脑子里直接蹦出栈了,但是因为电面太突然,脑子一下有点白,愣是没描述清楚具体过程,吭吭哧哧卡了一会儿,才说出先 压树根,而后每出栈一次,将非空的左右孩子入栈。直到栈空,遍历完毕。 

第三个问题,给出不重复但不保证全部出现的1~10亿间的自然数,进行排序。

面试前没有准备大数据类型题目,其实这是一道很经典的题。我当时只能回答,可以用桶排的思想,先将数按高位分为若干个文件,再依次细分文件,外部排序。或者使用外排归并。面试官直接说,直接读内存放不下,外排磁盘IO过高。我想了一下没想出其他方案,最后面试官告诉我用bitmap……这个问题回答的不好让我一下对这场面试更加没信心了。 

后面就是快速过了一下我简历上的每一个项目。当时因为先接到阿里的一面电面,面试官会抓着项目某个技术点深挖,因此当360面试官问我某个项目时,我只是很笼统的概述了一下,等待他问具体技术细节。没想到他竟然就这样很快的过掉了简历上的三个项目,没一个问到技术细节。又问了“何时能入职”等常规问题,而后直接跟我说等待通知,结束了面试。也没问我是否有问题要问他。整场面试只持续了13分钟,出奇的短。这也直接让我对这场面试的结果失去了信心。心情瞬间跌到谷底。 这些题目根本不算难,甚至可以说相当基础,但我却答得不好……

没想到次日内推的学姐就告诉我面试结果不错,通过了,并且没有后续的技术电面,只要等HR和我联系就行了。

这个结果大大出乎我的意料,但也是我通过的第一个职位,给了我很大的鼓励。

下面就是阿里的三轮技术面试了,因为过程较长内容较多,同时也是这段时间的主要内容,后面单开一篇博文写。有兴趣的读者可以继续阅读下一篇博文《实习应聘记(二)——阿里,总结》 

最小编辑距离 算法原理

问题

最小编辑距离 Minimum Edit Distance
关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。
设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。
例如 s1 = “12433” 和 s2 = “1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)

性质

计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质:

1.   d(s1,"") = d("",s1) = |s1|
     d("c1","c2") = c1 == c2 ? 0 : 1;
2.   d(s1+c1,s2+c2) = min(  d(s1,s2)+ c1==c2 ? 0 : 1 ,
                            1 + d(s1+c1,s2),
                            1 + d(s1,s2+c2)  );

第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有:

1.  把c1变成c2
2.  s1+c1后删除c1              d = (1 + d(s1, s2 + c2))
3.  s1+c1后插入c2              d = (1 + d(s1 + c1, s2))

对于2和3的操作可以等价于:
_2.   s2+c2后添加c1        d = (1 + d(s1, s2 + c2))
_3.   s2+c2后删除c2        d = (1 + d(s1 + c1, s2))

因此可以得到计算编辑距离的性质2。

复杂度分析

从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记,并假设两个串长度都为 n )
可以看到,该问题的复杂度为指数级别 3 的 n 次方,对于较长的串,时间上是无法让人忍受的。
分析: 在上面的结构中,我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

动态规划求解

首先为了避免重复计算子问题,添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到

M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ]   = min(  m[i-1,j-1] + E[ i, j ] ,
                    1 + m[i, j-1] ,
                    1 + m[i-1, j]  );

复杂度
从新的计算式看出,计算过程为

      i=1 -> |s1|
             j=1 -> |s2|
                    M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

改进

当s[i]和s[j]相等时,代价为0,必然为最小值,所以首先判断两字符是否相等,若相等则直接判定M[i][j]=M[i-1][j-1],判断下个。这样可以省很多计算。

工具宏:直接用一个宏来完成“求取三者最小值”的功能。不同于递归,宏定义消耗很小,完全可以放心使用。

#ifndef _MIN(xyz)
#define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(xyz)

[转]如何用Python写一个贪吃蛇AI

作者:Hawstein
出处:http://hawstein.com/posts/snake-ai.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

前言

这两天在网上看到一张让人涨姿势的图片,图片中展示的是贪吃蛇游戏, 估计大部分人都玩过。但如果仅仅是贪吃蛇游戏,那么它就没有什么让人涨姿势的地方了。 问题的关键在于,图片中的贪吃蛇真的很贪吃XD,它把矩形中出现的食物吃了个遍, 然后华丽丽地把整个矩形填满,真心是看得赏心悦目。作为一个CSer, 第一个想到的是,这东西是写程序实现的(因为,一般人干不出这事。 果断是要让程序来干的)第二个想到的是,写程序该如何实现,该用什么算法? 既然开始想了,就开始做。因为Talk is cheap,要show me the code才行。 (从耗子叔那学来的)

开始之前,让我们再欣赏一下那只让人涨姿势的贪吃蛇吧:( 如果下面的动态图片浏览效果不佳的话,可以右键保存下来查看)

语言选择

Life is short, use python! 所以,根本就没多想,直接上python。

最初版本

先让你的程序跑起来

首先,我们第一件要做的就是先不要去分析这个问题。 你好歹先写个能运行起来的贪吃蛇游戏,然后再去想AI部分。这个应该很简单, cc++也就百来行代码(如果我没记错的话。不弄复杂界面,直接在控制台下跑), python就更简单了,去掉注释和空行,5、60行代码就搞定了。而且,最最关键的, 这个东西网上肯定写滥了,你没有必要重复造轮子, 去弄一份来按照你的意愿改造一下就行了。

简单版本

我觉得直接写perfect版本不是什么好路子。因为perfect版本往往要考虑很多东西, 直接上来就写这个一般是bug百出的。所以, 一开始我的目标仅仅是让程序去控制贪吃蛇运动,让它去吃食物,仅此而已。 现在让我们来陈述一下最初的问题:

在一个矩形中,每一时刻有一个食物,贪吃蛇要在不撞到自己的条件下,
找到一条路(未必要最优),然后沿着这条路运行,去享用它的美食

我们先不去想蛇会越来越长这个事实,问题基本就是,给你一个起点(蛇头)和一个终点( 食物),要避开障碍物(蛇身),从起点找到一条可行路到达终点。 我们可以用的方法有:

  • BFS
  • DFS
  • A*

只要有选择,就先选择最简单的方案,我们现在的目标是要让程序先跑起来, 优化是后话。so,从BFS开始。我们最初将蛇头位置放入队列,然后只要队列非空, 就将队头位置出队,然后把它四领域内的4个点放入队列,不断地循环操作, 直到到达食物的位置。这个过程中,我们需要注意几点:1.访问过的点不再访问。 2.保存每个点的父结点(即每个位置是从哪个位置走到它的, 这样我们才能把可行路径找出来)。3.蛇身所在位置和四面墙不可访问。

通过BFS找到食物后,只需要让蛇沿着可行路径运动即可。这个简单版本写完后, 贪吃蛇就可以很欢快地运行一段时间了。看图吧:(不流畅的感觉来自录屏软件@_@)

为了尽量保持简单,我用的是curses模块,直接在终端进行绘图。 从上面的动态图片可以看出,每次都单纯地使用BFS,最终有一天, 贪吃蛇会因为这种不顾后果的短视行为而陷入困境。 而且,即使到了那个时候,它也只会BFS一种策略, 导致因为当前看不到目标(食物),认为自己这辈子就这样了,破罐子破摔, 最终停在它人生中的某一个点,不再前进。(我好爱讲哲理XD)

BFS+Wander

上一节的简单版本跑起来后,我们认识到,只教贪吃蛇一种策略是不行的。 它这么笨一条蛇,你不多教它一点,它分分钟就会挂掉的。 所以,我写了个Wander函数,顾名思义,当贪吃蛇陷入困境后, 就别让它再BFS了,而是让它随便四处走走,散散心,思考一下人生什么的。 这个就好比你困惑迷茫的时候还去工作,效率不佳不说,还可能阻碍你走出困境; 相反,这时候你如果放下手中的工作,停下来,出去旅个游什么的。回来时, 说不定就豁然开朗,土地平旷,屋舍俨然了。

Wander函数怎么写都行,但是肯定有优劣之分。我写了两个版本,一个是在可行的范围内, 朝随机方向走随机步。也就是说,蛇每次运动的方向是随机出来的, 总共运动的步数也是随机的。Wander完之后,再去BFS一下,看能否吃到食物, 如果可以那就皆大欢喜了。如果不行,说明思考人生的时间还不够,再Wander一下。 这样过程不断地循环进行。可是就像“随机过程随机过”一样,你“随机Wander就随机挂”。 会Wander的蛇确实能多走好多步。可是有一天,它就会把自己给随机到一条死路上了。 陷入困境还可以Wander,进入死胡同,那可没有回滚机制。所以, 第二个版本的Wander函数,我就让贪吃蛇贪到底。在BFS无解后, 告诉蛇一个步数step(随机产生step),让它在空白区域以S形运动step步。 这回运动方向就不随机了,而是有组织有纪律地运动。先看图,然后再说说它的问题:

没错,最终还是挂掉了。S形运动也是无法让贪吃蛇避免死亡的命运。 贪吃蛇可以靠S形运动多存活一段时间,可是由于它的策略是:

while 没有按下ESC键:
    if 蛇与食物间有路径:
        走起,吃食物去
    else:
        Wander一段时间

问题就出在蛇发现它自己和食物间有路径,就二话不说跑去吃食物了。 它没有考虑到,你这一去把食物给吃了后形成的局势(蛇身布局), 完全就可能让你挂掉。(比如进入了一个自己蛇身围起来的封闭小空间)

so,为了能让蛇活得久一些,它还要更高瞻远瞩才行。

高瞻远瞩版本

我们现在已经有了一个比较低端的版本,而且对问题的认识也稍微深入了一些。 现在可以进行一些比较慎密和严谨的分析了。首先,让我们罗列一些问题: (像头脑风暴那样,想到什么就写下来即可)

  • 蛇和食物间有路径直接就去吃,不可取。那该怎么办?
  • 如果蛇去吃食物后,布局是安全的,是否就直接去吃?(这样最优吗?)
  • 怎样定义布局是否安全?
  • 蛇和食物之间如果没有路径,怎么办?
  • 最短路径是否最优?(这个明显不是了)
  • 那么,如果布局安全的情况下,最短路径是否最优?
  • 除了最短路径,我们还可以怎么走?S形?最长?
  • 怎么应对蛇身越来越长这个问题?
  • 食物是随机出现的,有没可能出现无解的布局?
  • 暴力法(brute force)能否得到最优序列?(让贪吃蛇尽可能地多吃食物)

只要去想,问题还挺多的。这时让我们以面向过程的思想,带着上面的问题, 把思路理一理。一开始,蛇很短(初始化长度为1),它看到了一个食物, 使用BFS得到矩形中每个位置到达食物的最短路径长度。在没有蛇身阻挡下, 就是曼哈顿距离。然后,我要先判断一下,贪吃蛇这一去是否安全。 所以我需要一条虚拟的蛇,它每次负责去探路。如果安全,才让真正的蛇去跑。 当然,虚拟的蛇是不会绘制出来的,它只负责模拟探路。那么, 怎么定义一个布局是安全的呢? 如果你把文章开头那张动态图片中蛇的销魂走位好好的看一下, 会发现即使到最后蛇身已经很长了,它仍然没事一般地走出了一条路。而且, 是跟着蛇尾走的!嗯,这个其实不难解释,蛇在运动的过程中,消耗蛇身, 蛇尾后面总是不断地出现新的空间。蛇短的时候还无所谓,当蛇一长, 就会发现,要想活下来,基本就只能追着蛇尾跑了。在追着蛇尾跑的过程中, 再去考虑能否安全地吃到食物。(下图是某次BFS后,得到的一个布局, 0代表食物,数字代表该位置到达食物的距离,+号代表蛇头,*号代表蛇身, -号代表蛇尾,#号代表空格,外面的一圈#号代表围墙)

# # # # # # # 
# 0 1 2 3 4 # 
# 1 2 3 # 5 # 
# 2 3 4 - 6 # 
# 3 + * * 7 # 
# 4 5 6 7 8 # 
# # # # # # # 

经过上面的分析,我们可以将布局是否安全定义为蛇是否可以跟着蛇尾运动, 也就是蛇吃完食物后,蛇头和蛇尾间是否存在路径,如果存在,我就认为是安全的。

OK,继续。真蛇派出虚拟蛇去探路后,发现吃完食物后的布局是安全的。那么, 真蛇就直奔食物了。等等,这样的策略好吗?未必。因为蛇每运动一步, 布局就变化一次。布局一变就意味着可能存在更优解。比如因为蛇尾的消耗, 原本需要绕路才能吃到的食物,突然就出现在蛇眼前了。所以,真蛇走一步后, 更好的做法是,重新做BFS。然后和上面一样进行安全判断,然后再走。

接下来我们来考虑一下,如果蛇和食物之间不存在路径怎么办? 上文其实已经提到了做法了,跟着蛇尾走。只要蛇和食物间不存在路径, 蛇就一直跟着蛇尾走。同样的,由于每走一步布局就会改变, 所以每走一步就重新做BFS得到最新布局。

好了,问题又来了。如果蛇和食物间不存在路径且蛇和蛇尾间也不存在路径, 怎么办?这个我是没办法了,选一步可行的路径来走就是了。还是一个道理, 每次只走一步,更新布局,然后再判断蛇和食物间是否有安全路径; 没有的话,蛇头和蛇尾间是否存在路径;还没有,再挑一步可行的来走。

上面列的好几个问题里都涉及到蛇的行走策略,一般而言, 我们会让蛇每次都走最短路径。这是针对蛇去吃食物的时候, 可是蛇在追自己的尾巴的时候就不能这么考虑了。我们希望的是蛇头在追蛇尾的过程中, 尽可能地慢。这样蛇头和蛇尾间才能腾出更多的空间,空间多才有得发展。 所以蛇的行走策略主要分为两种:

1. 目标是食物时,走最短路径
2. 目标是蛇尾时,走最长路径

那第三种情况呢?与食物和蛇尾都没路径存在的情况下, 这个时候本来就只是挑一步可行的步子来走,最短最长关系都不大了。 至于人为地让蛇走S形,我觉得这不是什么好策略,最初版本中已经分析过它的问题了。 (当然,除非你想使用最最无懈可击的那个版本,就是完全不管食物, 让蛇一直走S,然后在墙边留下一条过道即可。这样一来, 蛇总是可以完美地把所有食物吃完,然后占满整个空间,可是就很boring了。 没有任何的意思)

上面还提到一个问题:因为食物是随机出现的,有没可能出现无解的局面? 答案是:有。我运行了程序,然后把每一次布局都输出到log,发现会有这样的情况:

# # # # # # # 
# * * * * * # 
# * * - 0 * # 
# * * # + * # 
# * * * * * # 
# * * * * * # 
# # # # # # # 

其中,+号是蛇头,-号是蛇尾,*号是蛇身,0是食物,#号代表空格,外面一圈# 号代表墙。这个布局上,食物已经在蛇头面前了,可是它能吃吗?不能! 因为它吃完食物后,长度加1,蛇头就会把0的位置填上,布局就变成:

# # # # # # # 
# * * * * * # 
# * * - + * # 
# * * # * * # 
# * * * * * # 
# * * * * * # 
# # # # # # # 

此时,由于蛇的长度加1,蛇尾没有动,而蛇头被自己围着,挂掉了。可是, 我们却还有一个空白的格子#没有填充。按照我们之前教给蛇的策略, 面对这种情况,蛇头就只会一直追着蛇尾跑,每当它和食物有路径时, 它让虚拟的蛇跑一遍发现,得到的新布局是不安全的,所以不会去吃食物, 而是选择继续追着蛇尾跑。然后它就这样一直跑,一直跑。死循环, 直到你按ESC键为止。

由于食物是随机出现的,所以有可能出现上面这种无解的布局。当然了, 你也可以得到完满的结局,贪吃蛇把整个矩形都填充满。

上面的最后一个问题,暴力法是否能得到最优序列。从上面的分析看来, 可以得到,但不能保证一定得到。

最后,看看高瞻远瞩的蛇是怎么跑的吧:

矩形大小10*20,除去外面的边框,也就是8*18。Linux下录完屏再转成GIF格式的图片, 优化前40多M,真心是没法和Windows的比。用下面的命令优化时, 有一种系统在用生命做优化的感觉:

convert output.gif -fuzz 10% -layers Optimize optimised.gif

最后还是拿到Windows下用AE,三下五除二用图片序列合成的动态图片 (记得要在format options里选looping,不然图片是不会循环播放的)

Last but not least

如果对源代码感兴趣,请戳以下的链接: Code goes here

另外,本文的贪吃蛇程序使用了curses模块, 类Unix系统都默认安装的,使用Windows的童鞋需要安装一下这个模块, 送上地址: 需要curses请戳我

以上的代码仍然可以继续改进(现在加注释不到300行,优化一下可以更少), 也可用pygame或是pyglet库把界面做得更加漂亮,Enjoy!

再议LCS(最长公共子序列)

上次在实验室作《从分治到动归 – 最优问题解法》的讲座的时候,举了LCS(最长公共子序列)作为例子。当时讲的是传统的动态规划解法。下面先提一下这个解法作为铺垫。

LCS问题

LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。

例如:

X={A,B,C,B,D,A,B}

Y={B,D,C,A,B,A}

则X和Y的最长公共子序列(之一)是{B,C,B,A}

传统动归解LCS

设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:

f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}

其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。

初值:f[i][0]=0 f[0][i]=0 f[1][1] = same(1,1)

这个动归方程乍看可能不好理解。它的思想是这样的。

对于已知f[i][j]的值,要往后拓展,有这两种情况:其末位i和j相同,或不相同。

考虑相同情况。因为i和j相同,它们必然已被记入最长公共子序列的部分。此时要想延长这个公共子序列,只得令i和j都向后移,看看它们后一位是否也相同。这就是f[i][j]+same(i+1,j+1)。

而对于不同情况,有这几种可能: 虽然第i和j位不相同,但i和j+1是相同的。此时要想延长,便是f[i][j+1]的情况。当然也可能i+1和j相同,便是f[i+1][j]的情况。

综上,写成递归式,因为不知道前一个状态的情况,所以便在这三种可能中取最大值。此时f[i][j]变为f[i-1][j-1],f[i][j+1]变为f[i-1][j],f[i+1][j]变为f[i][j-1]。便得到了上面的递归式。而初值很好理解,这里就不赘述了。

不难算出,这个算法的时间复杂度是O(n^2),空间复杂度也是O(n^2),但因为状态只与上一行有关,所以可以将空间复杂度优化至O(n)。

另一种解法?(以下内容有误,13/10/25勘误)

网络上还能找到另一种解决这个问题的方法:

(1)将两个字符串分别以行和列组成矩阵。

(2)计算每个节点行列字符是否相同,如相同则为1。

(3)通过找出值为1的最长对角线即可得到最长公共子串本方法只能得到最长连续公共子串,下列讨论关于最长公共子串全部应替换为最长连续公共子串。

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

这个方法非常好理解,直观易懂。而不难发现它的时间复杂度,竟然也是O(n^2),空间复杂度也可以由O(n^2)优化到O(n)!

这是巧合吗?

我们来分析一下这个做法。首先我们能总结出这个方法的递推式:d[i][j]=d[i-1][j-1]+same(i,j)。是不是很眼熟?但和上面的还不大一样啊?缺了两种情况呢。

别急,这个方法还需要在全矩阵中找出最大的值。而上面的动归方程,分散在各个状态求max的过程,合并起来,不就是求全矩阵的最大值吗?这段也有错误。详见下方勘误。

殊途同归!

动归解法通过记录各个不同截取位置的方法,避免朴素解法中的重复比较,从而提升了效率。而这个方法中的矩阵,其作用不难发现,也是一种记录的行为。

思想只存于我们的脑子中,我们的思维使算法发生了变化。但其结果,却殊途同归。

算法,是一种哲学。

2013年10月25日勘误

打造群博2:借助WP-o-Matic实现RSS自动抓取

上一篇我们讲到了关于改造模板使得文章只显示摘要以方便阅读,这一篇我们来讨论下如何基于WordPress来实现自动根据RSS抓取文章的群博功能。

介绍一下这个强大的插件:WP-o-Matic。这是我试了N个不同插件之后唯一能用而且效果还行而且支持中文的RSS抓取插件……它也是一个开源项目,目前的最新版本是2.3.9。
Continue reading “打造群博2:借助WP-o-Matic实现RSS自动抓取”