WindStorm

Android Native 代码NDK开发学习笔记

Sun, 22 Jan 2012 01:49:32 +0800

本文提供排版更佳的PDF版本下载。

JNI，全称Java Native Interface，是用于让运行在JVM中的Java代码和运行在JVM外的Native代码（主要是C或者C++）沟通的桥梁。代码编写者即可以使用JNI从Java的程序中调用Native代码，又可以从Native程序中调用Java代码。这样，编程人员可以将低阶的代码逻辑包装到高阶的程序框架中，获得高性能高效率的同时保证了代码框架的高抽象性。

在Android中，仅有以下类库是允许在JNI中使用的：

libc (C library) headers
libm (math library) headers
JNI interface headers
libz (Zlib compression) headers
liblog (Android logging) header
OpenGL ES 1.1 (3D graphics library) headers (since 1.6)
A Minimal set of headers for C++ support

JNI本身仅仅是一个把两者融合的工具，作为编程者需要做的，就是在Java代码和Native代码中按照固定的格式告诉JNI如何调用对方。在Android中，有两种方式可以调用JNI，一种是Google release的专门针对Android Native开发的工具包，叫做NDK。去Android网站上下载该工具包后，就可以通过阅读里面的文档来setup一个新的包含Native代码的工程，创建自己的Android.mk文件，编译等等；另一种是完整的源码编译环境，也就是通过git从官方网站获取完全的Android源代码平台。这个平台中提供有基于make的编译系统。更多细节请参考这里。不管选择以上两种方法的哪一个，都必须编写自己的Android.mk文件，有关该文件的编写请参考相关文档。

下面通过一个简单的使用例子来讲解JNI。Android给C和C++提供的是两套不同的Native API，本文仅以C++举例说明。假设这么一个需求，Java代码需要打印一个字符串，而该字符串需要Native代码计算生成。对应的JNI流程是这样的：

1. 在准备打印字符串的Android类中，添加两段代码。

第一段是：

private native String getPrintStr();

这一行代码的目的是告诉JNI，这个Java文件中有这么一个函数，该函数是在Native代码中执行的，Native代码会返回一个字符串供Java代码来输出。

第二段是：

try {System.loadLibrary(“LIBNAME” }

catch (UnsatisfiedLinkError ule) {Log.e(TAG, “Could not load native library”);}

这两行代码是告诉JNI，你需要找的所有Native函数都在libLIBNAME.so这个动态库中。注意JNI会自动补全lib和so给LIBNAME，你只需要提供LIBNAME给loadLibrary就行了。在最后执行的时候，JNI会先找到这个动态库，然后找里面的OnLoad函数，具体注册流程由OnLoad函数接管。

关于如何确定这个LIBNAME，和如何定义OnLoad函数，下面就会讲。

2. 上面的第一步是告诉JNI，java代码需要和Native代码交互，同时把在哪里找，找什么都通知了。接下来的事情就由Native端接管。如果把上面的getPrintString函数申明比作原型，那么本地代码中的具体函数定义就应该和该原型匹配，JNI才能知道具体在哪里执行代码。具体来说，应该有一个对应的Native函数，有和Java中定义的函数同样的参数列表以及返回值。另外，还需要有某种机制让JNI将两者相互映射，方便参数和返回值的传递。在老版的JNI中，这是通过丑陋的命名匹配实现的，比如说在Java中定义的函数名是getPrintStr, 该函数属于package java.come.android.xxx，那么中对应Native代码中的函数名就应该是Java_com_android_xxx_getPrintStr。这样给开发人员带来了很多不便。可以用javah命令来生成对应Java code中定义函数的Native code版本header文件，从中得知传统的匹配方法是如何做的。具体过程如下：

通过SDK的方式编译Java代码。
找到Eclipse的工程目录，进入bin目录下。这里是编译出的java文件所对应的class文件所在。
假设包括Native函数调用的java文件属于com.android.xxx package，名字叫test.java，那么在bin下执行javah -jni com.android.xxx.test

执行完后，可以看到一个新生成的header文件，名字为com_android_xxx_test.h。打开后会发现已经有一个函数申明，函数名为java_com_android_xxx_test_getPrintStr。这个名字就包括了该函数所对应Java版本所在的包，文件以及名称。这就是JNI传统的确定名字的方法。

值得注意的是，header文件中不仅包含了基于函数名的映射信息，还包含了另一个重要信息，就是signature。一个函数的signature是一个字符串，描述了这个函数的参数和返回值。其中”()” 中的字符表示参数，后面的则代表返回值。例如”()V” 就表示void Func(); “(II)V” 表示 void Func(int, int); 数组则以”["开始，用两个字符表示。

具体的每一个字符的对应关系如下：

字符	Java类型	C类型
V	void	void
I	jint	int
Z	jboolean	boolean
J	jlong	long
D	jdouble	double
F	jfloat	float
B	jbyte	byte
C	jchar	char
S	jshort	short

上面的都是基本类型。如果Java函数的参数是class，则以"L"开头，以";"结尾，中间是用"/" 隔开的包及类名。而其对应的C函数名的参数则为jobject。一个例外是String类，其对应的类为jstring。举例：

Ljava/lang/String; String jstring

Ljava/net/Socket; Socket jobject

如果JAVA函数位于一个嵌入类，则用$作为类名间的分隔符。例如 "(Ljava/lang/String;Landroid/os/FileUtils$FileStatus;)Z"

这个signature非常重要，是下面要介绍的新版命名匹配方法的关键点之一。所以，即使传统的命名匹配已经不再使用，javah这一步操作还是必须的，因为可以从中得到Java代码中需要Native执行的函数的签名，以供后面使用。

3. 在新版（版本号大于1.4）的JNI中，Android提供了另一个机制来解决命名匹配问题，那就是JNI_OnLoad。正如前面所述，每一次JNI执行Native代码，都是通过调用JNI_OnLoad实现的。下面的代码是针对本例的OnLoad代码：

/* Returns the JNI version on success, -1 on failure.

jint JNI_OnLoad(JavaVM* vm, void* reserved) {

JNIEnv* env = NULL;

jint result = -1;

if (vm->GetEnv((void**) &env, JNI_VERSION_1_4) != JNI_OK) {

LOGE("ERROR: GetEnv failed");

goto bail;

}

assert(env != NULL);

if (!register_Test(env)) {

LOGE("ERROR: Test native registration failed");

goto bail;

}

/* success -- return valid version number */

result = JNI_VERSION_1_4;

bail: return result;

}

分析这个函数。首先，OnLoad通过GetEnv函数获取JNI的环境对象，然后通过register_Test来注册Native函数。register_Test的实现如下：

int register_Test(JNIEnv *env) {

const char* const ClassPathName ＝ "com/android/xxx/test";

return registerNativeMethods(env, ClassPathName, TestMethods,

sizeof(TestMethods) / sizeof(TestMethods[0]));

}

在这里，ClassPathName是Java类的全名，包括package的全名。只是用 “/” 代替 ”.” 。然后我们把类名以及TestMethods这个参数一同送到registerNativeMethods这个函数中注册。这个函数是基于JNI_OnLoad的命名匹配方式的重点。

在JNI中，代码编写者通过函数signature名和映射表的配合，来告诉JNI_OnLoad，你要找的函数在Native代码中是如何定义的（signature），以及在哪定义的（映射表）。关于signature的生成和含义，在上面已经介绍。而映射表，是Android使用的一种用于映射Java和C/C++函数的数组，这个数组的类型是JNINativeMethod，定义为：

typedef struct {

const char* name;

const char* signature;

void* fnPtr;

} JNINativeMethod;

其中，第一个变量是Java代码中的函数名称。第二个变量是该函数对应的Native signature。第三个变量是该函数对应的Native函数的函数指针。例如，在上面register_Test的函数实现中，传给registerNativeMethods的参数TestMethods就是映射表，定义如下：

static JNINativeMethod TestMethods[] = {

{“getPrintStr”, “()Ljava/lang/String”, (void*)test_getPrintStr}

};

其中getPrintStr是在Java代码中定义的函数的名称，()Ljava/lang/String是签名，因为该函数无参数传入，并返回一个String。test_getPrintStr则是我们即将在Native code中定义的函数名称。该映射表和前面定义的类名ClassPathName一起传入registerNativeMethods：

static int registerNativeMethods(JNIEnv* env, const char* className, JNINativeMethod* Methods, int numMethods) {

jclass clazz;

clazz = env->FindClass(className);

if (clazz == NULL) {

LOGE(“Native registration unable to find class ‘%s’”, className);

return JNI_FALSE；

}

if (env->RegisterNatives(clazz, gMethods, numMethods) < 0) {

LOGE(“RegisterNatives failed for ‘%s’”, className);

return JNI_FALSE;

}

return JNI_TRUE;

}

在这里，先load目标类，然后注册Native函数，然后返回状态。

可以看出，通过映射表方式，Java code中的函数名不须再和Native code中的函数名呆板对应。只需要将函数注册进映射表中，Native code的函数编写就有了很大的灵活性。虽说和前一种传统的匹配方法比，这种方式并没有效率上的改进，因为两者本质上都是从JNI load开始做函数映射。但是这一种register的方法极大降低了两边的耦合性，所以实际使用中会受欢迎得多。比如说，由于映射表是一个<名称，函数指针>对照表，在程序执行时，可多次调用registerNativeMethods()函数来更换本地函数指针，而达到弹性抽换本地函数的目的。

4. 接下来本应介绍test_getPrintStr。但在此之前，简单介绍Android.mk，也就是编译NDK所需要的Makefile，从而完成JNI信息链的讲解。Android.mk可以基于模版修改，里面重要的变量包括：

LOCAL_C_INCLUDES：包含的头文件。这里需要包含JNI的头文件。
LOCAL_SRC_FILES: 包含的源文件。
LOCAL_MODULE：当前模块的名称，也就是第一步中我们提到的LIBNAME。注意这个需要加上lib前缀，但不需要加.so后缀，也就是说应该是libLIBNAME。
LOCAL_SHARED_LIBRARIES：当前模块需要依赖的共享库。
LOCAL_PRELINK_MODULE：该模块是否被启动就加载。该项设置依具体程序的特性而定。

5. 至此，JNI作为桥梁所需要的所有信息均已就绪。JNI知道在调用Java代码中的getPrintStr函数时，需要执行Native代码。于是通过System.loadLibrary所加载的libLIBNAME.so找到OnLoad入口。在OnLoad中，JNI发现了函数映射表，发现getPrintStr对应的Native函数是test_getPrintStr。于是JNI将参数（如果有的话）传递给test_getPrintStr并执行，再将返回值（如果有的话）传回Java中的getPrintStr。

6. 用于最后测试的test_getPrintStr函数实现如下：

const jstring testStr = env->NewStringUTF(“hello, world”);

return testStr;

然后在Java代码中打印出返回的字符串即可。这个网页详细介绍了env可以调用的所有方法。

7. 关于测试时使用Log。调用JNI进行Native Code的开发有两种环境，完整源码环境以及NDK。两种环境对应的Log输出方式也并不相同，差异则主要体现在需要包含的头文件中。如果是在完整源码编译环境下，只要include <utils/Log.h>头文件（位于Android-src/system/core/include/cutils），就可以使用对应的LOGI、LOGD等方法了，当然LOG_TAG，LOG_NDEBUG等宏值需要自定义。如果是在NDK环境下编译，则需要include <android/log.h>头文件（位于ndk/android-ndk-r4/platforms/android-8/arch-arm/usr/include/android/），另外自己定义宏映射，例如：

#include <android/log.h>

#ifndef LOG_TAG

#define LOG_TAG “MY_LOG_TAG”

#endif

#define LOGD(…) __android_log_print(ANDROID_LOG_DEBUG,LOG_TAG,__VA_ARGS__)

#define LOGI(…) __android_log_print(ANDROID_LOG_INFO,LOG_TAG,__VA_ARGS__)

#define LOGW(…) __android_log_print(ANDROID_LOG_WARN,LOG_TAG,__VA_ARGS__)

#define LOGE(…) __android_log_print(ANDROID_LOG_ERROR,LOG_TAG,__VA_ARGS__)

#define LOGF(…) __android_log_print(ANDROID_LOG_FATAL,LOG_TAG,__VA_ARGS__)

另外，在Android.mk文件中对类库的应用在两种环境下也不相同。如果是NDK环境下，需要包括

LOCAL_LDLIBS := -llog

而在完整源码环境下，则需要包括

LOCAL_SHARED_LIBRARIES := libutils libcutils

8. 如果希望知道如何在Native中访问Java类的私有域和方法，请参考这篇文章

也许你还会对这些文章感兴趣

2011-12-21 — 一个新的开源项目Libsvm-androidjni (5)
2011-12-06 — Hackborn的吐槽和Munn的剖析: Android graphics低性能背后的真像 (5)
2011-12-04 — 谈谈Android 4.0 (11)
2011-11-17 — 如何对Android的本地代码进行profiling (0)
2011-01-20 — 聊聊电脑性能测试的演变–看Android评测有感 (0)
2010-09-29 — Android上Tcpdump的使用 (0)
2010-07-18 — Samsung Galaxy S上手感受 (6)
2010-06-18 — Gingerbread，向左走还是向右走？ (5)
2010-06-09 — Android机器人T-shirt情侣衫照 (6)
2010-05-31 — Android并不伟大，但丝毫不令人沮丧 (6)
2010-02-11 — 目前最好的Android2.1 ROM之一 for Hero (4)
2010-01-23 — 彩色的Android debugging logcat term (0)

visit the website for more great content.

一个新的开源项目Libsvm-androidjni

Wed, 21 Dec 2011 15:29:03 +0800

我创建了一个关于libsvm库+Android的开源项目 Libsvm-androidjni.

这个项目的目的是让当今最流行的SVM支持向量机机器学习库Libsvm被移植到Android平台中。当然官方提供了Java库，但用Java来进行大规模的SVM计算还是太低效了，所以这个项目是要把c/c++版本的库移植到JNI环境下。

目前的code状态是svm的training和prediction功能皆可正常运行。具体的使用方式请参考README。虽然是c++环境，但主体code还是c的风格，这和我个人喜好有关，不影响使用。

目前还有一些高级功能不完善，比如完整的参数传递和误差计算。

项目代码请到https://github.com/cnbuff410/Libsvm-androidjni下载。

也许你还会对这些文章感兴趣

2011-11-17 — 如何对Android的本地代码进行profiling (0)
2011-08-21 — Android Native 代码NDK开发学习笔记 (2)
2011-12-06 — Hackborn的吐槽和Munn的剖析: Android graphics低性能背后的真像 (5)
2011-12-04 — 谈谈Android 4.0 (11)
2011-01-20 — 聊聊电脑性能测试的演变–看Android评测有感 (0)
2010-09-29 — Android上Tcpdump的使用 (0)
2010-07-18 — Samsung Galaxy S上手感受 (6)
2010-06-18 — Gingerbread，向左走还是向右走？ (5)
2010-06-09 — Android机器人T-shirt情侣衫照 (6)
2010-05-31 — Android并不伟大，但丝毫不令人沮丧 (6)
2010-02-11 — 目前最好的Android2.1 ROM之一 for Hero (4)
2010-01-23 — 彩色的Android debugging logcat term (0)

visit the website for more great content.

输入数学公式的Chrome应用推荐

Thu, 15 Dec 2011 13:53:51 +0800

我曾经写过的一篇博客是在blog中用LaTex输入数学公式。里面提到过“在线生成的方法”，并推荐了几个网站。今天在Chrome应用商店里发现了一个应用叫Daum Equation Editor，非常非常好用，界面漂亮，选项众多，支持字体特效和大小的调整，输出图片或者latex文字。基本上秒杀我那篇文章里推荐的那些软件。所以在这里再推荐一下:)

