落园 |专注经济视角下的互联网

初探Lick Observatory

湾区真是个神奇的地方。我住了一年居然不知道在离家二十多迈的地方居然有一个天文台。而且这个天文台居然历史追溯到100多年前(1876年开始建)。名字是以Lick命名的,听馆员的解说是这个人也很神奇,一下子捐了当年的70万美金(相当于现在的2亿美金)来建造了一个天文台。这个天文台现在归属于University of California,由University of California出资和管理,平时也免费对公众开放。当年这个望远镜是全球最大的反射式天文望远镜,就今天来看还是一个庞然大物。

之所以对家附近有个天文台比较意外,也是想着湾区这么多夜晚的灯光,不知会对天文台有多大的影响。看wiki上说,天文台附近的居民搬出去不少,算是减少了一些人工光的干预。在天文台上面可以俯瞰整个海湾,其实感觉湾区真的还挺小的...

作为一个从小就希望有个望远镜的,看到这么一个巨大的望远镜自然是很兴奋。可惜白天望远镜被老老实实的藏在观测室里面,穹顶是不开的。等到晚上夜幕降临、望远镜就会缓缓探出、观测星空。

所以今天更多的是了解一下那里的历史(也是今年第一次看落日),顺便一路上风景秀丽,也是不禁陶醉其中。待到夏天的时候天文台会有晚上的观星活动,这就让人额外兴奋了。早早注册好,顺便可以先去买个望远镜自己玩玩了。

DSC04347落日时分

DSC04311

夕阳下的天文台

DSC04273

外面的望远镜和观测角DSC04373

远处另外一个观测点

DSC04261雪景的样子,美到窒息。


继续抄笔记——KMP算法

在今天以前我也不知道有个大名鼎鼎的KMP算法,也是偶然看到的。KMP算法解决的是文本匹配的问题,比如我要在字符串“今天天气特别好”里面找到“特别”的位置(对应第5-6位),或者简单如我在word里面点击“查找”,然后搜索一个关键词。一般来说,如果是编程中为了解决这种问题,我就特别习惯的去写正则表达式了...从没想过正则表达式后面他们到底会怎么算。当然直到此刻我也不知道正则表达式会不会调用KMP算法。

在上面那个例子中,只要我慢慢从左到右一个个对比“今天天气特别好”和“特别”就很容易找到“特别”的位置,无非就是到第5位的时候发现“特”是匹配上的,然后对比一下第6位是不是一样。但是如果前面那句话变成了“今天特热,但天气特别好”,按照上面的算法,我就会在第三位发现“特”是匹配上的,但是第四位没有匹配到,于是我又开始从第四位开始重新一个个看、什么时候可以依次匹配到“特”和“别”。

这大概是最直观的算法了,写起来也并不麻烦。就是有点暴力的感觉:穷尽所有的可能、总能找得到是不是。

当查找的字符串简单如“特别”的时候,确实用不用kmp算法不会有任何区别。可是有的时候我们要查找的字符串比较长,那这样的暴力算法就有点浪费了——因为可能已经做过一些比较了。

举个例子。我现在想在“今天天气很好,街上人来人往好不热闹,我们一起出去玩好不好”这句话中寻找“好不好”。那么第一个“好”出现在“今天天气很”,然后发现嗯,下面一个是逗号,所以继续从逗号开始找下一个“好”;然后找到“好不热闹”,发现“好不”都被匹配到了,但是最后一个“好”没有匹配到,所以我们还得继续找。那么这时候是应该直接跳到哪里呢?“闹”、“热闹”呢,还是“不热闹”这里开始比较?显然看我们要寻找的字符串,“好不好”的第一位和第三位是一样的,然后第二位和他们俩都不一样,所以我们其实知道在“好不热闹”这个局部中,第二位的“不”不可能和“好”匹配,第三位的“热”也不可能和“好”匹配,所以我们可以直接跳到第四位“闹”。

这大概就是kmp的基本直觉了:先看一下我要搜寻的这个东西自己是不是有一定的模式,算一张局部匹配表(Partial Match Table),然后按照这个表就可以知道当每次前面部分匹配、而后面不匹配的时候,可以直接跳过几个格子往下走。(至于这个表格怎么算的,还是有点麻烦的....)

我是看这个解释看懂的:

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

然后matrix67也有一篇有点历史的文章来解释这个:http://www.matrix67.com/blog/archives/115

 


抄抄笔记——格雷码

想起来差不多十年前从图书馆里面一本又一本的借出来各种算法和数据结构的书籍,却从来没读完过...

