Archive for the ‘ lambda ’ Category

索引,做还是不做,这是个问题

先说个题外话很多人都搞错了mongodb的名字,错误地拼成了mangodb,或者mango。我劝大家不要吃芒果了。从我的网站搜索结果来看拼成mangodb的真的不在少数,这里还要请大家特别注意,尤其是母语不是英语的人。否则要是到英语讨论组提问的话,会引起不必要的误解。
首先要说明的是mongodb的索引和传统的关系型数据库的索引几乎完全一样,所以很多原来的优化手段这里也是适用的,反之也对。那么索引是什么呢?有些人觉得我故弄玄虚,玩数据库的谁人不知索引啊。好吧,那我换一个问法,索引用来干什么?索引是为了在查询的时候更加快速。bingo!这句话是有好多隐含的意思的。查询更加快速,那么是和什么相比呢?肯定是和笨方法相比了。所谓的笨方法就是复杂度为O(n)的线性查找了。这种查找的好处就是不用做任何预处理,而且不需要额外的空间,可以容易地并发。据我所知有两种方法可以降低时间复杂度,一种利用排序的方法,可以将查找有序表的时间复杂度降到O(log(n)),一种使用Hash的方法,用空间换时间,使得时间复杂度讲到O(1)。今天要讨论的主要集中在变无序为有序的做法,也就是大部分索引的机理。
既然涉及到排序,那么就涉及到顺序。所以按照{a:1, b:1}建立的索引,和{b:1, a:1}建立的索引是完全不同的。这种不同的表象是建立索引的速度会用不同,深层次的原因就是排序的准则不同所以顺序就不同,导致的排序复杂程度就不一样。要知道排一几乎有序的数列,和排一个几乎无序的数列可能是完全不同的工作量。还记得所有的算法书上都将到了最好情况和最坏情况吧。所以以一定要考虑你自己的数据究竟是什么样子的,本身有什么性质,建立索引的时候要尽量的符合现有顺序。少折腾,会有很大的获益。至于查询的时候,查询优化器不会计较{a:20, b:30}还是{b:30, a:20}会自动优化的。还要考虑的一个问题就是索引的复用,因为如果建立所以是{a:1,b:1,c:1,d:1},下面这几种都将能复用这个索引{a:10}, {a:10,b:20}, {a:10,b:20,c:90},查询关键字的顺序并不重要,但必须是建立索引的前几个关键字的组合,前一个,前两个,以此类推。
上面讲了第一顺序,还有另外一个顺序。那就是关键字的排序顺序。当然要是你的索引只有一个关键字,就没所谓了。要是有多个关键字,首先要考虑关键字摆放的顺序(上面讲到的),然后就是关键字本身怎么排的问题。是{a:1, b:-1}还是{a:1, b:1}。还是那句话,少折腾就多获益。
不要对不怎么变化的值进行索引。比如性别,有无驾照这种布尔类型的量,对这个索引是没有任何意义的。排不出顺序,也就失去了索引的意义。
有些时候需要返回大量结果,比如返回的结果占到集的一般,这时候,最好就别用索引, 老老实实的用笨方法更快。因为当你要把一本书的前半本都读出来时,索引帮不上什么忙的,反而显得很这腾。所以不见得索引就一定快,要适合自己才是关键。

巧用oplog

by 10gen’s Mathias Stearn
翻译:程显峰

你已经使用了热备(还没有?),也已经知道设置起来非常容易。但可能你还不知道:所有的操作都会存储在一个常规的固定集中,在主控上是local.oplog.$main,在备份上是local.oplog.rs。通过查询这个集,可以深入探究系统的各个方面,甚至可以实现异步触发器。

?View Code JAVASCRIPT
> use local
switched to db local
> db.oplog.$main.find().sort({$natural:-1})
{ "ts" : { "t" : 1288884355000, "i" : 1 }, "op" : "u", "ns" :
"test.foo", "o2" : { "_id" : 1 }, "o" : { "$set" : { "i" : 2 } } }
{ "ts" : { "t" : 1288884349000, "i" : 1 }, "op" : "u", "ns" :
"test.foo", "o2" : { "_id" : 1 }, "o" : { "$set" : { "i" : 1 } } }
{ "ts" : { "t" : 1288884227000, "i" : 1 }, "op" : "i", "ns" :
"test.foo", "o" : { "_id" : 1, "some" : "thing" } }
{ "ts" : { "t" : 1288884225000, "i" : 1 }, "op" : "n", "ns" : "", "o" : { } }

可以看到有两次更新,一次插入,一次空操作(就是最下面的那个)。op可以是下列值:
i – insert
d – delete
u – update
c – command
n – no-op

空操作定期执行确保时效性。如果想过滤掉这些信息,在查询条件加入{op:{$ne:’n’}}就可以了。

很重要的一点就是所有oplog条目都是等幂的。例如上面的两次更新都是由{$inc:{i:1}}调用的,但是最后会转换成$set操作,这样就可以在以后多次重放。