Random Posts

visit the website for more great content.

Hackborn的吐槽和Munn的剖析: Android graphics低性能背后的真像

Tue, 06 Dec 2011 16:26:33 +0800

Google+上有意思的讨论从未间断，几乎已是Google+的标志性特色了。最近两天，移动领域的爱好者都被Dianne Hackborn的一则吐槽所吸引。吐槽要火，两大因素不可缺少，一是该话题乃众人关注，却无统一意见。二是吐槽中有大料或者干货爆出，引人入胜。此番吐槽吸引人的地方，正是因为此吐槽是关于饱受争议的Android graphics性能的，自从Android推出的第一天起，graphics的渲染，动画切换等就为人诟病，到后来几乎成了果粉安粉大战的必备话题。而吐槽之人呢？是Android团队中比较senior的架构工程师Dianne Hackborn，相信关注Android开发的朋友，都不会对此女陌生。

为什么Dianne Hackborn身为Android内部人士，会突然公开讨论如此敏感的一个话题呢？用她自己的话说，就是“受够了外界谣传的关于Android图形渲染的不实信息”。我把她吐槽的大概重点归纳如下：

1. 外界盛传，Android图形渲染一直不支持硬件加速，直到3.0才开启此特性。我也一直深信此观点。其实，从最初起，Android就一直支持硬件加速图形窗口，比如你看到的所有比如菜单的出没，activity之间的切换，对话框的弹出等。

