寻找最快的Python字符串插入方式

目录 编程

在 MapReduce 分布式计算时有这样一种场景:mapper 输入来自多个不同的数据源,共同点是每行记录第一列是作为 key 的 id 列,reducer 需要根据数据源的不同,进行相应的处理。由于数据到 reducer 阶段已经无法区分来自什么文件,所以一般采取的方法是 mapper 为数据记录打一个 TAG。为了便于使用,我习惯于把这个 TAG 打到数据的第二列(第一列为 id 列,作为 reduce/join 的 key),所以有这样的 mapper 函数:

def mapper1(line):
    l = line.split('\t', 1)
    return "%s\t%s\t%s" % (l[0], 'TAG', l[1])

这样给定输入:

s = "3001	VALUE"

mapper1(s) 的结果就是:

s = "3001	TAG	VALUE"

这是一个潜意识就想到的很直白的函数,但是我今天忽然脑子转筋,陷入了“这是最快的吗”思维怪圈里。于是我就想,还有什么其它方法呢?哦,格式化的表达式可以用 string 的 + 运算来表示:

def mapper2(line):
    l = line.split('\t', 1)
    return l[0] + '\t' + 'TAG' + '\t' + l[1]

上面是故意将 '\t' 分开写,因为一般 TAG 是以变量方式传入的。还有,都说 join 比 + 快,那么也可以这样:

def mapper3(line):
    l = line.split('\t', 1)
    l.insert(1, 'TAG')
    return '\t'.join(l)

split 可能要消耗额外的空间,那就换 find:

def mapper4(line):
    pos = line.find('\t')
    return "%s\t%s\t%s" % (line[0:pos], 'TAG', line[pos+1:])

变态一点儿,第一个数是整数嘛,换成整型输出:

def mapper5(line):
    pos = line.find('\t')
    pid = long(line[0:pos])
    return "%d\t%s\t%s" % (pid, 'TAG', line[pos+1:])

再换个思路,split 可以换成 partition:

def mapper6(line):
    (h,s,t) = line.partition('\t')
    return "%s\t%s\t%s" % (h, 'TAG', t)

或者干脆 ticky 一点儿,用 replace 替换第一个找到的制表符:

def mapper7(line):
    return line.replace('\t', '\t'+'TAG'+'\t', 1)

哇,看一下,原来可选的方法还真不少,而且我相信这肯定没有列举到所有的方法。看到这里,就这几个有限的算法,你猜一下哪个最快?最快的比最慢的快多少?

先把计时方法贴一下:

for i in range(1,8):
    f = 'mapper%d(s)' % i
    su = "from __main__ import mapper%d,s" % i
    print f, ':', timeit.Timer(f, setup=su).timeit()

下面是答案:

mapper1(s) : 1.32489800453
mapper2(s) : 1.2933549881
mapper3(s) : 1.65229916573
mapper4(s) : 1.22059297562
mapper5(s) : 2.60358095169
mapper6(s) : 0.956777095795
mapper7(s) : 0.726199865341

最后胜出的是 mapper7 (tricky 的 replace 方法),最慢的是 mapper5 (蛋疼的 id 转数字方法),最慢的耗时是最慢的约 3.6 倍。最早想到的 mapper1 方法在 7 种方法中排名——第 5!耗时是最快方法的 1.8 倍。考虑到 mapper 足够简单,这个将近一倍的开销还是有一点点意义的。

最后,欢迎回复给出更快的方法!

长按识别二维码关注《边际效应》
长按识别二维码关注《边际效应》

6 条评论

  • lbaby
    2013-04-10

    这个函数应该写成lambda的,本来最直观的就是最后一种,为啥你最后才想到。。。

    • Solrex Yang
      2013-04-10

      不同人的直觉,差别还是很大的。

  • 蜡烛在线
    2013-05-10

    有段时间没更新了呀

  • qing
    2013-05-11

    路过,留个言

  • yeye
    2013-07-20

    路过,我就是微博@你的那个人

  • yeye
    2013-07-20

    -.-尽然使用多说。。。这个是我的网址www.nightc.com

发表评论

电子邮件地址不会被公开。 必填项已用*标注