今天看到一个东西,格雷码。看了半天硬是没怎么看懂(除了第一种递归的办法)...一看到二进制我就懵掉了,脑子里面一点线索都没有的悲催感。想想这块儿的知识应该也会挺有意思的吧?什么二叉树啊,红黑树啊,好像我都完全不了解是怎么个玩法。唉。

抄一点百度百科的笔记。争取过段时间再来看,能多看懂一些...现在脑子里面完全没有一点感觉。

递归生成码表

这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
  1. 1位格雷码有两个码字
  2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0
  3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1[3] 

2位格雷码
3位格雷码
4位格雷码
4位自然二进制码

00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

异或转换

二进制码→格雷码(编码)
此方法从对应的n位二进制码字中直接得到n位格雷码码字,步骤如下:
  1. 对n位二进制的码字,从右到左,以0到n-1编号
  2. 如果二进制码字的第i位和i+1位相同,则对应的格雷码的第i位为0,否则为1(当i+1=n时,二进制码字的第n位被认为是0,即第n-1位不变)[3] 
公式表示

(G:格雷码,B:二进制码)

例如:二进制码0101,为4位数,所以其所转为之格雷码也必为4位数,因此可取转成之二进位码第五位为0,即0 b3 b2 b1 b0。
0 xor 0=0,所以g3=0
0 xor 1=1,所以g2=1
1 xor 0=1,所以g1=1
0 xor 1=1,所以g0=1
因此所转换为之格雷码为0111
格雷码二进制码(解码)
从左边第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值(最左边一位依然不变)。依次异或,直到最低位。依次异或转换后的值(二进制数)就是格雷码转换后二进制码的值。
公式表示

(G:格雷码,B:二进制码)

原码:p[n:0];格雷码:c[n:0](n∈N);编码:c=G(p);解码:p=F(c);
书写时按从左向右标号依次减小,即MSB->LSB,编解码也按此顺序进行
举例:
如果采集器器采到了格雷码:1010
就要将它变为自然二进制:
0 与第四位 1 进行异或结果为 1
上面结果1与第三位0异或结果为 1
上面结果1与第二位1异或结果为 0
上面结果0与第一位0异或结果为 0
因此最终结果为:1100 这就是二进制码即十进制 12
当然人看时只需对照表1一下子就知道是12
...................c[n]=p[n],
解码:

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征,可以递归得到高阶格雷码。由于此方法相对繁琐,使用较少。生成格雷码的步骤如下:
  1. 将卡诺图变量分为两组,变量数目相近(最好相等)
  2. 以逻辑变量高位在左低位在右建立卡诺图
  3. 从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图,依次经过格子的变量取值即为典型格雷码的顺序
三位格雷码(三位格雷码由建立在二位基础上)
AB╲ C
0
1
00
0→
1↓
01
↓2
←3
11
6→
7↓
10
4
←5
格雷码次序:000起点001011010110→111101100终点
四位格雷码
AB╲CD
00
01
11
10
00
0→
1→
3→
2↓
01
↓4
←5
←7
←6
11
12→
13→
15→
14↓
10
8
←9
←11
←10
格雷码次序:0000起点→000100110010011001110101010011001101
111111101010101110011000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除,称为异或乘除,它的特点是无进退位。
如:10101除以11将变成1100余1。
二进制转格雷码
只要异或乘以二分之三,即二进制的1.1,然后忽略小数部分;也可以理解成异或乘以三(即11),再右移一位。
格雷码转二进制
异或除以三分之二,即除以1.1,忽略余数;或者左移一位,再异或除以三,忽略余数。

捡到的诗集

虽然最近一直在三藩活动,但是还是有一些一直想去而没机会去的地方。比如今天终于找到时间和理由来一家历史悠久的书店——City Lights Booksellers and Publishers。听名字就是一个很有感觉的地方,城市光线城市之光。以前留意过一些有趣的活动在这里,就大概估计这会是一个类似于诚品那样的书店,可以坐下来慢慢喝茶看书的。结果,我又以东方思维来推测西方生活了。这就是一个书店,一个纯粹的书店,一个不卖任何饮料的书店。

City Lights (城市之光书店)

City Lights (城市之光书店)

这个书店一进去就是密密麻麻的书架,然后随处可见的标示提醒着浮躁如我的都市人:坐下来,看本书(have a seat + read a book)。于是果断收起手机,随手翻起一本书,寻了一个安静的位置坐下。大概是也没想读一本很厚的诗集,于是随手选了一本薄薄的册子。本也没想读完,却没想到一打开就停不下来,然后竟然就坐在那里翻完了,伴随着心中感慨万千。严格地说,虽然这本书被放在poetry那边,但更像是文化记录的缩影,只是用诗歌这种形式来记录罢了。