2. 但Android却是用软件来渲染窗口里面的内容的。如果屏幕上有多个窗口呈现，其中一个窗口的内容需要重新绘制，那么其他窗口不会变化，而改变化的窗口的重新构成还是通过硬件加速，只不过其中变化的内容，却是软件绘制了(不好意思插一句。Redraw!!!!!Android开发者现在应该知道这多么坑爹了吧）。虽然说是软件绘制，却不一定就表示会卡。卡不卡，是由绘制频率和刷新率是否匹配所决定的，比如手机频的刷新率是60fps，但你的渲染率是50fps，双方不同步，自然就会有停顿的感觉产生。如果用软件做这个任务，做得好不好，这个取决于显示屏上的像素数量以及你CPU的能力。比如同样的渲染，Nexus S即使在800×480也不会有问题，而最老的Moto Droid如果也是这样的屏幕，就会力不从心。

3. “完全”的硬件加速，已经在Android 3.0中就支持了，也就是说，即使是窗口内容的渲染也是硬件做的。Android 4.0并没有比3.0有更多的加速能力。4.0的改进，仅仅是默认所有app都使用硬件加速了，而不是像3.0那样开发者还需要指定android:handwareAccelerated=”true”这个选项。然而，完全启用硬件加速的代价是，程序内存占用会严重增多，反而会导致别的方面，比如程序切换，变慢。正因为这样，在将ICS移植到Nexus S时，Google强制关闭了硬件加速选项，保证整个系统的流畅运行。

4. 人们经常比较的网页浏览的性能，iOS总是比Android好很多，但这个和硬件加速渲染是无关的。在Android中，网页是被当作list而不断在屏幕上渲染的，而iOS用的则是tile贴图。list的好处是你不会在放大缩小或者上下滑动时看到还没来得及绘制的tile，但这却大大增加了渲染frame rate的难度。所幸的是，从3.0开始，Android也使用了tile的渲染，所以之后的设备不会再有这种性能缺陷（在我的GN上是明显感觉出来了进步）。

她的吐槽还有很多内容，但大意就是这些。有兴趣的朋友可以直接点击那个链接过去看。总的来说，问题就是Android是一直都有硬件加速的，可惜这个加速仅仅是用于服务那些微不足道或者不重要的东西的—窗口的切换这些。真正和application相关的内容渲染却都是软件在做。这就是为什么iPhone永远感觉都比Android快的原因。iPhone一切的UIView都是Core Animation支持的，而Core Animation又是GPU支持的。更关键的是，iPhone的Core Animation是在不同的线程上run的，和用户正在做的操作是隔离的，所以动画效果会严格按照schedule的去产生，完全没有迟钝感。

Dianne Hackborn的这个吐槽引起了很大的影响，其中一位前Google的实习生，即将去Windows Phone开发组的Andrew Munn，也因此发表了其对此的看法。Munn强调，这些技术细节都不重要，用户关注的就是你卡不卡。作为一个长期服侍果粉LD的人，我对此深表同意。Munn也针对这个性能问题提出了不少技术看法，可惜其中有不少低级错误。我总结一些我觉得是对的吧：

1. 所有app硬件加速，如Dianna所说，不是万能良药。但是，至少如ICS所表现，确实解决了很多问题。Munn的Nexus S在运行ICS后流畅度大为增加，而从我使用Galaxy Nexus的情况看，完全不是和以前的Android一个等级的。特别是桌面环境（很多widget的情况下）和Android market。Munn还指出，硬件加速能帮助电池的使用长度。

2. 垃圾回收机制虽然已经并行化了，但还是需要改进。最明显的就是Android上的gallery app。如果你在使用gallery时，会发现frame rate很低的情况，这是因为Android将其限制到了30fps。为什么？因为如果你浏览60fps的照片，偶尔会出现垃圾回收引起的停顿，严重影响使用体验。

3. Java, Dalvik。这个问题相信所有开发者都有体会。作为Java痛恨者之一，我很早就做过论断，只要Android坚持java一天，系统效率就会落后iOS一天。如果你尝试过Android NDK的开发，你会发现，区别是多么惊人。

4. Android的UI问题是一个历史遗留问题。在目前市场上所有的移动系统里，Android是唯一一个早于iPhone推出之前就开始开发的，而且当时针对的是黑莓，非触摸屏机。所以，UI框架也有着不可原谅的遗留问题：UI的渲染是在主线程进行的，animation是由UI管的。而且UI没有任何优先级。之后，全新的WebOS, Win 7等都针对触摸操作而学习iOS的UI处理，只有Android没有，也无法推到重来。

如果你好奇为什么Google很难推到现在UI的框架重来，原因不外乎就是这几个：所有的app都需要重写。老旧而没升级的app无法兼容。在UI新框架ready之前，所有Android的特性都无法继续进行改进。

是的，Android有很多很强大的特性，比如widget，比如动态桌面，比如完全多进程。这些特性带给我们强大的体验，同时也增加了UI的负担，反过来成了Android一道长久的伤疤，而这个伤疤，即使是硬件再强大，也很难磨灭。作为一个长期使用iPhone的Android爱好者，UI是我之前一直无法忍受Android日常使用的第一原因。当然，正如我前一篇介绍Android4.0的文章提到，ICS是在这个方面的一个巨大进步。它能和iOS比肩了么？还不能。但它让Android从在万米长跑中落后100米，变为了落后20米。Munn和我对Google都有同样的印象，那就是：速度，在Google里永远是第一目标。Google有很多人，他们都对”lag”这个东西极度痛恨，对“速度”的追求永无停止。看看search，看看Gmail，看看Chrome，你就明白了。我不知道Android team能否最后找到不需要重写就能解决UI问题的方法，但以我对Android team的工作精神，能力以及管理（这个话题要展开可以另写一篇文章，但总的来说我觉得Android是Google内部管理最好的团队之一）的了解，我相信Android迟早会达到这个目标的。也许就在今年6月。

也许你还会对这些文章感兴趣

2011-12-04 — 谈谈Android 4.0 (11)
2011-12-21 — 一个新的开源项目Libsvm-androidjni (5)
2011-11-17 — 如何对Android的本地代码进行profiling (0)
2011-08-21 — Android Native 代码NDK开发学习笔记 (2)
2011-01-20 — 聊聊电脑性能测试的演变–看Android评测有感 (0)
2010-09-29 — Android上Tcpdump的使用 (0)
2010-07-18 — Samsung Galaxy S上手感受 (6)
2010-06-18 — Gingerbread，向左走还是向右走？ (5)
2010-06-09 — Android机器人T-shirt情侣衫照 (6)
2010-05-31 — Android并不伟大，但丝毫不令人沮丧 (6)
2010-02-11 — 目前最好的Android2.1 ROM之一 for Hero (4)
2010-01-23 — 彩色的Android debugging logcat term (0)

visit the website for more great content.

谈谈Android 4.0

Sun, 04 Dec 2011 13:15:16 +0800

昨天刚拿到Galaxy Nexus，把玩了差不多一天了。这篇文章并不想花大篇幅介绍这款机器的硬件和软件，如果你好奇，可以看一下下面这些知名网站的评测，再详细不过了

Engadget
The Verge: 8.6/10（和iPhone4s同分）
SlashGear
Boy Genius Report
TechRadar
PhoneArena: 9.5/10
GigaOM:一个iPhone用户的评测
Gizmodo
GigaOM

如果真要总结，那只有一句话，这是Android有史以来第一款能和苹果手机并肩的机器。这篇文章里，我就谈谈，在我眼里，Android的后续发展，和ICS的意义，当然都是结合了我在Google４个月的所见所闻以及感想。很多朋友希望看到我有一篇专门的实习总结，我想了想还是算了，首先我实习做的东西比较保密，没法说，其次也没什么写的，Google工作环境好，条件好，牛人多，大家都知道，没必要再吹一次。

很多人都觉得我是Google粉，因为我一直在鼓吹Android，而且还机缘巧合算是在Android团队里做过实习。但我想辩解的是，我是Google服务爱好者，但我确实不是fanboy。那为什么我要“鼓吹”Android？因为它geek，和我一样。它开源，给你随便折腾，随便改。难道你就未曾想尝试过在自己的手机上跑自己编译甚至修改的操作系统？Hell，那你根本就算不上一个geek。实际生活中，如果要说我是什么fans，我是“好东西”fans。我用Google的服务，Gmail, Gmap, Chrome，是因为它们确实好用。我也用iMac和MBA，是因为它们确实好用。朋友找我推荐手机，我都是仔细询问需求，然后大部分情况下都是推荐了iPhone。迄今为止，我用了一年半的iPhone4。如果你到我家来一趟，你肯定会给我贴上”Apple fanboy”的标签。因为我家苹果的东西太多了。

我只是喜欢用最好的东西而已。

那也许有人问，你既然用苹果，为啥还分析Android？有没有credit？我觉得我有。你要问我用过多少Android做开发，我估算一下不下十种。从最早的G1 Dream，到最新的Galaxy S2。每一款机器，我都会插进我的sim卡用一段时间，亲身感受。即使有时不是随身携带，因开发关系，也会深入了解系统。

我曾经写过两篇关于Android发展的文章。在”Android并不伟大，但丝毫不令人沮丧“一文中，我提到五点：

1. Android会越来越多地和云服务结合，并逐步融合Chrome OS的思想。
2. Android必须免费。一旦有强大定制化的开源系统，高度统一的收费系统就没法统治整个消费电子领域。
3. Android绝对不能被单方控制。
4. SNS和移动网络融合是一个趋势，也是目前没有明显强势选手的领域，Android能不能把握这个趋势，加入一些创新的元素，决定了Android是不是能继续保持和iPhone争锋的势头。
5. Google不能完全进入手机硬件市场。为什么说Android令人沮丧一文提出的Google收购Moto的建议，不客气地说，从目前Android发展阶段看，实在是馊主意。

1这一点Android是越做越好，以Google Music为代表。2,3也是没问题的，4则是以Google+为代表。有意思的是5。应该说，我至少错了一半。是的，Google收购Moto了，而且就是为了Android。但是为什么我说我可能只错了一半呢？我在那篇文章里面还提到：

“Android的定位已经悄然起了变化，这个变化，以家居电子厂商和汽车电子厂商纷纷表示对Android的兴趣或者直接推出对应产品为起点，以Google TV的推出为标志，彻底公开在了人们面前：Android已经从一个移动设备操作系统，变成了一个消费电子设备操作系统。”

很明显，这也是苹果下一个扩展领域。对于Android来讲，Android@Home和Google TV的更新是一个明显的信号。当然，对于消费电子，特别是家庭电子，该领域太大太广，厂商众多，Google想分一杯羹谈何容易。如果所有的领域都需要别的硬件厂商的鼎力支持，有些领域可能完全就没机会打进去。何况有时候，别的硬件厂商完全就不靠谱，比如Sony做的Google TV。你会用么？反正我不会。所以，从这个层面上讲，Google收购的不是Moto的手机能力，而是硬件能力。有了Moto，Google可以做各种各样的硬件创新，并以此打入完全陌生的领域。

那么这个收购在手机领域有什么影响呢？我不知道。而且当时大部分Googler也不知道，这也是Google内部问得最多的问题。我感觉肯定有影响，只是该影响可能在2-3年后太能体现。短时间内，Google肯定还是会一碗水端平，甚至会稍微照顾别的厂商一些。

我在那篇文章里面有没有完全错误的论断呢？有。我说“Android只是Google的一个棋子。Android对于Google来说，是冗长战线上的一个坦克而已”。这个论断是完全错误的。Android对于Google来说，不是一个冗长战线上的坦克，而是一个王牌军。Google很清楚移动领域的未来，也很清楚它应该有多少资源投进Android。任何担心Android的地位会受哪怕一点点Chrome OS威胁的人，都是杞人忧天。Android会借鉴别的东西，但Android一直会是Android，Google在移动时代的王牌之一。

在写完此文不久，我就写了另一篇文章，”Gingerbread，向左走还是向右走？“。我在其中提到了一个观点：

今天网上广为流传的消息，是来自TechCrunch的，Android团队正在努力解决用户体验的问题。伴随而来的，是Google正在考虑停止厂商自定义UI的权利，包括Sense UI、Moto Blur、Ninja Blur等等。一旦消息属实，我们假设Android真的限制了UI的定制权利，其他厂商如果生产Android手机，必须使用原生UI，那么造成的结果是什么样的？我会说，Android很可能会大败给苹果，而且连智能手机市场老二位置都占不了。

直到今天，我认为这在当时发展情况下，也是无比正确的论断(汗)。为什么？当时的Android太丑了。我想象不出任何一个非Geek，在看到原生Android UI和iOS的UI后，会不选择后者。接下来，我分析了对于Google的可行策略：

因为还有另外一种可能性，就是Google只限定底层的Framework不能更改，第三方手机制造商还是可以在系统里加入自己的预置功能，把系统改为自己希望改为的UI。我不希望看到自定制界面的灭亡，我只希望看到自定制界面的系统也能和原生系统一样，一起升级。

除非，除非Gingerbread的UI有着超级大变身一般的升级，一下子让其他所有第三方UI完全失色，甚至超过苹果。这个幅度基本等于从赛亚人直接变身为超级赛亚人之三的幅度，换句话说，基本不可能。否则，否则Google必须想出某种办法，在改进UI体验的同时，尽可能少地牺牲Android开源的特性，让别的厂商没有退出不做的打算。是的，Moto在搞自己的系统，Samsung在搞自己的系统，HTC很可能搞自己的系统，但是没关系，Google只需要保证Android比他们都好一截，那么他们仍然会帮Android占领市场份额——反正是免费的。还是那个观点，Google不需要争第一，Google只需要让自己一直不断渗透这个市场，让市场没有明显的一家独大，就可以了。

至于Google如何保证Android比这些硬件厂商的OS都好一截，这个的可能性还是很大的。

同样，到现在，我认为当时的这个推测非常正确。Google的后续系统正是按照这个轨迹发展的。唯一的偏差是两点

1. Gingerbread没有达到我的期望，虽然有改进，还是很丑，还是不流畅。Honeycomb终有巨大改进，可惜非通用系统。

2. ICS完全做到了这个预测，甚至基本已经达到变身超级塞亚人2.5的地步了。

到现在，话题终于和本篇文章的标题关联了。是的，这就是我对ICS的评价：基本可以和iOS并驾齐驱了。无论什么方面，设计，速度，操作感，灵魂。人们总是说，Android就是喜欢搞军备竞赛，不管什么硬件，系统还是那么丑那么烂那么卡那么多Bug。ICS推出之日，即是该说法消亡之时。

读到这里，有些朋友可能要说了，太明显的android fanboy的言论。其实如果你看过我一年前的Galaxy S评测，或者更早关于hero的文章，就知道，我的blog评测都是尽量客观的。那我就简单归纳一下，是什么让我有此感受的。

1.　快，流畅。ICS终于支持GPU加速了。我不知道是什么导致Android到今天才完全拥抱此特性(3.0算半个支持），但幸运的是，终于支持了。如果你曾经在Android和iPhone上都用过twitter的话，你一定能留意出两者scroll时流畅的区别。这个区别一去不复返了。用ICS，任何时候你都能感觉到流畅，流畅，流畅。动画切换也好，scroll也好，不管在哪里。靠，连语音输入识别都那么流畅。我相信它不会比iPhone 4s“更流畅”，但至少是“一样流畅”。

2. 漂亮。天阿，这是两年来第一款让我称赞操作系统漂亮的Android手机。我不知道GN上这个无以伦比的屏幕会不会加点分，我只知道，现在的系统，一切看着都是舒服的，而不是让人皱眉。精致的图标，优雅的切换。我在各种不同的界面中都用它和LD的iPhone 4比较，可以说各有千秋，再无巨大区别。不用多说，我就简单上两个图比较。这是国内bbs.gfan.com论坛一位网友照的Galaxy S2和Galaxy Nexus设置界面的区别：

这是著名AndroidPolice网站评测图中的一张

你现在可以想象到为什么很多以Android为日常用机的朋友都会谴责界面了。

顺带说一句，如果你是已有Android用户，希望知道更多ICS 界面的翻天覆地变化，可以看看Android Police推出的getting-to-know-android-4-0系列。不会让你失望的。

3.　直观。一个操作系统，流畅和漂亮是外在，直观的操作是核心。应该说，论直观性，ICS目前还是不如iOS。但和之前的Android版本比，确已经有了一个巨大的进步。用手势来remove进程，网页，通知，用手势来翻页。大幅度减少menu的使用，widget大小的自定制，等等等等。当你真正用的时候，你会发现，很多时候你想的是“早就应该这样了”

4. 所有自带的Google服务软件完全超越其他所有平台。是的，我是说所有。Gmail, Gmap, Gvoice, Calendar, Google+, GMusic, you name it. 如果你是重度Google用户，你一旦用上，就不会再想离开这个天堂。Gmail和Gmap这些app，用起来纯粹是一种享受。更强的功能，更清新的界面，更直观的选项，更快捷的手势。

5. 当Google说，他们会帮你同步手机上的everything时，它们真的是这么做的。如果你是之前Android手机用户的话，在同步完GN之后，不仅仅是你之前手机所有的apps，widgets，联系人信息都有，还同步了所有的墙纸，相片簿，以及网页里的bookmark和历史。是的，一切同步。你打开手机即可使用。

6.　其他本来优势功能的继续增强。比如notification，widget，语音输入这些本来和iOS比就有优势的东西，现在的优势更大。之前一般的输入法也变得非常准确。还有有趣的头像解锁。更有意思的是，Cook刚在iPhone 4s发布会上讽刺了Android手机照相时间，ICS立刻推出了秒杀所有平台的即拍即得特性。连全景照相也是官方内置了。论算法的强大，Google还是不遑多让。

如果你要问，难道这个系统就没有什么缺点么？有。某些小地方还是不够consistent，还有，还有，还有…….hell, 对于喜欢Android的人来说，真没了……是，GN有一些缺点，比如相机质量一般，屏幕费电。但对于ICS……对不起，我真的找不出什么明显的缺陷了。

那和iOS5比呢？

那就得加上一个大缺陷：专门为ICS优化的app还是太少。不过这点在接下来的几个月中会大有改观。ICS不是Gingerbread，不是Honeycomb，它是unified system，也就是说，手机可用，平板可用，笔记本可用，冰箱可用，X86可用，ARM可用，连桌面电脑的显示屏都能正常显示。换句话说，人们只需要开发核心程序一次，然后用不同的界面配置，就可以让app运行在不同硬件上。加上ICS本身的巨大改进，开发者会蜂拥而来，做ICS oriented的app的。

这是第一款，让我能彻底放弃我的iPhone 4并且没有丝毫回头之意并且还能欣赏其带来的新东西的手机。第一款。Jobs推出iPhone 1的时候说过，苹果领先别的系统至少5年。他又对了，今年是第五年。Android终于赶上了，从ICS开始。

让我们期待Android和iOS从今往后的精彩战争吧。竞争，永远是对用户最好的事情。

*************************************我是分割线*********************************************

一个题外话。还有朋友曾经问我用过Win7没有。

我用过。

感觉如何？

不错。简洁流畅。不是很喜欢它的UI风格，但这是个人偏好。有希望在市场开辟另一片天。

为什么不写一些关于它的想法？为什么每次都拿iOS和Android比？

恩……不好意思，我对微软怨念太深了。所有关于微软产品的文章，让我写出来最后估计3/4篇幅都是关于微软的吐槽。

也许你还会对这些文章感兴趣

2011-12-06 — Hackborn的吐槽和Munn的剖析: Android graphics低性能背后的真像 (5)
2011-12-21 — 一个新的开源项目Libsvm-androidjni (5)
2011-11-17 — 如何对Android的本地代码进行profiling (0)
2011-08-21 — Android Native 代码NDK开发学习笔记 (2)
2011-01-20 — 聊聊电脑性能测试的演变–看Android评测有感 (0)
2010-09-29 — Android上Tcpdump的使用 (0)
2010-07-18 — Samsung Galaxy S上手感受 (6)
2010-06-18 — Gingerbread，向左走还是向右走？ (5)
2010-06-09 — Android机器人T-shirt情侣衫照 (6)
2010-05-31 — Android并不伟大，但丝毫不令人沮丧 (6)
2010-02-11 — 目前最好的Android2.1 ROM之一 for Hero (4)
2010-01-23 — 彩色的Android debugging logcat term (0)

visit the website for more great content.

如何对Android的本地代码进行profiling

Thu, 17 Nov 2011 02:42:45 +0800

现在用Android native code写程序库的人越来越多。对于那些需要写的库实时性要求特别强的应用，通过profiling来进行优化是一个非常有用的特性，因为它能帮你理解程序编译后的本质，比如多少instruction，哪些method调用多少次，多长时间，等等。

Android开发环境提供了Traceview这样一个工具，可以点到这个链接里面去看官方对他的介绍。总的来说，就是它提供给程序开发者目标程序的执行日志，以此帮助你调试程序和优化性能。有两种方法能够声称traceview所需的log，一种是利用DDMS的profiling特性，通过控制什么时候开始和结束logging来获得log。这个方法在你没有程序源代码的时候有用，因为只需要Run程序就能获得log信息，但是没有精准的起始中止控制。另一种是通过将Android自带的Debug类加到code中，然后调用里面的method来开始和中止trace信息的纪录。这个方法能让开发者非常精准地控制什么时候开始纪录，什么时候结束纪录，因为开始和技术都是在code中执行的。

对于Java程序来说，官方网页介绍了一个标准流程，就是在程序中引入Debug类，然后在你想要开始纪录profiling信息的时候调用startMethodTracing()，然后在准备结束的时候调用stopMethodTracing()方法。纪录的log文件默认放在sdcard中。

然而对于本地native代码，该方法就无效了。原因是这个方式只能trace你的java层的方法和其对Android API的调用，却无法trace Android API背后的那些方法，也无法trace你自己写的native code。如果你希望trace这些更底层的代码，就需要用Debug类提供的Debug.startNativeTracing()和 Debug.stopNativeTracing()。而且，这个配对只能工作的虚拟机emulator中，因为只有trace qemu emulator，才能去trace每一个进程的每一条cpu指令，甚至包括内核的代码，我们也才能获得更多的信息比如context switch，cache misses。

下面就来看看，利用该方法对来profile native code是怎样一个流程：

1. 新建一个Android Virtual Device，给一个名字，比如Profile。可以在AVD manager中创建。

2. 在命令行中通过命令”emulator -avd -trace
” 来运行该AVD。比如emulator -avd Profile -trace myTrace。

3. 将startNativeTracing()和stopNativeTracing()添加到你想profile的代码中。

4. 在Eclipse中build代码，确保没有错误。安装到正在运行的AVD中。

5. 去AVD中运行代码，确保你希望trace的代码段正常运行了。如果你观察运行AVD的那个terminal的窗口，应该会有比如“–start tracing–” 和 “–stop tracing–”这样的消息出现，这就说明代码正常运行了。

6. App运行完毕后，退出emulator。

7. 去你的用户目录找trace文件。这个目录是存储你AVD settings的目录，默认一般都在/Home/User/.android/avd/下。这个User是你自己的用户名，如果你是用的Mac或者Linux，这个路径也就是~/.android/avd。

8. 找到和你AVD名字对应的文件夹，里面有另一个子文件夹，命名就是你的trace名字，比如这里就是myTrace。里面的文件包括：

qtrace.bb
qtrace.exc
qtrace.insn
qtrace.method
qtrace.pid
qtrace.static

9.你需要用tracedmdump这个工具来将这些文件转化为符合Traceview格式的文件。问题在于，坑爹的Android SDK/NDK环境不原生提供这个工具。所以……..请看下一步

10. 好吧，这个工具来自于Android的源代码环境。那我们需要做的，就是下载整个Android源代码，编译。这个过程通常会持续……一个小时以上。请参考官方手册来进行编译。如果你使用的是Linux，恭喜你，什么别的资料都不用找，就一步一步按照手册来就行了。如果你是Mac用户……哥们，还是按照官方手册来吧，但过程就听天由命了。

11. Okay，假设到这里，你已经完成了整个Android源代码的编译。接下来，在源代码的根目录下运行“source build/envsetup.sh”，然后将根目录下的/out/host/xxxx/bin加到PARH路径中。xxx表示你的编译平台。这下你就可以run tracedmdump了。开一个终端，执行“tracedmdump ~/.android/avd/Profile/myTrace/”，tracedmdump去分析刚才那些五花八门的二进制文件，挖掘里面的symbolic信息，然后将其和trace数据对应。等一小会，就可以得到instruction的信息，并会生成一个更详细的包括所有profiling信息的html文档，这个文档和Traceview兼容的，可以直接打开，也可以用Traceview工具分析。

这样，整个profiling过程就结束了。需要注意一点的是，这个方法和method tracing比有一个局限，就是因为工作在真实设备上，所以emulator不能模拟所有的真实设备效果，比如memory contention和bus contention，同时也无法模拟真实的cache效果，因为emulator中的cache设计是大大简化了的。

也许你还会对这些文章感兴趣

2011-12-21 — 一个新的开源项目Libsvm-androidjni (5)
2011-12-06 — Hackborn的吐槽和Munn的剖析: Android graphics低性能背后的真像 (5)
2011-12-04 — 谈谈Android 4.0 (11)
2011-08-21 — Android Native 代码NDK开发学习笔记 (2)
2011-01-20 — 聊聊电脑性能测试的演变–看Android评测有感 (0)
2010-09-29 — Android上Tcpdump的使用 (0)
2010-07-18 — Samsung Galaxy S上手感受 (6)
2010-06-18 — Gingerbread，向左走还是向右走？ (5)
2010-06-09 — Android机器人T-shirt情侣衫照 (6)
2010-05-31 — Android并不伟大，但丝毫不令人沮丧 (6)
2010-02-11 — 目前最好的Android2.1 ROM之一 for Hero (4)
2010-01-23 — 彩色的Android debugging logcat term (0)

visit the website for more great content.

小波变换和motion信号处理（二）

Wed, 19 Oct 2011 01:26:21 +0800

这是《小波变换和motion信号处理》系列的第二篇，深入小波。第一篇我进行了基础知识的铺垫，第三篇主要讲解应用。

在上一篇中讲到，每个小波变换都会有一个mother wavelet，我们称之为母小波，同时还有一个father wavelet，就是scaling function。而该小波的basis函数其实就是对这个母小波和父小波缩放和平移形成的。缩放倍数都是2的级数，平移的大小和当前其缩放的程度有关。

还讲到，小波系统有很多种，不同的母小波，衍生的小波基就完全不同。小波展开的近似形式是这样：

其中的就是小波级数，这些级数的组合就形成了小波变换中的基basis。和傅立叶级数有一点不同的是，小波级数通常是orthonormal basis，也就是说，它们不仅两两正交，还归一化了。

我们还讲了一般小波变换的三个特点，就是小波级数是二维的，能定位时域和频域，计算很快。但我们并没有深入讲解，比如，如何理解这个二维？它是如何同时定位频域和时域的？

在这一篇文章里，我们就来讨论一下这些特性背后的原理。

首先，我们一直都在讲小波展开的近似形式。那什么是完整形式呢？之前讲到，小波basis的形成，是基于基本的小波函数，也就是母小波来做缩放和平移的。但是，母小波并非唯一的原始基。在构建小波基函数集合的时候，通常还要用到一个函数叫尺度函数，scaling function，人们通常都称其为父小波。它和母小波一样，也是归一化了，而且它还需要满足一个性质，就是它和对自己本身周期平移的函数两两正交：

另外，为了方便处理，父小波和母小波也需要是正交的。可以说，完整的小波展开就是由母小波和父小波共同定义的。

其中是母小波，是父小波。需要提醒一点的是，这个正交纯粹是为了小波分析的方便而引入的特性，并不是说小波变换的基就一定必须是正交的。但大部分小波变换的基确实是正交的，所以本文就直接默认正交为小波变换的主要性质之一了。引入这个父小波呢，主要是为了方便做多解析度分析（multiresolution analysis, MRA）。说到这里，你的问题可能会井喷了：好好的为什么出来一个父小波呢？这个scaling function是拿来干嘛的？它背后的物理意义是什么？wavelet function背后的物理意义又是什么？这个多解析度分析又是什么呢？不急，下面，我们围绕一个例子来巩固一下前面的知识，同时再引出新的特性。

假设我们有这样一个信号：

该信号长度为8，是离散的一维信号。我们要考虑的，就是如何用小波将其展开。为了方便讲解，我们考虑最简单的一种小波，哈尔小波。下面是它的一种母小波：

那如何构建基于这个母小波的基呢？刚才提到了，要缩放，要平移。我们先试试缩放，那就是ψ(2n)：

但这样的话，它与自己的内积就不是1了，不符合小波基orthonormal的要求，所以我们要在前面加一个系数根号二，这样我们就得到了另一个哈尔小波的basis function：

同理，我们可以一直这样推广下去做scale，得到4n，8n，…….下的basis function。当然在这个例子里，我们信号长度就是8，所以做到4n就够了。但推广来说，就是这种scaling对母小波的作用为，这是归一化后的表示形式。

平移的话也很简单，我们可以对母小波进行平移，也可以对scale之后的basis function进行平移。比如对上一幅图中的basis function进行平移，就成了

看得出来，平移后的basis function和母小波以及仅仅scale过的小波，都是正交的，附合小波basis的特点。如果我们用ψ(n)来表示这个mother wavelet，那么这些orthonormal basis函数可以写成：

这里的k是可以看成时域的参数，因为它控制着小波基时域的转移，而j是频域的参数，因为它决定了小波基的频率特性。看到这里，你应该会感觉很熟悉，因为这里的平移和变换本质和刚才对scaling function的平移变换是一模一样的。

这样，我们就有了针对此信号space的哈尔小波basis组合：

图1

可以看出，我们用到了三层频率尺度的小波函数，每往下一层，小波的数量都是上面一层的两倍。在图中，每一个小波基函数的表达形式都写在了波形的下面。

等等，你可能已经发现了，有问题。这里为什么多了个没有函数表达式的波形呢？这货明显不是wavelet function阿。没错，它是之前提到的scaling function，也就是父小波。然后你可能就会问，为啥这个凭空插了一个scaling function出来呢？明明目标信号已经可以用纯的小波基组合表示了。是，确实是，就算不包括scaling function，这些小波函数本身也组成了正交归一基，但如果仅限于此的话，小波变换也就没那么神奇的功效了。引入这个scaling function，才能引入我们提到的多解析度分析的理论，而小波变换的强大，就体现在这个多解析度上。那在这里，我们怎么用这个多解析度呢？这个哈尔小波basis组合是怎么通过多解析度推导出来的呢？

话说在数学定义中，有一种空间叫Lebesgue空间，对于信号处理非常重要，可以用L^p(R)表示，指的是由p次可积函数所组成的函数空间。我们在小波变换中要研究的信号都是属于L^2(R)空间的，这个空间是R上的所有处处平方可积的可测函数的集合，这样就等于对信号提出了一个限制，就是信号能量必须是有限的，否则它就不可积了。小波变换的定义都是基于但不限于L^2(R)中的信号的。这玩意的特性要具体解释起来太数学了，牵涉到太多泛函知识，我就不在这里详述了。而且老实说我也没能力完全讲清楚，毕竟不是学这个的，有兴趣可以参考wiki。总之你记住，小波变换研究中所使用的信号基本都是平方可积的信号，但其应用不限于这种信号，就行了。

对L^2(R)空间做MRA是在干嘛呢？就是说，在L^2(R)空间中，我们可以找出一个嵌套的空间序列，并有下列性质：

(i)

(ii)

(iii)

(iv)

(v) 有这样一个方程, 是的orthonormal basis。

我来简单解释一下这些性质。这个V_j都是L^2(R)空间中的子空间，然后他们是由小到大的，交集是{0}，因为这是最小的子空间，并集就是L空间。是不是有点难以理解？没关系，看看下面这个图就清楚了：

这个图是圈圈套圈圈，最里面的圈是V0，之后分别是V1，V2，V3，V4 。那他们有趣的性质就是，假如有一个函数f(t)他属于一个某空间，那你将其在时域上平移，它还是属于这个空间。但如果你对它频域的放大或缩小，它就会相应移到下一个或者上一个空间了。

同时我们还知道，你要形容每一个空间的话，都需要有对应的orthonormal basis，这是必然的，那对于V0来讲，它的orthonormal basis就是

这一系列函数是什么呢？是的时域变换，而且我们刚才也说了，时域上平移，是不会跳出这个空间的。这样，我们就可以说，由这一系列basis所定义的L^2(R)子空间V0被这些basis所span，表示成：

k从负无穷到正无穷。上面的bar表示这是一个闭包空间，也就是说

这样，我们就定义了基本的V0这个子空间。刚才说了，这个子空间的基都是对的整数时域变换，这里我们称为scaling function，所以换个说法，就是说这里整个子空间V0，由scaling function和其时域变换的兄弟们span。

当然，如果这个scaling function只是用来代表一个子空间的，那它的地位也就不会这么重要了。刚才我们提到，这个嵌套空间序列有一个性质，。这就是这个函数，如果你对它频域的放大或缩小，它就会相应移到下一个或者上一个空间了。这个性质就有意思了，它代表什么呢？对于任何一个包含V0的更上一层的空间来讲，他们的基都可以通过对scaling function做频域的scale后再做时域上的整数变换得到！推广开来就是说，当

我们有

这也就意味着，对于任何属于V_j空间的函数f(t)，都可以表示为：

到这里，我们就明白这些个子空间和那个凭空冒出来的scaling function的作用了。scaling的构建这些不同的子空间的基础，当j越大的时候，每一次你对频率变换后的scaling function所做的时域上的整数平移幅度会越小，这样在这个j子空间里面得到的f(t)表示粒度会很细，细节展现很多。反之亦然。通俗点说，就是对scaling function的变换平移给你不同的子空间，而不同的子空间给你不同的分辨率，这样你就可以用不同的分辨率去看目标信号。

下面就是时候看看什么是MRA equation了，这是更加有趣，也是更加核心的地方。通过刚才的讲解，V0属于V1，那scaling function是在V0中的，自然也在V1中了。我们把他写成V1的基的线性组合，那就是

其中的h(n)是scaling function的系数，也叫做scaling filter或者scaling vector，可以是实数，也可以是虚数。根号2是为了维持norm为1的。看，在这个公式里，我们就把属于V0的函数用V1的基表示出来了。同理，我们可以循环如此，把属于V0的在V2, V3, …, Vn中表示出来。这些方程就是MRA equation，也叫refinement equation，它是scaling function理论的基础，也是小波分析的基础之一。

好，稍微总结一下。到现在，已经讲了关于scaling function的基本理论知识，知道了信号空间可以分为不同精细度的子空间，这些子空间的basis集合就是scaling function或者频率变换之后的scaling function，如下图所示：

上图就是四个子空间的basis集合的展览。通过前面的讨论，我们还知道，一开始的scaling function可以通过更精细的子空间的scaling function（它们都是对应子空间的basis）来构建。比如

对于更加finer的scale：

图2
依此类推。实际上，对于任何scale和translate过的scaling function，都可以用更加精细的scale层面上的scaling function构建出来。

然后，我们有各种scale下的scaling function了，该看看它们分别所对应的嵌套的空间序列了。先看看V0，自然就是以基本的scaling function为基础去span出来的：

这个不新鲜，刚才就讲过了。这个子空间代表什么样的信号？常量信号。道理很简单，这个scaling function在整个信号长度上，没有任何变化。继续往下看：

这个相比V0更加finer的子空间，代表着这样一种信号，它从1-4是常量，从5-8是另一个常量。同理我们有：

V2代表的信号，是分别在1，2; 3，4; 5，6; 7，8上有相同值的信号。那么V3呢？则表示任何信号，因为对于V3来讲，任何一个时间刻度上的值都可以不一样。而且现在，我们也可以通过上面的一些scaling functions的波形验证了之前提到的多解析度分析中的一个核心性质，那就是：

我们之前讲了一堆多解析度的理论，但直到现在，通过这些图形化的分析，我们可能才会真正理解它。那好，既然我们有一个现成的信号，那就来看看，对这个信号作多解析度分析是啥样子的：

你看，在不同的子空间，对于同一个信号就有不同的诠释。诠释最好的当然是V3，完全不损失细节。这就是多解析度的意义。我们可以有嵌套的，由scaling function演变的basis function集合，每一个集合都提供对原始信号的某种近似，解析度越高，近似越精确。

说到这里，可能你对scaling function以及多解析度分析已经比较理解了。但是，我们还没有涉及到它们在小波变换中的具体应用，也就是还没有回答刚才那个问题：凭空插了一个scaling function到小波basis组合中干嘛。也就是说，我们希望理解scaling function是怎么和小波函数结合的呢，多解析度能给小波变换带来什么样的好处呢。这其实就是是小波变换中的核心知识。理解了这个，后面的小波变换就是纯数学计算了。

好，我们已经知道，对于子空间V0，basis是scaling function：

对应的小波函数是：

然后子空间V1的basis集合是这俩哥们：

看出什么规律了么？多看几次这三个图，你会惊讶地发现，在V0中的scaling function和wavelet function的组合，其实就是V1中的basis！继续这样推导，V1本来的的basis是：

然后V1中对应的wavelet function是

他们的组合，本质上也就是V2的basis（参考图2）。你继续推导下去，会得到同样的结论：在scale j的wavelet function，可以被用来将Vj的basis扩展到V(j+1)中去！这是一个非常非常关键的性质，因为这代表着，对任何一个子空间Vj，我们现在有两种方法去得到它的orthonormal basis：

1. 一种就是它本来的basis ，对任意k。

2. 第二种就是它上一个子空间的basis，对任意k，以及上一级子空间的wavelet function ，对任意k。

第二种选择能给我们带来额外的好处，那就是我们可以循环不断地用上一级子空间的scaling function以及wavelet function的组合来作为当前子空间的基。换句话说，如果针对V3这个子空间，它实际上就有四种不同的，但是等价的orthonormal basis：

1. 本级(V3)的scaling function basis set

2. 上一级(V2)的scaling function + wavelet function;

3 . 上上一级(V1)的scaling function + 上上一级(V1)的wavelet function + 上一级(V2)的wavelet function;

4. 上上上一级(V0)的scaling function + 上上上一级(V0)的wavelet function + 上上一级(V1)的wavelet function + 上一级(V2)的wavelet function

好，看看最后一种选取方式，有没有感到眼熟？对了，它就是我们之前提到的“针对此信号space的哈尔小波basis组合”，参见图1。现在我们知道了，这个scaling function不是凭空插进去的，而是通过不断的嵌套迭代出来的：）

那为什么我们最后选定的是这种选取方式呢？实际上，刚才介绍的这个性质已经告诉我们，对于任何的scale j0，我们都可以给我们的signal space找到一组orthonormal basis，这个basis是通过组合scale j0上的scaling function以及所有在scale j，j>=j0上的wavelets得到的。这样，基于这个orthonormal basis，所有信号空间中的信号都可以写成组成这个basis的functions的线性组合：

对应的系数的计算和平常一样：

这，就是最终的，也是最核心的，小波变换形式。不管是信号压缩，滤波，还是别的方式处理，只要是用小波变换，都逃不出这个基础流程：

1. 选取合适的wavelet function和scaling function，从已有的信号中，反算出系数c和d。

2. 对系数做对应处理

3. 从处理后的系数中重新构建信号。

这里的系数处理是区别你的应用的重点。比如图像或者视频压缩，就希望选取能将能量聚集到很小一部分系数中的小波，然后抛弃那些能量很小的小波系数，只保留少数的这些大头系数，再反变换回去。这样的话，图像信号的能量并没有怎么丢失，图像体积却大大减小了。

还有一个没有解释的问题是，为什么要强调尺度函数和小波函数组成一个orthonormal basis呢？计算方便是一方面，还有一个原因是，如果他们满足这个性质，就满足瑞利能量定理，也就是说，信号的能量，可以完全用每个频域里面的展开部分的能量，也就是他们的展开系数表示：

到这里，我们对小波变换的形式就讲完了。虽然是用的最简单的哈尔小波为例子，但举一反三即可。我们着重介绍了多解析度分析以及它给小波变换带来的杀手锏：时域频域同时定位。结束之前，再多说几句小波变换的意义。我们拿刚才例子中V3子空间的第二种可选择的orthonormal basis作为例子：

左边这四个basis组成元素，也就是scaling functions，的系数，表征的是信号的local平均（想想它们和信号的内积形式），而右边的这四个basis组成元素，也就是wavelet functions，的系数则表征了在local平均中丢失的信号细节。得益于此，多解析度分析能够对信号在越来越宽的区域上取平均，等同于做低通滤波，而且，它还能保留因为平均而损失的信号细节，等同于做高通滤波！这样，我们终于可以解释了wavelet function和scaling function背后的物理意义了：wavelet function等同于对信号做高通滤波保留变化细节，而scaling function等同于对信号做低通滤波保留平滑的shape！

对小波变换的基础知识，我们就讲到这里。需要注意的是，这只是小波变换最基本最基本的知识，但也是最核心的知识。掌握了这些，代表你对小波变换的物理意义有了一定的了解。但对于小波变换本身的讲解，一本书都不一定能将讲透，还有很多的基础知识我都没有讲，比如如何构建自己的scaling function，选取合适的系数集h[k]，并由此构建自己的wavelet functions。所以，如果有深入下去研究的同学，好好买一本书来看吧。而只是希望用小波变换来服务自己的应用的同学，个人觉得这些知识已经足够让你用来起步了。

也许你还会对这些文章感兴趣

2011-02-15 — 小波变换和motion信号处理（一） (9)

visit the website for more great content.

给vim添加自动代码长度检测逻辑

Sun, 25 Sep 2011 11:35:33 +0800

每一种编程语言都有自己的代码规范，这里面少不了的就有代码长度。比如一般c或者python就是80，而java就是100。很多朋友都喜欢在vim下写代码，也就习惯了设置不同长度的wrap来处理这个问题。但wrap有时候会很不方便。这里介绍两个另类但是也很常用的方法。

一种是在vim里面自动在80/100的地方画一条红色竖线，提醒你，一旦你越线，就超过代码长度了。这个命令是（以80为例子）

au BufRead,BufNewFile *.c,*.cpp,*.py match Error /\%80v.\%81v./

另一种是不画醒目的竖线，但一旦你的type的code到了一定位置，就用下划线标示出来。我个人更prefer这种：

au BufRead,BufNewFile *.c,*.cpp,*.py 2match Underlined /.\%81v/

另外，根据读者朋友的留言，vim7.3内置了该功能，比如

:set colorcolumn=81

会和第一个方法产生的效果差不多。

介绍给有这种需求的朋友使用。

也许你还会对这些文章感兴趣

visit the website for more great content.

巧遇

Sun, 01 May 2011 13:08:07 +0800

前两天在Facebook上碰到一位同学，同名同姓，同毕业于西电，同在美国读书，同去Google实习。

这世上还真有这么巧的事。

Random Posts

visit the website for more great content.

聊聊这次找Google实习的过程

Sun, 10 Apr 2011 15:13:31 +0800

这次拿到Google总部的实习offer挺不容易的，也挺幸运的。每年都有很多中国学生申请他家的实习，不管是总部还是分部，我估摸着我可以把这段经历写出来，算是一个回忆，也给后面的学弟学妹一个参考。

首先想对以后希望去的朋友说的是，因为Google实习应该是计算机行业最顶级的实习待遇了，所以外面很多人传美国名校的学校找有优势。我想说，这不是让你退缩的理由。我看了一下今年实习的名单，确实MSBHCP这几个学校很有优势，学生很多，但后面的不错的学校也都不少人，比如Gatech, Purdue, UC其他系列等等。我们学校CS也就30出头的排名，除我以外还去了一个本科生一个研究生。所以你有想法，就去试，大家都要经历技术面和项目面，有实力就可能进，用实力说话。

第二个需要提到的，就是找实习，要趁早。Google今年有几百个实习坑，基本上80%已经在三月之前就定了，我就因为这个吃了亏，差点没等到match的host。所以如果下次再申请他家，一定要上一年12月左右就开始准备。

下面讲讲具体的经历吧。

去年有过实习的打算，后来因为思乡之情过于严重，还是决定暑假回家了，实习留到今年。不过由于我没心没肺的性格，基本把这事给忘了。直到今年三月的时候，看到学校的广告，说很多实习公司来校招了，才猛然一惊，该找实习了。赶紧找到老板报告有暑假实习的想法。老板一句话：实习可以，但除了Google或者Apple，别的最好别去（这里没有看不起其他公司的意思，这个领域软件有MS, FB, IBM, Intel, amazon都是适合我背景的好公司，估摸着老板的意思是这两个公司是把创新性，研究和开发结合比较好的。如果实习只是开发，不是研究，对培养自己的能力也有一定限制）。

插一句，Apple全程都没有理我。我问了一下我们学校以前去实习的人，似乎基本都是有内部推荐才会有机会面试。如果内部推荐很Strong，面试就是走流程。所以如果我明年准备换Apple实习的话，还得找找有没有朋友在里面……

回来继续讲Google。老板如此放话了，我也就只能照做。赶紧准备简历，材料，填写Ｇ家和Ａ家的申请表格之类的。我的简历也没有特意包装，没有任何让什么简历网站之类的帮忙改，随便网上找了几个模板综合一下就出来了。这样其实很不好，其实每个美国学校都有career service服务，如果你对简历的格式不放心，可以找他们看看，都是免费的，水平还很专业。我的内容写得不多，就是个人信息，RA和以前在中科院实习的经历，然后就是几篇论文。有一篇是很好会议的Best paper nomination，估计这个有点加分。然后就是我本科的一些全国竞赛奖了。这个估计作用不大，但聊胜于无。我建议大家简历别写太复杂，就是publication和各种竞赛奖，能说明你这个人还不错，就行了，过HR的简历筛选关问题不大。另外，我知道很多人喜欢在简历里面夸张，什么语言都精通，什么架构都熟悉。最好别这么干，Google里面牛人众多，他会针对你的简历去选精通的人面试，你要是不熟悉还说精通，一问就fail了。比如我对C++不熟悉，对C和Python熟，我就照实写了。

我搞完这些之后已经三月初，因为要忙一篇Sensys的paper，所以投出去就没管了，干自己的活。没过几天，就收到Google的回信，说简历过了，准备进入技术面试。这个时候，我对这些面试流程还一无所知，赶紧去网上查。网上有两个特别好的参考网站，一个是Career Cup，上面有各大公司的最新面试题集锦。一个是传说中的mitbbs买买提，上面有一个Job hunting版，都是大家介绍经验的，也有一些解题交流。这两个网站让我从实习小白变成了高中生水平，基本上知道面试是怎么回事了。简单说，就是一开始有两轮技术面试，每个45分钟，面试官出算法题，你写程序，分析复杂度，改进复杂度，等等。每个面试都会给你share一个Google Doc，然后面试官会在上面写题目，然后你在上面直接写程序。过了这两轮面试，就进入了Google的Talent pool，你的简历会放在这个pool里面，让所有group挑选，这就是Host match阶段。任何group发现有很match的candidate了，就会主动联系他，然后进行项目面试。项目面试就千奇百怪了，没有具体的形式，可以是他们给你介绍他们的产品，可以是你介绍你以前的项目，可以是再给你出一些更难的算法题打击你，可以是描述一个系统让你做基本的框架实现。总之很多样，取决于每个组的偏好。

我的两轮技术面是在某周周一，距离我受到通知只有两周。我之前忙Paper，没有进行任何准备，收到邮件就慌了。以前本科看过一些算法知识，到现在丢了很久。基本的数据结构，比如hash阿树阿这些我都熟，各种排序，图算法，我也能说一些，至于其他动态规划，A star，红黑树这些稍微高级的，我就全忘了。平时根本就没用到这些东西。概念都说不上来，更别说写了。我赶紧开始规划，不管再忙，每天抽两个小时时间看算法，写写程序，提前练练。然后是面试前的一天一整天都去看看别人分享的题，大概了解一下思路。实际上到了面试当天，真让我现场写KMP或者红黑树，我还是写不出来，肯定一堆Bug，毕竟算法涵盖面广，我复习时间不超过40个小时。但也就赶鸭子上架，硬撑了。心里面就盘算着，反正我就这样，爱要不要。阿Q一下还是可以的:)实际上从我的面试题看，我这个策略很不错，根本没有考非常高级的算法，我复习的都比较对点子，还一点都没有耽误写Paper:)