新玩具_1289266510

不错的Js Chart图工具:
http://www.highcharts.com/
还有一个什么来着??
http://raphaeljs.com/

这个配合node.js使用,兼容IE5.5。
http://socket.io

这个其实并非新玩具,Javascript实现的Scheme:
http://tryscheme.sourceforge.net/

另外发现YAML是一种很好的配置文件格式,可以比INI表现更丰富的层次关系和更明确的属性类型。
另外JSON是YAML的一个子集。

祝大家玩得开心,用着舒心~

Euler-{18,67}

http://projecteuler.net/index.php?section=problems&id=67
典型的动态规划。
原先在手机里写的,
跟机器一起丢了……
补上一个 T^T

?View Code PYTHON
#Python的解
dat_lines =  [ map(int, l.split(' ')) for l in open('triangle.txt').readlines() ]
dat_lines.reverse()
 
for i, l in enumerate(dat_lines):
    if not i:
        continue
    else:
        for ei, ev in enumerate(dat_lines[i]):
            dat_lines[i][ei] += max(dat_lines[i-1][ei], dat_lines[i-1][ei+1])
 
print dat_lines[i][0]
?View Code HASKELL
module Main where
 
acc_l [] (o1:[]) = []
acc_l (c1:cs) (o1:o2:os) = ((max o1 o2) + c1) : acc_l cs (o2:os)
 
main = do 
    lns <- readFile "triangle.txt"
 
    let real_lns = map (\l -> [ read x::Int | x <- words l ]) (lines lns)
 
    --Haskell里头列表项的值是不可变的,用foldr做累加。
    print $ head $ foldr (\nl ol-> acc_l nl ol) (last real_lns) (init real_lns)
 
    return ()

New Challenge

今日入职新工作,工作机是一台WinXP,来得时候没带其他OS的安装介质,只好挂着代理下Python的安装包。

想起老大吩咐准备Python培训时说:实在不行就每天一道Python Challenge