IMG_3316

这本书的名字是,I am the Beggar of the World, Landays from contemporary Afghanistan. landay大概相当于歌谣,并不一定是用文字(暂不论语言)记录在纸上,而是以声音的形式进行传播和电子记录(这里还要多谢智能手机的发明,很多语音资料得以被很方便的记录下来)。我不是很了解这个书店的定位,粗粗扫了一眼大致以文学书籍为多,还有很多他们自己出版的。直接的感慨就是美国的文化还是很开放的,至少允许人们出版自己的所见所闻。一句题外话,原来只是感慨有墙的存在所以大家翻墙查阅电子资料不方便,上周一个朋友说其实在国内做人文研究也很苦,因为很多国外出版的书籍都买不到、甚至连图书馆里面也很难借到。这样想想,貌似像我这样随便走进书店然后偶遇一本自己可能感兴趣的书,可能也是一件比较奢侈的事情了。不知道这样的隔阂,到底会造福谁。我们甘愿沉浸于禁锢的思想和快餐娱乐吗?

[......]

Read more


AEA的一点记录

年初的时候连续三天跑到三藩AEA去凑了个热闹。如果这次不是在三藩的话估计我也不会大老远特意跑过去,毕竟这个会都是学术界的人,我跑过去难免有纯粹凑热闹惹人烦之嫌。

首先就是被会议的规模惊呆了。作为一个见惯了国内各种大型会议各种大场面的人,我还是被这样上万人的会议惊呆了。谁说美国地广人稀来着....据某个童鞋说,她从欧洲飞过来入关的时候,SFO的海关都知道了,直接问,“是那个经济学会议对吧?”。这两天的飞机上各种都是来开会的人也不足为奇,据说有好多邻座什么的都是economists或者未来的economists...很多人的直接反馈就是这样的job market确实是很有效率的,是一个高效的matching algorithm,只是不是机器计算的而是大家各种人肉计算出来的。

从上段的描述可以看出来,很多人来AEA就是来找工作的,要么来面试要么面试其他人。像我这种纯粹去围观的估计不多——虽然有很多演讲的sessions但是大家基本也都是各种小圈子里面自娱自乐。说实话,虽然我已经毕业这么久了,但是我也没想到很多session已经到了看标题都看不懂的地步了...哎,分工实在是太细了。

对我来说最重要的估计就是见各种人了——见到了很多快五年没有见过的人。估计不是AEA的话,这些人真的是再过n多年都不一定能见到。有的时候也是感慨,很多在国内的人在国内的时候各种见不到,跑到美国来反而容易见到。各种在美国的人在美国的时候见不到,回国反而能见到。这是一种什么样的给航空公司创造利润的模式...还是用一种最好听的方式来表述吧:大家越来越国际化了。

大牛的话,我主要是去围观Susan Athey的,连听了她两场。一场是比较好玩的bitcoin,都是一些描述性的统计,但是问题本身很好玩,很多新的东西大家都不知道是怎么回事儿,看到一些基本的分析、想想后面的逻辑也是蛮有意思的。另一场是big data,就是她们的tree model去detect heterogeneous treatment effect,这东西前段时间一直在跟,所以到也不陌生,只是感慨很多想法大家其实都有,最后就是看谁有数据谁又坚持下去一点一点把细节都推敲出来。话说中途发消息给某统计学家感慨,人家直接懒懒的回我一句,不记得了。好吧,大牛们的脑路变化都是奇快无比的,不记得就不记得吧。作为一个乖乖的学生,我自己记得学习的心路历程就好了。还去听了Tadelis的两场,虽然很多paper已经听过一遍了,但是去现场玩玩还是挺好玩的,顺便可以见到很多ebay和ex-ebay的人(其中有真人比照片帅的帅哥)。也是一种networking的过程吧。

还有比较好玩的就是不同人的不同状态。很多找工作的人在三天的时间有十几个面试,于是各种亚历山大、繁忙的穿梭在各个酒店之间,偶尔路上碰到也就是匆匆打个招呼。已经进入tenure clock的人相对来讲这次就是来聚一聚的,席间还能听到各种八卦。打算明年上job market的就是提前来看一下情况顺便听听sessions,倒也蛮紧凑的。相比来讲心态最放松的大概就是已经拿到tenure的,来开会更多是纯粹的来开会。各种人的各种状态和各种消息还是蛮有意思的。

还有什么呢?好像已经习惯了每天往返三藩和圣何塞,这样的折腾背后也是预示着什么——既然有那么多事情都是在三藩。