终于到了技术面的那天。我逃了课，放松了一上午。到规定时间，他们就打过来了，还是很准时的。第一轮的面试官英语很好，估计是本国人，自我介绍说是Chrome组的。一上来我就问，能不能用python写程序?反正都是考算法思路，用c麻烦一些。他说没问题，我一下子心就镇定很多了。然后他就开始在Google Doc里面出题。出于保密协议，我不方便直接透露原题，但可以说的是，第一个面试官的题都不是那种特别难的，但需要动脑子改进的。这里要说到另一个经验，就是面试官问你什么题，你通常会马上想到一个最简单也最麻烦的方法，别犹豫，马上说出来，然后再讨论怎么改进。如果你闷着头自己去想最优解，人家压根就不知道你在干嘛，说不定还以为你不知道怎么解呢。其中一道题，我就是从最初的暴力解法O(N^3)说给他听，他问有改进方法没，我想了想搞了一个O(N^2)的，他比较满意，又问我还能不能进一步改进。我想了一分钟左右没说话，他就过了。这道题我面试完马上就想到了O(NlogN)了解法了，可惜晚了。不过从这个过程看，我没有栽在这里，说明中间的交流过程他还是比较满意的。还有就是，你提出用什么语言，就一定要熟悉这个语言的特性。你的面试官是针对你的简历选的，你说你熟悉什么，他就会熟悉什么。比如他的最后一道题就是和python的特性有关，不用写程序。但如果你之前没有用过这个特性，说不定就不知道了。这次面试是45分钟左右，感觉还不错，我写程序也写得很快，中间只有一个程序有一个Bug。