于是等待下载的时候就捡起了Python Challenge(http://www.pythonchallenge.com/)。话说上次(四年前?)被第五关那个伪装成”Pack Hell”的”pickle”给恶心到了,当时心中隐隐懊恼自己的E文水平,顺便也认为在计算机编程题中以谐音作为难点很无趣,于是就木有继续做下去。
没想到会又一次面对这站。

因为安装包还在下载中,所以解题时自然无法使用本机的Python。

于是突发奇想,反正从前也用Python切过这站,今次何不换门语言?

把Python Challenge 玩成New Challenge好了 : P

第一关,直接在地址栏里敲入

?View Code JAVASCRIPT
javascript: alert(Math.pow(2, 38));

……貌似算得还挺快?

第二关, 移位密码……脑子里立刻浮现出一堆 map 和 lambda ……
这就不麻烦 js 了吧~
打开 TryHaskell(http://www.tryhaskell.org),敲了几句代码,正确性没问题,不过 tryhaskell 的shell不能粘贴代码,整段密文好长……
只好老老实实的在vps的terminal里启一个hugs,幸好tryhaskell里头输入的代码还是可以拷贝下来的。

?View Code HASKELL
let s="……lmu ynnjw ml rfc spj. " 
in map (\w -> inter­sperse "" $ map (\c -> [chr $ 97 + mod (ord c - 97 + 2) 26]) w) $ words­ s

写得很快,读着有点恶心的一坨代码 : P

此处的 intersperse 在 Data.List 中定义(tryhaskell 很体贴,默认就导入了这个函数,而且在tryHaskell中使用ord和chr等函数也无需import Data.Char, 很方便吧?……不过话说tryhaskell里头貌似无法导入任何模块,所以提供的函数全一些也是为了大家玩得开心。),用途和 Python 中的字符串方法 join 近似,只不过 intersperse 定义在泛型的列表上,可用的范围更广罢了。另外intersperse返回值类型仍然一个列表,如果在处理字符串的时候希望达到和Python中join函数相同的效果,需要对结果 concat 一下 : )

Python中的

?View Code PYTHON
",".join(["hello", "world"])

在Haskell中可以写为

?View Code HASKELL
concat $ intersperse  ","  ["hello", "world"]

其实 concat 和 intersperse 的组合与 Data.List 中的 intercalate 函数是等价的。
写成这样就行了:

?View Code HASKELL
intercalate  ","  ["hello", "world"]

好吧,既然Haskell里头实现Python的join函数很容易,那么split函数呢?
……这个,貌似除了Hackage中的那个正则split,并没有特别简单的方法。
前些天山寨了一个,简单用用,性能没测,不知在特别大的字符串上效率如何。
正确性是没问题的 : P

?View Code HASKELL
> module MySplit (split) where
 
> split :: String -> String -> [String]
 
> split s tkn | l == 0 = [s]
>             | otherwise = _split s
 
>     where
>         l = length tkn
>         _split x | tkn == take l x =
>                         "": (_split $ drop l x)
 
>                  | null x =
>                         "":[]
 
>                  | otherwise =
>                         (head x : head sp) : tail sp
>                             where
>                                 sp = _split $ tail x

这个实现采取逐位匹配的方法搜寻作为分割符的串,好处是清晰易懂,坏处是会做许多无用功,如果使用BM算法的跳转匹配,效率会提升许多。

呃,貌似跑题了……

本帖主题是New Challenge来着……嗯

虽说学习新语言时,应该避免”用Pascal语法写出BASIC风格的程序”(《十年学会编程》http://daiyuwen.freeshell.org/gb/misc/21-days-cn.html),

但是,使用新语言尝试过去已经完成的任务,确实是一个学习语言的好方法。
著名的编程语言联系练习项目PLEAC(http://pleac.sourceforge.net/),就是如此。

PLEAC中使用接近30种不同的语言来重复完成Perl CookBook中的练习。其中既包括Python,Ruby,C++等热门语言,也包括Haskell,OCaml,Guile,R等小众语言,甚至还有汇编语言。

看来学习就是一个”重复”的过程,
不断挑战自己,用旧瓶酿出新酒来吧~!
: D

生成器的另一种写法

Python中的列表生成式大家应该很熟悉了

?View Code PYTHON
from random import random
[random() for i in xrange(10)]

结果应该是含十个随机数的List。

好,现在让我们换一种写法:

?View Code PYTHON
(random() for i in xrange(10))

仅仅是”[]”换成了”()”
“[]”表示List,”()”表示Tuple
那么这句的结果是否是个包含十个随机数的Tuple呢?

?View Code PYTHON
type(
    (random() for i in xrange(10))
)
#<type 'generator'>

原来得到的是一个生成器。哈哈,看来猜错了。

关于什么是生成器,及其用法,请参考:
使用生成器
迭代器和简单生成器

xrange应该是大家最常用的生成器了,相对于range函数,其优点是速度快且省资源。

下面有一个直观的比较:
对一堆随机数求和(偷懒使用IPython内置的%timeit函数统计耗时)

?View Code PYTHON
In [21]: timeit sum(map(lambda x:random(), xrange(1000000)))
10 loops, best of 3: 432 ms per loop
 
In [22]: timeit sum((random() for i in xrange(1000000)))
10 loops, best of 3: 266 ms per loop

使用生成器的版本明显比使用map的版本快。
所以现在俺已经养成了习惯,能用生成器的地方,决不用map :p

使用生成器时需要注意的是,生成器对某个值只生成一次。

考虑下面的代码:

?View Code PYTHON
def foo(l, n):
    def cond(i):
        return False if i % n else True
    if 2 == n:
        return filter(cond, (i + n for i in l))
    elif 3 == n:
        return filter(cond, (i - n for i in l))
    elif 5 == n:
        return filter(cond, (i ** n for i in l))
    elif 0 == n:
        # 当参数 n 为 0 的时候,则通过递归求得参数 n 分别为2, 3, 5 时的所有结果
        return [foo(l, x) for x in (2, 3, 5)]

以列表为第一个参数,测试这个函数递归时的行为。

?View Code PYTHON
for i in foo(range(10), 0):
    print i
 
# [2, 4, 6, 8, 10]
# [-3, 0, 3, 6]
# [0, 3125]

好吧,记住这些结果。

让我们看看以生成器参数进行递归时会产生什么结果:

?View Code PYTHON
l = (i for i in range(10))
for i in foo(l, 0):
    print i
 
# [2, 4, 6, 8, 10]
# []
# []

只有第一次返回了正确的结果,因为生成器在第一次递归调用后就已经返回了,所以最后两次调用根本没有收到有效的参数。

说穿了很容易理解—生成器对某个值只生成一次。
注意一下即可,话说笔者也是曾经因为粗心,出过类似的Bug才长了记性的。

对刚才的函数修改一处即可在递归时正确处理生成器参数。

?View Code PYTHON
def foo(l, n):
    def cond(i):
        return False if i % n else True
    if 2 == n:
        return filter(cond, (i + n for i in l))
    elif 3 == n:
        return filter(cond, (i - n for i in l))
    elif 5 == n:
        return filter(cond, (i ** n for i in l))
    elif 0 == n:
        return [foo(
                    tuple(l), # 只是在递归前显式地将生成器转为tuple而已……
                    x) for x in (2, 3, 5)]

以上是近期遇到的关于生成器问题的一个小总结。

此物大善:GTK-server

The GTK-server is a free, open-source project, which offers a stream-oriented interface to the GTK libraries, enabling access to graphical user interfaces for shellscripts and interpreted programming languages using either GTK 1.x or 2.x. It was inspired by Sun’s DeskTop KornShell (dtksh) of the Common Desktop Enviroment (CDE) for Unix.

来这里看看例子吧:

http://www.gtk-server.org/apps.html