第一轮面完之后休息了一下，继续第二轮。这一次听口音是一个印度人，他介绍完他是哪个组之后我就朦了，根本听不懂……我到现在也不知道他是哪个组的。顺带说一句，我真的真的真的不适应印度英语……面试的过程更加痛苦，他说每一道题我都要问三遍以上才能知道他到底想问什么，其中有一道图像算法的问题，我一直都没听懂，sorry了几次之后，他不耐烦就过了。我的感觉一下变得很差，心想估计栽这里了。到最后一道题的时候，我脑子已经基本都是空白了，连蒙带猜估计了一下题意，就马上开始写代码了，而且用的没有任何优化的算法……他中间甚至没怎么看懂，重复问了我一下是不是理解了题意。我写完之后，他总算看懂了，回了一句：这不就是brute force么。我想，完了，连最后一题也搞砸了。就在他准备鸣金收兵的时候，当时不知道怎么回事，脑子突然灵光闪现，一下子就想到了针对这个问题的O(n)算法，估计也是最优的。马上给他说，不好意思老大，我有一个新的想法，能说一下么？他犹豫了一下，说行。我立刻巴拉巴拉边说边在GDoc里面画，尽量快地把我的意思体现出来。说到最后他也理解了，说，我喜欢这个解法。我后来琢磨，我能过这两轮，或者就是第一轮的那位哥们分数给力，或者就是第二轮的这个最终解法救了我。

所以总结下来，Google的实习技术面试没有工作技术面试那么难，不会有很多高级算法，主要还是基本的算法素质和基础知识，准备的时候针对这些就行了。当然基础知识有很多考法，比如理想情况怎么办，内存不够怎么办，多台机器同时跑怎么办，等等。你需要对基础知识熟练到能应付扩展情况，并且如果有新的情况了，要会分析新的复杂度。其他就看运气了。

技术面之后，我觉得希望不大，所以也没太放在心上，想着不行就留校继续当RA吧。在这种期望不高的情况下，有时候真会有惊喜出来。两周后，我正在写paper，突然收到HR的信，说我通过了技术面试，进入Host match阶段。我当时特别高兴，感觉就像已经拿offer了，还在twitter上发了一个更新，估计很多朋友还能记得。因为按以前经验看，进入这个阶段的人90%都能拿到offer。没想到正是因为我面得晚，结果出得也晚，大多数组已经都招满了。我又等了两周，一直没有组联系我，我发邮件问HR，回复是他们在尽量找，但确实不保证能找到。我的心情从充满希望又回落到了充满失望，想着，估计我要成为悲剧的10%中的人了。

最后阴差阳错，上天确实很眷顾我，有一个和我背景比较match的组最后还是面试了我。我对我之前的项目阐述地很好，毕竟都是自己做的。项目的重要性，创新性也都突出介绍了。估计我的老板他们的推荐信也很给力，面完的第三天就决定给我offer了。从几乎出局到最终达成，locate到做mobile的组，我喜欢的方向，mentor是一个ACM Fellow，本领域的大牛，Google总部。对我来说，这是一个Dream offer，完美的结局。

整体流程就是这样的。我不是一个算法大牛，这我的朋友都知道。我只是因为

1 正确的时间高效作了复习工作
2 在老板的严苛要求下做了一些有意义的项目
3 未来Mentor的帮助和信任
4 一直以来都不错的狗屎运

等因素才拿到这个实习offer。我将来工作的终极目标并不是去Google，但Google的实习能带给我很多新的东西，新的朋友，新的视野，新的能力。我坚信这点，所以我感谢所有帮助我的人，感谢那几个不知道名字的UWashiton和Gatech的哥们一直在论坛上交流和相互打气，感谢我的老板，感谢我的师弟师妹在我最忙的时候take了很多我的工作。

希望未来的几个月里，我能写写具体的实习经历和感受。如果有任何后来人希望找Google实习，对面试过程有什么问题，都可以和我交流。

Random Posts

visit the website for more great content.