Bit Focus Bit Focus broadcast http://blog.bitfoc.us Redis Cluster 简单配置与动态扩容 http://blog.bitfoc.us/?p=524 http://blog.bitfoc.us/?p=524 Oct 23 2014 - 07:13:49 +0000 这里还有官方教程之后, 发现似乎必须用命令行来搞着, 而且官方提供的 redis-trib.rb 要求至少 3 个节点才能建立一个集群, 这规格是向党支部看齐么...
    至少 3 个节点这个还是略坑, 而且不能自动添加节点 (难道要我启动个 py 的 subprocess 去掉 ruby?), 于是去看看源代码, 惊讶地发现, 原来限制 3 个节点起步的是 ruby 脚本, 而且调集群加节点平衡负载其实都可以用 redis 命令来完成. 好吧, 那我自己来连 socket 搞总行了吧.
    结果一番折腾还真的可行的样子, 于是有了这篇文章和一个简单的工具. 那么首先说说怎么用 redis-cli 来做这些事情.

    如何在 redis-cli 手动启动集群呢, 请随意连上一个空的支持集群模式的节点, 然后执行
cluster addslots 0 1 2 ... 16383
    千万不要误会了, 中间那个 ... 可是要实打实地从头写到尾的哦. 所以如果可以的话, 手动写个脚本来干这事情吧.
    不过也可以略过这些步骤, 反正下面看看例子就行, 最后会给出一个 Python 工具来做这些.
    接下来的例子中, 假定已经开好了一个集群, 共有 3 个 master 节点. 要在控制台检视这些节点, 请用 redis-cli 随意连上其中一个, 并执行
cluster nodes
    输出
e7f4fcc0dd003fc107333a4132a471ad306d5513 127.0.0.1:8001 master - 0 1414033928009 3 connected 0-2729 8192-10921
bd239f7dbeaba9541586a708484cdce0ca99aba5 127.0.0.1:8000 master - 0 1414033929011 2 connected 2730-8191
787e06e9d96e6a9a3d02c7f3ec14e243882293e9 127.0.0.1:7999 myself,master - 0 0 1 connected 10922-16383
以上每一行是一个节点信息, 按空格分隔的域依次表示
  • 节点 ID
  • 节点地址
  • 节点角色 (master / slave), 如果是当前节点, 还会有个 myself
  • 对于 slave 而言, 其 master 节点的 ID
  • 最后一次 ping 时间戳
  • 最后一次 pong 时间戳
  • 节点顺序号
  • 节点连接状态
  • 之后的所有 : 节点所配给的槽位, 如果槽位连续, 就以 BEGIN-END 表示, 不连续的由空格隔开
    如果要向集群新增一个节点, 需要用 redis-cli 连上这个新节点, 调用一次 cluster meet 命令. 如
cluster meet 127.0.0.1 7999
后面参数是已经在集群中的节点中任意一个节点的地址及端口. 然后再来一次
e7f4fcc0dd003fc107333a4132a471ad306d5513 127.0.0.1:8001 master - 0 1414034715486 3 connected 0-2729 8192-10921
bd239f7dbeaba9541586a708484cdce0ca99aba5 127.0.0.1:8000 master - 0 1414034714983 2 connected 2730-8191
787e06e9d96e6a9a3d02c7f3ec14e243882293e9 127.0.0.1:7999 master - 0 1414034714482 1 connected 10922-16383
a0fa298711f5da94cb8acc0ed913970f7b00c7af 127.0.0.1:8010 myself,master - 0 0 0 connected
    就会发现这个节点已经加入集群, 但是没有被分配任何槽位. 现在得从原来几个节点搬运一些过来. 在执行这个操作前, 为了测试, 先向集群里扔一个值进去
set "foo14308" "bar"
这个键对应的槽位是 7 号. 等会儿就尝试将 7 号槽移动到新节点上.

    第一步, 锁定槽位. 这个操作需要分开进行. 首先用 redis-cli 连上新节点 (上述例子中端口 8010 的那个) 并执行
cluster setslot 7 importing e7f4fcc0dd003fc107333a4132a471ad306d5513
这表示即将从 ID 为 e7f4fcc0dd003fc107333a4132a471ad306d5513 的节点 (也就是 7 号槽位的所有者) 导入 7 号槽.
    接下来连上 7 号槽位的所有者所在的 8001 端口, 执行
cluster setslot 7 migrating a0fa298711f5da94cb8acc0ed913970f7b00c7af
    再执行
cluster getkeysinslot 7 10
    查看 7 号槽位的全部键 (参数 7 表示槽位, 参数 10 表示数量). 这样 redis 会回显刚才放进去的 "foo14308".
    现在开始手动迁移这些键. 在 8001 端口的客户端上执行
migrate 127.0.0.1 8010 foo14308 0 15000
    (最后两个参数, 其实我也不知道什么意思, 从 官方代码里 抄过来的)
    因为只有这一个键, 所以现在整个槽的迁移已经完成了, 需要告知整个集群 7 号槽位已经被新节点承包了, 官方源码里 这里进行了广播, 在命令行里的话似乎需要逐个连接节点, 执行以下命令
cluster setslot 7 node a0fa298711f5da94cb8acc0ed913970f7b00c7af
    搞完就好了.

    在知道以上这些的基础上, 做了一个简单的集群小工具, 能够在单节点上启动集群, 以及将一个新节点加入集群中并且自动平衡槽位. 此 Python 工具已加入 GitHub, 欢迎大家拍砖.
]]>
如何弄一个在不同站点做不同事情的 Chromium 扩展 http://blog.bitfoc.us/?p=523 http://blog.bitfoc.us/?p=523 Jul 18 2014 - 07:17:45 +0000     国内似乎有不少所谓的说好听叫资源聚合网站说直白叫盗文章的网站, 虽然鄙博客文章质量很一般, 但也至少被三个不同的网站全文抓取了 (http://outofmemory.cn/ http://www.taocms.org/ http://www.tuicool.com/). 其实流量点击量什么的都不是个事, 我也没打算靠写博客赚钱, 问题是这些网站长得都太残了. (tuicool 还好一点, outofmemory 代码都没用等宽字体你那网站能看! 简直白白浪费这么好个域名) 于是就有了这么个需求: 当访问到这些网站时自动跳转到原博客页面.
    当然了各位读者不必搞这么过河拆桥的需求, 大可写个插件去展开豆瓣页面上的那些短网址什么的.

    简单看一下 Chromium 扩展的结构, 无非就是一个配置文件 (manifest.json) 加上一些 JS 文件, 有必要的话再加上一些 HTML 文件. 这里就说说最简单的, 进入一个网站在页面加载完毕之后执行一个指定 JS 文件中的代码. 那么配置文件要这么写
{
  "name": "ExtensionName",
  "version": "0.1.0",
  "description": "ext descr",
  "browser_action": {
    "default_title": "Extension Title"
  },
  "content_scripts": [
    {
      "matches": ["http://ju.outofmemory.cn/entry/*"],
      "js": ["outofmemory.js"]
    }
  ],
  "manifest_version": 2
}
    以上 JSON 中, content_scripts 部分是个数组, 其中每个元素有至少两个属性, matches 表示在 URL 满足什么条件时加载脚本, 而 js 则是加载那些脚本; 如果扩展要用到 jQuery 之类的库, 可以加到此数组最前面.
    也就是说, 上面这个例子会在所有 URL 开头为 http://ju.outofmemory.cn/entry/ 的网页上, 调用 outofmemory.js 这个文件. 而这个文件的内容很简单
-function() {
    console.log('Hello world!');
    // window.location = document.getElementsByClassName('copyright')[0].getElementsByTagName('a')[1].href;
}()
    想了一下我还是把代码藏着点, 仍然用业界标准的 Hello world 来开场好了.
    新建一个目录, 把这两个文件保存在此目录下.
    点 Chromium 浏览器菜单 -> 工具 (Tools) -> 扩展程序 (Extensions), 勾选开发者模式 (Developer mode) 下面会刷出来 3 个按钮, 最左边就是加载野生扩展, 在对话框中选中刚才新建的目录, 这样扩展就上线了. 然后挑个页面进去看看控制台吧, 比如 http://ju.outofmemory.cn/entry/81081
    到此代码能执行了, 后面就没什么需要继续说的了, 剩下就是自己抓 DOM 看该怎么搞怎么搞吧.

    附项目地址
]]>
麻将听牌算法 [下篇] http://blog.bitfoc.us/?p=522 http://blog.bitfoc.us/?p=522 Jul 16 2014 - 05:43:49 +0000 上篇中分析了听牌可能有关字牌的情形, 具体包括字牌中有一个单张, 而剩下的数牌全能构成面子的单骑醒, 或者字牌中有个对子, 而剩下某数牌含有一个对子的双碰型或一个搭子的边/嵌张听牌. 这篇要讨论字牌全是刻子时的类似情况. 之所以说类似是由于此时数牌只可能有以下两种情况
  • 某一色数牌的牌总数模 3 余 1, 其它两个色都能恰好构成面子
  • 某两色数牌的牌总数摸 3 余 2, 剩下一色能恰好构成面子
体现成代码就是, 需要解决以下两个函数
def _waits_4groups(tiles):
    # 前略
    # 在前面情况不满足时, 调用如下实现
    return (_detect_numeric_suit_with_one_more(tiles) +
            _detect_2_numeric_suits_with_2_more(tiles))

# 找一个花色, 它的数量模 3 余 1
def _detect_numeric_suit_with_one_more(tiles):
    pass

# 找两个花色, 它们各自的牌的数量模 3 都余 2
def _detect_2_numeric_suits_with_2_more(tiles):
    pass
在上一篇代码的支援下, 后一个函数的实现相对容易一些, 如下
def _detect_2_numeric_suits_with_2_more(tiles):
    # 首先, 跟上节中实现的 _detect_numeric_suit_with_two_more 函数
    # 使用类似的方法, 找出是哪些花色多出两张牌
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 2:
        return []

    # 先看看剩下的那个花色是否能恰好完全构成面子, 如果不行, 那么后面也就不用继续了
    group_suit = mod_numerics[2][0]
    completed_groups = _completed_numeric_groups(
        group_suit, tiles.numerics[group_suit].copy_rank()).value()

    if completed_groups is None:
        return []

    # 调用上节实现的 _numeric_suit_with_two_more
    # 分别分析这两个花色的牌
    suit_2more_a, suit_2more_b = mod_numerics[0][0], mod_numerics[1][0]
    waits_a, flag_pair_a = _numeric_suit_with_two_more(
        suit_2more_a, tiles.numerics[suit_2more_a].copy_rank())
    waits_b, flag_pair_b = _numeric_suit_with_two_more(
        suit_2more_b, tiles.numerics[suit_2more_b].copy_rank())

    # 那么, 当其中一个花色有对子时, 另一个花色所缺的牌都是听牌
    # 特别地, 如果两个花色都没有对子, 即 flag_pair_a, flag_pair_b 都是 False 时
    # result 会是空集, 此时没有听牌
    result = []
    if flag_pair_a:
        result.extend(waits_b)
    if flag_pair_b:
        result.extend(waits_a)
    return result
    而 _detect_numeric_suit_with_one_more 会相对麻烦一点, 因为它内部也有单骑 (除了面子多出 1 张) 和一个对子加上一个搭子或对子 (多出 4 张) 两种情况.
    不过为了省代码, 就把这两个情况放一个循环里写了. 下面是实现.
def _detect_numeric_suit_with_one_more(tiles):
    # 先找出数量模 3 余 1 的那个花色, 以及, 看看剩下的两个花色能否都构成面子
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 1 or mod_numerics[1][1] != 0:
        return []
    suit_one_more = mod_numerics[0][0]
    group_suit_a, group_suit_b = mod_numerics[1][0], mod_numerics[2][0]
    completed_groups = (
        _completed_numeric_groups(
            group_suit_a, tiles.numerics[group_suit_a].copy_rank()) +
        _completed_numeric_groups(
            group_suit_b, tiles.numerics[group_suit_b].copy_rank())
    ).value()

    if completed_groups is None:
        return []

    tiles = tiles.numerics[suit_one_more].copy_rank()
    result = []
    for i, c in enumerate(tiles):
        # 如果某个牌至少有一张, 那么假定单骑这张牌; 去掉这一张, 试试剩下的能否全部构成面子
        if c != 0:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 1
            groups = _completed_numeric_groups(suit_one_more, copy_tiles)
            if groups.value() is not None:
                result.append(tile.Tile(suit_one_more, i))

        # 如果某个牌至少有两张, 那么假定该牌是对子
        # 去掉这个对子, 试试剩下的是不是一个搭子或对子加上面子
        if c >= 2:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 2
            result.extend(_numeric_suit_with_two_more(
                suit_one_more, copy_tiles)[0])

    return result
    如此便实现完毕了. 完整的源代码可以在这里看到.

    最后再放上测试代码, 保存为 test.py, 然后使用 python -m unittest test 来执行这些测试.
import unittest

import tile
import waits

# 为了简化手牌信息输入, 这里使用函数将字符串转换为手牌
# 如 123 234 555 11 22
#    前三个是数牌花色, 分别是 123 各一张, 555 各一张, 3 三张
#    第四个是风牌, 11 表示两个东 (2/3/4 则分别表示南/西/北)
#    最后一个是三元牌, 1/2/3 分别表示中/白/发 (其实对于三元牌来说哪个是哪个无所谓了)
#    如果某个位置是一个横线, 则表示该花色没牌
def str2hand_tiles(s):
    suits = s.split(' ')

    tiles = tile.HandTiles()
    for i in xrange(3):
        if suits[i] != '-':
            for s in suits[i]:
                tiles.numerics[i].add_rank(int(s) - 1)

    if suits[3] != '-':
        for s in suits[3]:
            tiles.wind.add_rank(int(s) - 1)

    if suits[4] != '-':
        for s in suits[4]:
            tiles.dragon.add_rank(int(s) - 1)
    return tiles

# 同样为了简化代码, 将字符串变成牌的集合, 各部分与上面的函数意义一致
def str2tile_set(s):
    suits = s.split(' ')
    tiles = set()

    for i in xrange(3):
        if suits[i] != '-':
            for s in suits[i]:
                tiles.add(tile.Tile(i, int(s) - 1))

    if suits[3] != '-':
        for s in suits[3]:
            tiles.add(tile.Tile(tile.WIND_SUIT, int(s) - 1))

    if suits[4] != '-':
        for s in suits[4]:
            tiles.add(tile.Tile(tile.DRAGON_SUIT, int(s) - 1))
    return tiles

NO_TILE = '- - - - -'


class Waits(unittest.TestCase):
    def assertWait(self, hand, waits_):
        self.assertSetEqual(str2tile_set(waits_),
                            waits.waits(str2hand_tiles(hand)))

    def test_13_orphans(self):
        self.assertWait('19 19 1999 123 12', NO_TILE)
        self.assertWait('19 19 199 124 123', '- - - 3 -')
        self.assertWait('19 19 19 1234 123', '19 19 19 1234 123')

    def test_7_pairs(self):
        self.assertWait('11 22 3 1122 1122', '- - 3 - -')
        self.assertWait('112233 111 - 1122 -', '- 1 - 12 -')

    def test_in_one_num_suit(self):
        self.assertWait('1 - - - -', '1 - - - -')
        self.assertWait('1223 - - - -', '2 - - - -')
        self.assertWait('1123 - - - -', '14 - - - -')
        self.assertWait('1233 - - - -', '3 - - - -')
        self.assertWait('2355 - - - -', '14 - - - -')
        self.assertWait('1234 - - - -', '14 - - - -')
        self.assertWait('2345699 - - - -', '147 - - - -')
        self.assertWait('2345678 - - - -', '258 - - - -')
        self.assertWait('2233 - - - -', '23 - - - -')
        self.assertWait('2333 - - - -', '124 - - - -')
        self.assertWait('2233445566 - - - -', '2356 - - - -')
        self.assertWait('2233445566678 - - - -', '23569 - - - -')
        self.assertWait('1112345677889 - - - -', '235689 - - - -')
        self.assertWait('2223333444456 - - - -', '1234567 - - - -')
        self.assertWait('2223456777999 - - - -', '12345678 - - - -')
        self.assertWait('1112345678999 - - - -', '123456789 - - - -')

    def test_in_two_num_suits(self):
        self.assertWait('11 11 - - -', '1 1 - - -')
        self.assertWait('12233 11 - - -', '14 - - - -')
        self.assertWait('11 23 - - -', '- 14 - - -')
        self.assertWait('11 13 - - -', '- 2 - - -')
        self.assertWait('23456 11 - - -', '147 - - - -')
        self.assertWait('11123 11123 - - -', '14 14 - - -')
        self.assertWait('23 13 - - -', NO_TILE)
        self.assertWait('11 11234567 - 111 -', '1 1 - - -')
        self.assertWait('11 11123456 - 111 -', '1 147 - - -')
        self.assertWait('11 11123 - 111222 -', '1 14 - - -')
]]>
麻将听牌算法 [上篇] http://blog.bitfoc.us/?p=521 http://blog.bitfoc.us/?p=521 Jul 02 2014 - 10:13:02 +0000     首先是数据结构, 这里用如下类来描述
# tile.py

# 牌
class Tile(object):
    def __init__(self, suit, rank):
        self.suit = suit # 花色: 用 0, 1, 2, 3, 4 表示
                         # 其中 0-2 是数牌 3 是风牌 4 是三元牌
        self.rank = rank # 数值: 对于数牌范围是 0-8 风牌范围 0-3 三元牌范围 0-2

    def __eq__(self, rhs):
        return self.suit == rhs.suit and self.rank == rhs.rank

    # 为了能让这东西被放进 set
    def __hash__(self):
        return hash(self.suit) * hash(self.rank)

    # 直观显示
    def __repr__(self):
        return (self.suit, self.rank + 1).__repr__()

# 一个花色里的牌
class TilesSuite(object):
    def __init__(self, count, suit):
        # 这个数字表示个数
        # 比如手牌是 2 个二万 3 个三万, 那么这个数组会是 [0, 2, 3, 0, 0, 0, 0, 0, 0]
        self.rank_count = [0] * count
        self.suit = suit

    def count(self, rank):
        return self.rank_count[rank]

    # 摸上来一张牌
    def add_rank(self, rank):
        self.rank_count[rank] += 1

    # 打出一张牌
    def remove_rank(self, rank):
        self.rank_count[rank] -= 1

    def copy_rank(self):
        return self.rank_count[:]

    # 去掉所有为 0 的项目, 返回一个元素结构为
    #    (牌, 数量)
    # 元组的列表
    def list_tiles(self):
        return [(Tile(self.suit, i), e)
                for i, e in enumerate(self.rank_count) if e != 0]

    # 这个花色下总共有几张牌
    def total(self):
        return sum(self.rank_count)

WIND_SUIT = 3   # 如之前提到的, 风牌的花色值为 3
DRAGON_SUIT = 4 #             三元牌的花色值为 4

# 一副手牌
class HandTiles(object):
    def __init__(self):
        # 三种数牌个数量分布
        self.numerics = [TilesSuite(9, i) for i in xrange(3)]
        # 风牌的数量分布
        self.wind = TilesSuite(4, WIND_SUIT)
        # 三元牌的数量分布
        self.dragon = TilesSuite(3, DRAGON_SUIT)

    def total(self):
        return (sum([self.numerics[i].total() for i in xrange(3)]) +
                self.wind.total() + self.dragon.total())

    def list_tiles(self):
        return (sum([self.numerics[i].list_tiles() for i in xrange(3)], []) +
                self.wind.list_tiles() + self.dragon.list_tiles())
    (有关的翻译部分参考这里, 以及维基百科英文)
    在只处理听牌时, 以上结构中的风牌和三元牌其实可以合并到一起, 但若要处理和牌后的役还是暂且分开了.

    下面按日麻规则会处理三种截然不同的牌型听牌: 标准的 4 面子 1 对子; 七对子; 国士無双. 这三种情况应该分成三个对应的函数, 下面来起个头.
# waits.py

def waits(tiles):
    return set(_waits_13(tiles) + _waits_7pairs(tiles) + _waits_4groups(tiles))

# 国士 13 面听的全部牌, 容我写死在这里
_13_ORPHANS_WAITS = (
    [tile.Tile(0, 0), tile.Tile(0, 8), tile.Tile(1, 0), tile.Tile(1, 8),
     tile.Tile(2, 0), tile.Tile(2, 8)] +
    [tile.Tile(tile.WIND_SUIT, i) for i in xrange(4)] +
    [tile.Tile(tile.DRAGON_SUIT, i) for i in xrange(3)])

def _waits_13(tiles):
    if tiles.total() != 13:
        return []

    # 将手牌里的 13 种幺九字牌弄出来
    # 组成一个元素结构为
    #    (牌, 数量)
    # 元组的列表, 并对这个列表进行排序, 排序的键是上述元组中的 "数量"
    orphans = sorted(
        [(tile.Tile(s, 0), s.count(0)) for s in tiles.numerics] +
        [(tile.Tile(s, 8), s.count(8)) for s in tiles.numerics] +
        [(tile.Tile(tile.WIND_SUIT, i), tiles.wind.count(i))
         for i in xrange(4)] +
        [(tile.Tile(tile.DRAGON_SUIT, i), tiles.dragon.count(i))
         for i in xrange(3)], key=lambda k: k[1])
    # 如果这个列表开头两项的数量都为 0 (因为排序了所以只要看第二项是不是 0) 肯定不是国士听牌
    if orphans[1][1] == 0:
        return []
    # 而如果第一项的数量就是 1 那么一定就是 13 面听了
    if orphans[0][1] == 1:
        return _13_ORPHANS_WAITS
    # 否则听的牌就是缺的那个
    return [orphans[0][0]]

def _waits_7pairs(tiles):
    if tiles.total() != 13:
        return []
    # 列出当前所有牌以及该牌的数量
    tiles_list = tiles.list_tiles()

    # 如果牌的种类大于 7 肯定不是七对子听牌
    # 一般的日麻规则中不允许七对子出现两个相同的对子, 若按照这个规则此处判断应该是严格等于 7,
    if 7 < len(tiles_list):
        return []

    # 如果数量为奇数的牌恰好 1 个就是七对子听牌
    odds = [t[0] for t in tiles_list if t[1] % 2 == 1]
    return odds if len(odds) == 1 else []

def _waits_4groups(tiles):
    pass
    最后的 4 面子 1 对子听牌判定就稍复杂, 情况比较多. 从字牌的数量状况下手比较容易理清头绪. 考虑到听牌时, 如果字牌不是恰好全是刻子, 那么只有下面两种情况
  • 字牌中有一个对子
  • 字牌单骑 (为了简单起见, 如果手牌中有 4 张相同的字牌, 判定为刻子加上多出的那一张单骑; 拆成一个对子加上另一个对子其实是等价的)
从这个角度出发还有个好处, 在开局手牌比较乱的情况下, 先处理字牌有利于直接判定某个手牌形式根本没有听牌 (比如字牌中有两张单的, 或一个对子一张单的), 那样就不用去分解数牌了.
    废话不多说了, 实现如下
def _wind_dragon_groups(tiles):
    # 按照 (牌, 数量) 的方式列出全部字牌
    tiles_list = tiles.wind.list_tiles() + tiles.dragon.list_tiles()
    if len(tiles_list) == 0:
        return [], [], []
    singles = [t for t in tiles_list if t[1] == 1]
    pairs = [t for t in tiles_list if t[1] == 2]
    triplets = [t for t in tiles_list if t[1] == 3]
    quads = [t for t in tiles_list if t[1] == 4]
    # 如刚才所说 4 张牌被认为是 1 个刻子加上 1 个单张, 所以 quads 也会被加进 triplets 和 singles 中
    return triplets + quads, pairs, singles + quads

def _waits_4groups(tiles):
    triplets, pairs, singles = _wind_dragon_groups(tiles)
    if pairs and singles: # 同时有单张和对子, 没听牌
        return []
    if 1 == len(singles): # 字牌单骑, 如果剩下的数牌都能拆解成面子, 那么听牌就是被单骑的那个
        groups = _detect_completed_numeric_groups(tiles)
        return [] if groups is None else [singles[0][0]]
    if 2 == len(pairs): # 字牌里有两个对子, 如果剩下的数牌都能拆解成面子, 那么就是双碰听牌
        groups = _detect_completed_numeric_groups(tiles) # 见下方
        return [] if groups is None else [pairs[0][0], pairs[1][0]]
    if 1 == len(pairs): # 有一个对子, 如果剩下有某一个数牌能被拆解成面子 + 1 个搭子 / 1 个对子, 那么就能听牌
        waits, pair_wait = _detect_numeric_suit_with_two_more(tiles) # 见下方
        if len(waits) == 0:
            return []
        if pair_wait:
            waits.append(pairs[0][0])
        return waits
    # 字牌全是刻子或没有字牌的情况

# 这个函数用于检测是不是剩下的所有数牌都可以被分解成面子, 这是下一节的课题
# 如果可以, 那么这个函数会返回所有的面子列表; 否则会返回 None
def _detect_completed_numeric_groups(tiles):
    pass

# 这个函数用于检测手牌中是否两个花色都能被拆解成面子
# 而另一个花色的牌去掉一个搭子或去掉一个对子之后也能全部拆解成面子
# 这个函数返回 2 个值, 分别是
#    若拆解成功, 返回搭子所缺的牌的列表 (空列表表示拆解失败)
#    若拆解成功, 返回去掉一个对子后是否能完全拆解为面子
def _detect_numeric_suit_with_two_more(tiles):
    pass
    具体说一下 if 1 == len(pairs) 这个分支要做的事情. 分支第一句话会得到一个二元组 waits, pair_wait, 根据下面计划会实现的函数的描述, waits 表示这个花色中除了面子剩下的搭子缺什么, 那么缺什么就会听什么; 还有一种情况, 就是 pair_wait 是真, 也就是说可能这是个双碰听牌, 这样的话该字牌对子本身也是所听的牌之一. 具体的例子如
  • 数牌为 "二万 三万", 此时返回值为 ([一万 四万], False) (两面听)
  • 数牌为 "一万 三万", 此时返回值为 ([二万], False) (嵌张)
  • 数牌为 "三万 三万", 此时返回值为 ([三万], True) (双碰)
  • 数牌为 "二万 三万 四万 四万 四万", 此时返回值为 ([一万 四万], True) (复合听)
这个分支也就是在以上情况中选择是否将字牌加入所听的牌的列表中.

    而无论是实现 _detect_completed_numeric_groups 还是 _detect_numeric_suit_with_two_more 都依赖于一个算法: 将数牌拆解成面子. 实现这个函数之前先弄几个类似 list 的数据结构, 用于混合正常返回和错误返回. (虽然这并不是最好的设计)
# group.py

class Group(object):
    pass

# 顺子
class Sequence(Group):
    def __init__(self, suit, starting_rank):
        self.suit = suit
        self.starting_rank = starting_rank

# 刻子
class Triplet(Group):
    def __init__(self, suit, rank):
        self.suit = suit
        self.rank = rank

# 没有分组, 此类的实例表示错误的返回值
class NoGroup(object):
    def value(self):
        return None # 这个特殊的返回值将会作为标记使用

    def __add__(self, rhs):
        return self

    def append_group(self, group):
        return self

# 分组, 此类的实例就是面子分组列表
class Groups(list, NoGroup):
    def __init__(self, value=None):
        list.__init__(self, value or [])

    def value(self):
        return self

    def __add__(self, rhs):
        if type(rhs) is NoGroup: # 如果加上错误值则为错误值
            return NoGroup()
        return Groups(list.__add__(self, rhs))

    def append_group(self, group):
        self.append(group)
        return self
    那么接下来就是分组函数了. 返回值是上面的 NoGroup 实例, 或它子类 Groups 的实例.
def _completed_numeric_groups(suit, suit_tiles):
    for i, c in enumerate(suit_tiles):
        if c != 0:
            first_rank = i # 找到该花色下序数最小的一张牌, 记下它的序数
            break
    else:
        return group.Groups() # 如果该花色下已经没牌了, 那么分组有效, 只不过是空的

    # 因为此时该牌序数最小, 如果此牌数量不小于 3, 那么肯定最终会被分解成刻子
    # 或者是三个相同的顺子, 但这种情况被分解成三连刻也没有问题
    if suit_tiles[first_rank] >= 3:
        tri = group.Triplet(suit, first_rank)
        suit_tiles[first_rank] -= 3 # 将这个刻子独立出来, 剩下地牌递归处理
        return _completed_numeric_groups(suit, suit_tiles).append_group(tri)

    # 如果序数最小的牌不形成刻子, 那么以下情况不可能组成合理的顺子
    #    这个牌序数太靠后 (>6)
    #    序数比此牌大 1 或大 2 的牌的数量少于此牌
    if (first_rank > 6 or suit_tiles[first_rank] > suit_tiles[first_rank + 1]
            or suit_tiles[first_rank] > suit_tiles[first_rank + 2]):
        return group.NoGroup()

    # 如果满足组成顺子的条件, 那么将构成这些顺子的牌给扣除, 剩下的牌再递归处理
    seqs = [group.Sequence(suit, first_rank)
            for _ in xrange(suit_tiles[first_rank])]
    suit_tiles[first_rank + 1] -= suit_tiles[first_rank]
    suit_tiles[first_rank + 2] -= suit_tiles[first_rank]
    suit_tiles[first_rank] = 0
    return _completed_numeric_groups(suit, suit_tiles) + seqs
    有了以上实现, 那么检测 3 种花色是否都各自形成面子就很容易了
def _detect_completed_numeric_groups(tiles):
    for i in xrange(3):
        if tiles.numerics[i].total() % 3 != 0:
            return None
    return sum([_completed_numeric_groups(i, tiles.numerics[i].copy_rank())
                for i in xrange(3)], group.Groups()).value()
    而检测某个花色多出来两个, 剩余两个花色全是面子则会繁琐许多
def _detect_numeric_suit_with_two_more(tiles):
    # 首先得判断到底是哪个花色多出两个
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    # 将 (花色 ID, 该花色牌的数量对 3 取模) 这个元组序列按 "模 3 的余数" 进行排序
    # 如果满足前提, 那么当然第一个值的余数是 2, 而后两个都是 0
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 0:
        return [], False

    # 然后先检测这两个花色是不是恰好都能分解成面子, 如果不是, 那么也就没有继续下去的必要了
    group_suit_a, group_suit_b = mod_numerics[1][0], mod_numerics[2][0]
    completed_groups = (
        _completed_numeric_groups(
            group_suit_a, tiles.numerics[group_suit_a].copy_rank()) +
        _completed_numeric_groups(
            group_suit_b, tiles.numerics[group_suit_b].copy_rank())
    ).value()

    if completed_groups is None:
        return [], False

    # 下面会有一堆函数涵盖在一个花色多出 2 张牌时的各种情况
    suit_two_more = mod_numerics[0][0]
    return _numeric_suit_with_two_more(
        suit_two_more, tiles.numerics[suit_two_more].copy_rank())

def _numeric_suit_with_two_more(suit, tiles):
    # 如果多出来的是对子
    result = [tile.Tile(suit, pair_rank) for pair_rank, groups in
              _numeric_groups_with_pair(suit, tiles[:])]
    flag_pair = len(result) != 0 # 记得设置对子 flag

    # 如果多出来的是两面搭子
    for starting_rank, groups in _numeric_groups_with_side_waits(
            suit, tiles[:]):
        if starting_rank != 0:
            result.append(tile.Tile(suit, starting_rank - 1))
        if starting_rank != 7:
            result.append(tile.Tile(suit, starting_rank + 2))

    # 如果多出来的是嵌张
    result.extend([
        tile.Tile(suit, staring_rank + 1)
        for staring_rank, groups in _numeric_groups_with_middle_waits(
            suit, tiles[:])])

    return result, flag_pair

def _numeric_groups_with_pair(suit, suit_tiles):
    result = []
    for i, c in enumerate(suit_tiles):
        # 找到一个对子, 去掉它, 试试剩下的能不能全凑成面子
        if c >= 2:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 2
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result

def _numeric_groups_with_side_waits(suit, suit_tiles):
    result = []
    for i in xrange(8):
        # 找出一个搭子, 去掉之后试试剩下的能不能全凑成面子
        if suit_tiles[i] and suit_tiles[i + 1]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 1] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result

def _numeric_groups_with_middle_waits(suit, suit_tiles):
    result = []
    for i in xrange(7):
        # 找出一个两坎, 去掉之后试试剩下的能不能全凑成面子
        if suit_tiles[i] and suit_tiles[i + 2]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 2] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result
    最后的各个函数返回值类型均为元素结构为 (对子或搭子首张序数, 面子分组) 的列表.

    这样所有听牌与字牌可能相关的情况讨论完毕. 而无字牌或字牌全为刻子的情况则会在下篇中讨论.
]]>
数学证明的边界扩张 http://blog.bitfoc.us/?p=520 http://blog.bitfoc.us/?p=520 May 16 2014 - 01:42:10 +0000 证明与反驳这本书, 虽然不是什么数学著作, 讨论的也不是改变世界的重要定理, 不过围绕着多面体面棱角个数关系的那个欧拉定理讲得风生水起, 还是挺有意思的.
    书里提到数学研究的一个策略, 对于一个已经证明的定理, 通过想方设法扩张其证明步骤中的条件「边界」, 也许可以把定理从一个特殊形式扩展到普遍形式. 就像写程序库一样, 总希望写出来的东西能尽可能满足各种不同参数下的需求, 虽然在软件行业这么干往往会把自己玩死...
    比如看看费马平方和定理第四步的结论 (请一定看完前四步证明, 后文的内容均是修改此证明)
  • 对于互素的任意整数 a 和 b, a2 + b2 的每一个因子也都能表示为两个整数的平方和的形式
    这一步虽然内容上有不少平方和, 不过还不是平方和定理实际内容, 只是一步中间引理. 然而即使如此证明看起来也挺费神的.
    要扩展这个定理的话, 可以从多个不同角度出发, 对于两个整数平方和成立, 对于三个整数平方和是否成立; 或者, 本文将采取的方式如下
  • 给定正整数 v, u, 对于互素的任意整数 a 和 b, v * a2 + u * b2 的每一个因子也都能表示为 v * p2 + u * q2 的形式
    然后试着往原来的证明过程中套, 看看会发生什么.

    第一步用到了名字巨长的恒等式, 这个等式说两个平方和的乘积还是一个平方和, 在代数学中有个术语叫封闭性. 比如整数集里面任取两个元素出来进行加减乘运算, 结果还是整数 (除就不一定了), 那么加减乘这三种运算 (三个二元函数) 对于整数集就是封闭的. 类似的, 上述恒等式说明在所有能表示成两个整数平方和的数的集合内, 乘法是封闭的.
    那么这个结论能否运用到形如 v * a2 + u * b2 的整数呢? 很快就能验证
(v * a2 + u * b2) * (v * c2 + u * d2)
  = v2 * (ac)2 + vu * ((ad)2 + (bc)2) + u2 * (bd)2
  = v2 * (ac)2 + u2 * (bd)2 + 2 * uv * abcd
    + vu * ((ad)2 + (bc)2- 2 * uv * abcd
  = (vac + ubd)2 + vu(ad - bc)2
    并不是 (v * p2 + u * q2) 而是 (p2 + vu * q2) 的形式. 真糟糕, 第一步封闭性就阵亡了. 那么今天的内容就到这里, 谢谢大家观看, 我们下期节目再见...
    噢等等, 我觉得这个扩张还可以抢救一下, 只要作出一点小牺牲, 把内容收缩一点就好: 令 v, u 之一等于 1, 也就是说变成比如
  • 给定正整数 u, 对于互素的任意整数 a 和 b, a2 + u * b2 的每一个因子也都能表示为 p2 + u * q2 的形式
    还是可以继续下去的, 至少
(a2 + u * b2) * (c2 + u * d2)
    = (ac + ubd)2 + u(ad - bc)2
    = (ac - ubd)2 + u(ad + bc)2
    确实是两种 p2 + u * q2 的形式.

    虽然 p2 + u * q2 这么个不对称的形式肯定会让强迫症加数学美学狂热者想要砸显示器, 不过也没办法, 将就着到第二步:
  • 给定整数 u, 对于任意整数 a, b (不要求互素), 如果形如 (a2 + u * b2) 的整数能被可表示为 (p2 + u * q2) 的素数整除, 则其商也能表示为以上形式
    如果想挑战一下, 别继续滚页面, 自己推演一下.
    答案将在三行之后开始揭晓.
    第一行. 回头再看一眼命题第一句, 是「给定任意整数 u」. 这个正是很重要的, 虽然第一步恒等式对于任意整数 u 都能成立, 但若 u 不是正数, 这一步证明会有一个不严格的地方, 而第四步中若 u 不是一个正数则完全是硬伤.
    第二行. 来个简单有效的反例, 在 u = -1 时, 随便令 a 和 b 为两个不同的奇素数, 显然 a2 - b2 会是个偶数, 能被 2 整除, 但 2 没法写成平方差的形式.
    第三行. 具体为什么, 到最后一步再说吧. 接下来继续证明.
    因为 (p2 + u * q2) 能整除 (a2 + u * b2), 那么它肯定能整除 u * q2 * (a2 + u * b2), 从而也就能整除
u * q2 * (a2 + u * b2) - a2 * (p2 + u * q2)
    = (ubq)2 - (ap)2 = (ubq + ap) * (ubq - ap)
    根据算术基本定理惟一性证明的引理, 作为素数的 (p2 + u * q2) 能整除 (ubq + ap) 与 (ubq - ap) 两个数之积, 那么必须能至少整除其中某一个.
    假设整除的是 (ubq + ap), 那么
(a2 + u * b2) * (p2 + u * q2) = (ap + ubq)2 + u(aq - bp)2
    两边同除以 (p2 + u * q2)2
(a2 + u * b2) / (p2 + u * q2) = ((ap + ubq) / (p2 + u * q2))2 + u((aq - bp) / (p2 + u * q2))2
    显然等式左边是一个整数, 右边有两项, 其中第一项根据假设是一个整数, 那么第二项也得是个整数, 因此? 第二项似乎正好是 ux2 的形式, 证明搞定?
    似乎又糟糕了, u((aq - bp) / (p2 + u * q2))2 是一个整数并不能说明 ((aq - bp) / (p2 + u * q2)) 是一个整数, 有一种可能是 (p2 + u * q2) 恰能整除 u, 而不是能整除 (aq - bp), 使得这一项最终为整数; 如果是这样, 第二项的 u 这个因子就会被削减得小一点, 因而形式并不成立.
    万幸地是, 很显然 u 怎么可能被比 u 自己还大的素数 (p2 + u * q2) 整除? (p, q 必须全不为 0, 否则此数不是一个素数, 因此它肯定比 u 大; 但是刚才说了, 在 u 为负数的情况下则不然, 一个例子是, 当 u = -2 时, p, q 分别取 p = 2, q = 1, 代入得 2 * 2 - 2 * 1 * 1 = 2 可以整除 u) 所以右边的第二项确实是满足要求的.

    刚才说到, (p2 + u * q2) 至少能整除 (ubq + ap) 与 (ubq - ap) 两者之一, 并在假设能整除前者时命题成立. 现在还得证明能整除后者的情况. 若这种情况发生, 则采用另一种表示方式
(a2 + u * b2) * (p2 + u * q2) = (ap - ubq)2 + u(aq + bp)2
    故伎重演, 同除以 (p2 + u * q2)2, 结果
(a2 + u * b2) / (p2 + u * q2) = ((ap - ubq) / (p2 + u * q2))2 + u((aq + bp) / (p2 + u * q2))2
    这样就安全通过第二步了.

    第三步: 如果一个能表示为 (a2 + u * b2) 的整数被另一个不能表示为 (a2 + u * b2) 的整数整除, 则它们的商也必有一个不能表示为 (a2 + u * b2) 的因子.
    这一步是反证法, 没什么好说的, 跟 Wiki 上证明的说辞类似.

    激动人心的最后一步终于来了.
    先剧透一下, 其实 u 除了 1 之外, 只有 2 能过这一步, 也就是说到头来只多证明了所有形如 (a2 + 2 * b2) 的整数的所有因子有同样形式...
    如果各位看官直觉敏锐, 早先也许就能想到了, 类似 u = -1 的情况, 在 u > 2 时, 如果 (a2 + u * b2) 是个偶数, 因子 2 是不能写成 (a2 + u * b2) 的形式的 orz..
    不过 u=3 的时候能证明一个特性命题, 虽然不那么完美. 后述.
    最后一步其实也没什么花样, 跟 Wiki 证明一样, 设因子为 x, 且
a = mx + c
b = nx + d
则有
zx = a2 + u * b2 = Ax + c2 + u * d2 (中略)
    <= (x/2)2 + u * (x/2)2 = x2 * (1 + u) / 4

z <= x * (1 + u) / 4
就是这个不等式右边坏事了, 不等式右边必须是一个严格小于 x 的数, 这样才使得 z < x 必然成立, 后面的证明用到的无穷下降法才能进行下去. 如此以来只有 u < 3 时才行. 但是 u 又不能是负数, 特别负得太厉害的时候, 会导致右边是个负数, 这样与 x 乘在一起的另外的因子也必须是负数, 当把这个校正成正数的时候, 硬伤来了: 不等式的不等号由 <= 变成了 >=, 这还怎么下降怎么收场?!

    最后说一下 u=3 时的特别情况.
    还是回到刚才的不等式的右边, 如果 x 是奇数的话, c 和 d 都不可能正好等于分数 (x / 2), 因此不等式的符号就可以由小于等于换成严格小于. 此时无穷下降法成立. 也就是说, 对于互素整数 a 和 b, 所有形如 (a2 + 3 * b2) 的奇数因子都能写成同样形式.
    如果 a, b 是一奇一偶, (a2 + 3 * b2) 是一个奇数, 这样其所有因子都是奇数.
    如果 a, b 是两个奇数, 容易证明 (a2 + 3 * b2) 能被 4 整除, 但不可能被 8 整除. 这造成了一个有趣的结论: 该数的所有奇数因子, 以及能被 4 整除的因子都能写成此形式 (因为虽然 2 不能表示成 p2 + 3 * q2, 但是代入 p = q = 1 却正好等于 4).
]]>
VerbalExpressions 与状态机词法分析器 http://blog.bitfoc.us/?p=519 http://blog.bitfoc.us/?p=519 May 06 2014 - 08:40:39 +0000 VerbalExpressions    说到字符串检索分析替换修改自然会想到正则表达式, 不过这东西实在是一个只写语言. 更改系统中一个一般复杂的正则表达式, 传统的读懂代码然后替换一条语句或者加上一个分支或者参数的模式不管用, 而是直接重写, 就像清理一个塞满的垃圾桶, 方法不是把垃圾一点点挖出来, 而是整个倒掉再铺上新的垃圾袋; 正则表达式有时太复杂了, 一条语句一个调用就顶过一打的循环和分支.
    人们总会想到一些更节省脑细胞的方式来对付字符串, 让机器理解人类的咒语, 于是发明了 VerbalExpressions.
    下面是一个 JS 的例子
var tester = VerEx()
            .startOfLine()
            .then("http")
            .maybe("s")
            .then("://")
            .maybe("www.")
            .anythingBut(" ")
            .endOfLine();
    上面这一串等价于 /^(http)(s)?(\:\/\/)(www\.)?([^\ ]*)$/ 这么个正则表达式, 不过书写起来显得科学多了; 如果需要更改逻辑, 也很容易下手到底是什么地方需要增加或者减少一点什么.

基于自动机的词法分析器

    这个轮子很有启发性, 于是乎想到以类似的方式构造个词法解析器. 接口上的愿景是类似
var t = Tokenizer();
t.simpleSymbols('+-*/=', 'operator')
 // ...
 .ignore(' ')
 .ignore('\t')
 .ignore('\r')
 // ...
 // 上面都是单独的一个字符, 接下来是循环的模式
 .loop(DIGITS)
 .accept('integer') // 以 0-9 循环的模式, 接受为整数类型

 .startWith(LETTERS)
 .loop(LETTERS + DIGITS)
 .accept('identifier') // 以字母开头, 数字和字母循环的模式, 接受为标识符

 // 接下来是保留字
 .fixed('if')
 .fixed('for')
 // 以及一些超过 1 字符的操作符
 .fixed('==', 'operator')
 .fixed('<=', 'operator')
 // ...
;
var inputString = 'for (i = 0; i < 10; i = i + 1) { if (i % 3 == 0) { print(i); } }';
var tokenArray = t.tokenize(inputString);
console.log(tokenArray);
    看起来应该是这么回事. 以这种方式构造出来的东西应该是一个状态机而不是一大波正则表达式形成的集群. 因此首先得构造一个状态数据结构. 作为一个演示就不弄太复杂了, 它看起来类似
var State = {
    '0': nextState0,
    '1': nextState1,
    a: nextStateA,
    // 以上是一个超大状态映射表, 将每个可能遇到的字符映射到下一个状态
    // 这是最纯天然最暴力的状态机实现方法, 但原则上应该将这些东西弄成一个函数
    // 因为映射全部的字符 (超过 216 个 Unicode 字符) 是不现实的
    // 所以先假定 : 测试数据只含有 ASCII 字符

    // 以下是每个状态本身的性质
    _ignore: true, // 这个状态被忽略; 不引起错误, 也不产生结果, 如空格
    _type: 'integer' // 接受的类型, 如 'integer', 'identifier'
};
    接下来就要提供构造状态跳转网络的接口, 即前面愿景中的 simpleSymbols, ignore, loop, startWith, fixed 等等. 在编译原理中任何一个自动机都要有初始状态, 在下面的代码中将命名其为 entryState; 现实中还需要一个忽略状态, 它会被称为 ignoreState.
    以下是 simpleSymbols 的实现
var entryState = {};
var ignoreState = {_ignore: true};

function simpleSymbols(symbols, name) {
    var symbolState = {_type: name};
    for (var i = 0; i < symbols.length; ++i) {
        var ch = symbols[i];
        if (entryState[ch]) {
            throw 'duplicate entry: ' + ch;
        }
        entryState[ch] = symbolState;
    }
    // 之前写的是链式操作, 那就得返回 this, 虽然目前这个函数并没有处于任何合适的对象上下文中
    return this;
}
    如此以来, 当调用 simpleSymbols('+-*/=', 'operator') 之后, entryState'+-*/=' 这些字符各自对应的状态映射被指向相同的一个 symbolState, 该状态的类型是 operator.
    ignore 函数的实现如下, 将 entryStateignoreState 连接起来
function ignore(symbols) {
    for (var i = 0; i < symbols.length; ++i) {
        var ch = symbols[i];
        entryState[ch] = ignoreState;
        ignoreState[ch] = ignoreState;
    }
    return this;
}
    比较麻烦的是 startWith, loop, accept 这一组, 可能还有其它的函数, accept 是最后收尾的, 而在之前可能多次以不同的方式调用 startWith, loop, 并且 startWith 还能省略. 这样产生了一些单个函数无法控制的状态转换, 必须新弄一个什么来记录
var stateTrace = [];

function startWith(symbols) {
    if (stateTrace.length) {
        throw 'already started';
    }
    var startState = {};

    for (var i = 0; i < symbols.length; ++i) {
        var ch = symbols[i];
        if (entryState[ch]) {
            throw 'duplicate entry: ' + ch;
        }
        entryState[ch] = startState;
    }

    stateTrace.push(startState);
    return this;
}

function loop(symbols) {
    if (stateTrace.length === 0) {
        startWith(symbols);
    }
    var currentState = stateTrace[stateTrace.length - 1];
    for (var i = 0; i < symbols.length; ++i) {
        var ch = symbols[i];
        currentState[ch] = currentState;
    }
    return this;
}

function accept(type) {
    if (stateTrace.length === 0) {
        throw 'pattern not started';
    }
    var currentState = stateTrace[stateTrace.length - 1];
    currentState._type = type;
    stateTrace.length = 0; // 清空状态栈
    return this;
}
    要点就是 stateTrace 这个状态栈保存当前进行到何处这一信息. (loop 的实现有瑕疵, 因为重复调用 loop 竟不会产生新的状态, 这显然与直觉不一致; 有兴趣的话可以尝试修复这个 bug)

    其它类似的函数就不赘述了. 最后说说这个状态机的状态跳转都构造完成后, 如何使用它来切割字符串.
function tokenize(input) {
    var state = entryState;
    var token = []; // 当前词元包含的字符
    var result = [];

    // 处理下一个字符
    function nextChar(ch) {
        // 如果下一个字符可以直接跳转状态
        if (state[ch]) {
            // 那就跳转状态呗
            state = state[ch];
            if (!state._ignore) {
                token.push(ch);
            }
            return;
        }
        // 下一个字符跳不动了, 看看这个状态是否有类型, 即被接受
        if (state._type) {
            // 把之前临时存储的字符打包在一起, 作为一个被接受的词元
            result.push({
                token: token.join(''),
                type: state._type
            });
            // 当前字符本身还需要被处理
            return resetConsume(ch);
        }
        // 好吧, 字符跳不动了, 而当前停留的状态也不是一个接受状态
        if (state._ignore) {
            // 不过幸好这是需要忽略的
            return resetConsume(ch);
        }
        // 万般无奈只能报错了
        throw 'unexpected character';
    }

    // 重置状态并处理接下来的第一个字符
    function resetConsume(ch) {
        token.length = 0;
        state = entryState;
        nextChar(ch);
    }

    for (var i = 0; i < input.length; ++i) {
        nextChar(input[i]);
    }
    // 当遍历所有字符后, 可能停留在一个可接受的状态上
    if (token.length !== 0 && state) {
        result.push({
            token: token.join(''),
            type: state._type
        });
    }
    return result;
}
    零碎的代码逻辑大概就是这样了. 完整的例子请看这里.
]]>
就算是 Linux 命令行只要有爱就能剪辑 MAD 了吧 http://blog.bitfoc.us/?p=518 http://blog.bitfoc.us/?p=518 Mar 22 2014 - 13:03:30 +0000 http://zlo.gs/p/neuront/linux-dakedo-ai-sae-areba-mad-dekiru-yone
]]>
索引统计与 Python 字典 http://blog.bitfoc.us/?p=517 http://blog.bitfoc.us/?p=517 Jan 01 2014 - 05:16:40 +0000
    索引引擎的基本工作原理便是倒排索引, 即将一个文档所包含的文字反过来映射至文档; 这方面算法并没有太多花样可言, 为了增加效率, 索引数据尽可往内存里面搬, 此法可效王献之习书法之势, 只要把十八台机器内存全部塞满, 那么基本也就功成名就了. 而基本思路举个简单例子, 现在有以下文档 (分词已经完成) 以及其包含的关键词
  • doc_a: [word_w, word_x, word_y]
  • doc_b: [word_x, word_z]
  • doc_c: [word_y]
将其变换为
  • word_w -> [doc_a]
  • word_x -> [doc_a, doc_b]
  • word_y -> [doc_a, doc_c]
  • word_z -> [doc_b]
    写成 Python 代码, 便是
doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']}
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']}
doc_c = {'id': 'c', 'words': ['word_y']}

docs = [doc_a, doc_b, doc_c]
indices = dict()

for doc in docs:
    for word in doc['words']:
        if word not in indices:
            indices[word] = []
        indices[word].append(doc['id'])

print indices
    不过这里有个小技巧, 就是对于判断当前词是否已经在索引字典里的分支
if word not in indices:
    indices[word] = []
可以被 dictsetdefault(key, default=None) 接口替换. 此接口的作用是, 如果 key 在字典里, 那么好说, 拿出对应的值来; 否则, 新建此 key, 且设置默认对应值为 default. 但从设计上来说, 我不明白为何 default 有个默认值 None, 看起来并无多大意义, 如果确要使用此接口, 大体都会自带默认值吧, 如下
for doc in docs:
    for word in doc['words']:
        indices.setdefault(word, []).append(doc['id'])
    这样就省掉分支了, 代码看起来少很多.
    不过在某些情况下, setdefault 用起来并不顺手: 当 default 值构造很复杂时, 或产生 default 值有副作用时, 以及一个之后会说到的情况; 前两种情况一言以蔽之, 就是 setdefault 不适用于 default 需要惰性求值的场景. 换言之, 为了兼顾这种需求, setdefault 可能会设计成
def setdefault(self, key, default_factory):
    if key not in self:
        self[key] = default_factory()
    return self[key]
倘若真如此, 那么上面的代码应改成
for doc in docs:
    for word in doc['words']:
        indices.setdefault(word, list).append(doc['id'])
不过实际上有其它替代方案, 这个最后会提到.

    如果说上面只是一个能预见但实际上可能根本不会遇到的 API 缺陷, 那么下面这个就略打脸了.
    考虑现在要进行词频统计, 即一个词在文章中出现了多少次, 如果直接拿 dict 来写, 大致是
def word_count(words):
    count = dict()
    for word in words:
        count.setdefault(word, 0) += 1
    return count

print word_count(['hiiragi', 'kagami', 'hiiragi', 'tukasa', 'yosimizu', 'kagami'])
    当你兴致勃勃地跑起上面代码时, 代码会以迅雷不及掩脸之势把异常甩到你鼻尖上 --- 因为出现在 += 操作符左边的 count.setdefault(word, 0) 在 Python 中不是一个左值. 怎样, 现在开始念叨 C艹 类型体系的好了吧.

    因为 Python 把默认的字面常量 {} 等价于 dict() 就认为 dict 是银弹的思想是要不得的; Python 里面各种数据结构不少, 解决统计问题, 理想的方案是 collections.defaultdict 这个类. 下面的代码想必看一眼就明白
from collections import defaultdict

doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']}
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']}
doc_c = {'id': 'c', 'words': ['word_y']}

docs = [doc_a, doc_b, doc_c]
indices = defaultdict(list)

for doc in docs:
    for word in doc['words']:
        indices[word].append(doc['id'])

print indices

def word_count(words):
    count = defaultdict(int)
    for word in words:
        count[word] += 1
    return count

print word_count(['hiiragi', 'kagami', 'hiiragi', 'tukasa', 'yosimizu', 'kagami'])
    完满解决了之前遇到的那些破事.

    此外 collections 里还有个 Counter, 可以粗略认为它是 defaultdict(int) 的扩展.
]]>
简易配置 gunicorn http://blog.bitfoc.us/?p=516 http://blog.bitfoc.us/?p=516 Oct 30 2013 - 07:29:13 +0000 引子    单纯 gevent 跟 nodejs 一样有个问题是如果服务器有大的同步计算 (比如压缩一张图片什么的) 需求时, 服务器会很卡. 这也不能怪它们, 因为本来它们的长处是 IO 异步化, 同步计算卡住是缺陷特性之一.
    然, 或荐基独搅受 gunicorn 以解此困. 只是其首页上例子意味不明, 各种文档文章都说要编写一些离奇复杂的配置文件, 然后跑个语焉不详的 hello world, 并没能明示重点问题.

正文

    嘛, 一番探索之后配了下面一个用例 (Flask)
import time
import flask

app = flask.Flask(__name__)

@app.route('/<int:n>')
def root(n):
    time.sleep(2)
    i = n / 2
    while 1 < i:
        if n % i == 0:
            return 'not prime'
        i -= 1
    return 'prime'

if __name__ == '__main__':
    app.run(port=8000)
    这个例子里面兼顾了长 IO (用睡眠去模拟) 跟大计算 (算请求的数是不是个素数). 把这货在控制台裸着启动起来, 然后用 apache benchmark 来一发 (如果觉得后面请求参数里那个素数不够大, 可以自行算一个大的替换)
ab -n 500 -c 50 localhost:8000/16785407
    当然了, -c 50 这个参数纯是卖萌的, 因为上面这代码自身根本异步不起来. 结果自然是惨不忍睹, 重点两行在测试机上表现如下
Time per request:       131417.472 [ms] (mean)
Time per request:       2628.349 [ms] (mean, across all concurrent requests)
    平均单个请求耗时 2.6 秒以上, 其中 2 秒是睡过去的, 剩下 0.6 秒是计算. 也就是说 IO 时间与计算时间大概的比例是 3:1.

    安装 gunicorn 可以直接通过 pip 安装, 简单容易, 就不废话了. 下面上 gunicorn 平装版, 把上面的文件保存为 test.py, 在控制台中执行
gunicorn -w 4 test:app
    这个是说, 开 4 个进程跑 test 模块下的 app (就是文件里全局定义的 app 变量啦). 现在再开 ab 来一炮 (参数完全相同), 结果是
Time per request:       33150.026 [ms] (mean)
Time per request:       663.001 [ms] (mean, across all concurrent requests)
    从结果上来看差不多就是裸跑的 1/4 了, 因为开了 4 个进程一起搅嘛.

    虽然有 4 个进程睡睡醒醒轮番搞, 但没有异步 IO 的支持, 进程睡着就不干事了. 作为要榨干 worker 进程以及 CPU 使用率的系统管理员来说这可不能忍, 于是继续折腾个 gevent 进去好了, 两者互补, 相得益彰.
    不过用 gunicorn 就不需要在文件最开始打猴子补丁了, gunicorn 有个参数直接让 gevent 嵌入进程
gunicorn -w 4 -k gevent test:app
    再来一发 ab, 结果是
Time per request:       9724.214 [ms] (mean)
Time per request:       194.484 [ms] (mean, across all concurrent requests)
    嘛, 算是还看得过去的数据了.

补充说明

绑定其它端口

gunicorn -b 0.0.0.0:8000 -w 4 -k gevent test:app

我没有定义在全局的 app / 我的 app 需要特殊的初始化方式

    假如在文件里以一个特别的函数初始化 app, 比如
def init_app(arg0, arg1):
    # ...
    return app
    可以如此法启动
gunicorn -b 0.0.0.0:8000 -w 4 -k gevent 'test:init_app("value0", "value1")'
    看起来有点类似与传命令行参数.

    感谢双木成林对这篇文章的指导与建议.
]]>
记一些 (没) 有意义的 reduce 用法 http://blog.bitfoc.us/?p=515 http://blog.bitfoc.us/?p=515 Sep 30 2013 - 03:26:41 +0000 reduce 函数. 其中 Python 中 reduce 作为全局函数出现, 而 Javascript 中则是 Array 的成员函数. 大量的用 reduce 来做累加累乘之类的例子就不说了, 这里探讨一个特殊的用例.
    前端经常会需要将页面中用户填写的一些内容打包成 JSON 字典, 比如一个注册页面片段
<div>
    <input id='email' placeholder='Email'>
    <input id='password' placeholder='Password'>
    <input id='conform_password' placeholder='Confirm Password'>
    <input id='address' placeholder='Address'>
    <input id='phonenum' placeholder='Phone Number'>
    <button id='subm'>Submit</button>
</div>

<script>
document.getElementById('subm').onclick = function() {
    var inputValues = {
        email: document.getElementById('email').value,
        password: document.getElementById('password').value,
        address: document.getElementById('address').value,
        phonenum: document.getElementById('phonenum').value
    };
    /* process inputValues */
};
</script>
    以后每次这个表单多一项时, 构造 inputValues 时就会多一项, 代码维护会很烦.
    如果能这样写的话可能会好一些
var inputValues = {k: document.getElementById(k).value
                   for k in ['email', 'password', 'address', 'phonenum']};
    可惜 Javascript 里面没有温暖人心的 dict comprehension... 于是, 就有了下面这种 reduce 替代品 (终于正题了)
var inputValues = ['email', 'password', 'address', 'phonenum'].reduce(
    function(obj, item) {
        obj[item] = document.getElementById(item).value;
        return obj;
    }, {}));
    看来 Python 在语法灵活度上的优势已经虐掉 filter, map 函数两条街, 而且 dict comprehension 还能顺带打压一下 reduce, 也难怪 Guido 会挑明了说他不喜欢这些函数. 不过他不喜欢 reduce 主要是这东西太灵活, 一眼看不明白 (能一眼看明白的都直接用 sum 去了). 比如上面这个用例如果没有铺垫, 要理解还得废点草稿纸 (用来提升 bignity 倒是不错). 而下面这个例子也是 (Python)
some_dict = {
    'x': {
        'y': {
            'a': 10
        },
        'z': {
            'b': 20
        },
    },
}
reduce(lambda obj, key: obj.get(key, dict()), ['x', 'y', 'a'], some_dict)
    嘛, 是否允许在项目里面使用类似的机巧代码, 也许是比「哪个语言好」更值得每月探 (zheng) 讨 (chao) 的问题; 或是指定一些固定用法作为范式, 像背乘法口诀表一样背下来也许也不错的说.
]]>
Flask / MongoDB 搭建简易图片服务器 http://blog.bitfoc.us/?p=514 http://blog.bitfoc.us/?p=514 Sep 07 2013 - 04:10:57 +0000 前期准备通过 pip 或 easy_install 安装了 pymongo 之后, 就能通过 Python 调教 mongodb 了.
接着安装个 flask 用来当 web 服务器.
当然 mongo 也是得安装的. 对于 Ubuntu 用户, 特别是使用 Server 12.04 的同学, 安装最新版要略费些周折, 具体说是

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 7F0CEB10
echo 'deb http://downloads-distro.mongodb.org/repo/ubuntu-upstart dist 10gen' | sudo tee /etc/apt/sources.list.d/mongodb.list
sudo apt-get update
sudo apt-get install mongodb-10gen

如果你跟我一样觉得让通过上传文件名的后缀判别用户上传的什么文件完全是捏着山药当小黄瓜一样欺骗自己, 那么最好还准备个 Pillow 库

pip install Pillow

或 (更适合 Windows 用户)

easy_install Pillow

正片

Flask 文件上传

    Flask 官网上那个例子居然分了两截让人无从吐槽. 这里先弄个最简单的, 无论什么文件都先弄上来
import flask

app = flask.Flask(__name__)
app.debug = True

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    print f.read()
    return flask.redirect('/')

@app.route('/')
def index():
    return '''
    <!doctype html>
    <html>
    <body>
    <form action='/upload' method='post' enctype='multipart/form-data'>
         <input type='file' name='uploaded_file'>
         <input type='submit' value='Upload'>
    </form>
    '''

if __name__ == '__main__':
    app.run(port=7777)
  • 注: 在 upload 函数中, 使用 flask.request.files[KEY] 获取上传文件对象, KEY 为页面 form 中 input 的 name 值
    因为是在后台输出内容, 所以测试最好拿纯文本文件来测.

保存到 mongodb

    如果不那么讲究的话, 最快速基本的存储方案里只需要
import pymongo
import bson.binary
from cStringIO import StringIO

app = flask.Flask(__name__)
app.debug = True
db = pymongo.MongoClient('localhost', 27017).test

def save_file(f):
    content = StringIO(f.read())
    db.files.save(dict(
        content=bson.binary.Binary(content.getvalue()),
    ))

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    save_file(f)
    return flask.redirect('/')
    把内容塞进一个 bson.binary.Binary 对象, 再把它扔进 mongodb 就可以了.
    现在试试再上传个什么文件, 在 mongo shell 中通过

db.files.find()

    就能看到了. 不过 content 这个域几乎肉眼无法分辨出什么东西, 即使是纯文本文件, mongo 也会显示为 Base64 编码.

提供文件访问

    给定存进数据库的文件的 ID (作为 URI 的一部分), 返回给浏览器其文件内容, 如下
def save_file(f):
    content = StringIO(f.read())
    c = dict(content=bson.binary.Binary(content.getvalue()))
    db.files.save(c)
    return c['_id']

@app.route('/f/<fid>')
def serve_file(fid):
    f = db.files.find_one(bson.objectid.ObjectId(fid))
    return f['content']

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    fid = save_file(f)
    return flask.redirect('/f/' + str(fid))
    上传文件之后, upload 函数会跳转到对应的文件浏览页. 这样一来, 文本文件内容就可以正常预览了, 如果不是那么挑剔换行符跟连续空格都被浏览器吃掉的话.

当找不到文件时

    有两种情况, 其一, 数据库 ID 格式就不对, 这时 pymongo 会抛异常 bson.errors.InvalidId; 其二, 找不到对象 (!), 这时 pymongo 会返回 None.
    简单起见就这样处理了
@app.route('/f/<fid>')
def serve_file(fid):
    import bson.errors
    try:
        f = db.files.find_one(bson.objectid.ObjectId(fid))
        if f is None:
            raise bson.errors.InvalidId()
        return f['content']
    except bson.errors.InvalidId:
        flask.abort(404)

正确的 MIME

    从现在开始要对上传的文件严格把关了, 文本文件, 狗与剪刀等皆不能上传.
    判断图片文件之前说了我们动真格用 Pillow
from PIL import Image

allow_formats = set(['jpeg', 'png', 'gif'])

def save_file(f):
    content = StringIO(f.read())
    try:
        mime = Image.open(content).format.lower()
        if mime not in allow_formats:
            raise IOError()
    except IOError:
        flask.abort(400)
    c = dict(content=bson.binary.Binary(content.getvalue()))
    db.files.save(c)
    return c['_id']
    然后试试上传文本文件肯定虚, 传图片文件才能正常进行. 不对, 也不正常, 因为传完跳转之后, 服务器并没有给出正确的 mimetype, 所以仍然以预览文本的方式预览了一坨二进制乱码.
    要解决这个问题, 得把 MIME 一并存到数据库里面去; 并且, 在给出文件时也正确地传输 mimetype
def save_file(f):
    content = StringIO(f.read())
    try:
        mime = Image.open(content).format.lower()
        if mime not in allow_formats:
            raise IOError()
    except IOError:
        flask.abort(400)
    c = dict(content=bson.binary.Binary(content.getvalue()), mime=mime)
    db.files.save(c)
    return c['_id']

@app.route('/f/<fid>')
def serve_file(fid):
    try:
        f = db.files.find_one(bson.objectid.ObjectId(fid))
        if f is None:
            raise bson.errors.InvalidId()
        return flask.Response(f['content'], mimetype='image/' + f['mime'])
    except bson.errors.InvalidId:
        flask.abort(404)
    当然这样的话原来存进去的东西可没有 mime 这个属性, 所以最好先去 mongo shell 用 db.files.drop() 清掉原来的数据.

根据上传时间给出 NOT MODIFIED

    利用 HTTP 304 NOT MODIFIED 可以尽可能压榨与利用浏览器缓存和节省带宽. 这需要三个操作
  • 记录文件最后上传的时间
  • 当浏览器请求这个文件时, 向请求头里塞一个时间戳字符串
  • 当浏览器请求文件时, 从请求头中尝试获取这个时间戳, 如果与文件的时间戳一致, 就直接 304
    体现为代码是
import datetime

def save_file(f):
    content = StringIO(f.read())
    try:
        mime = Image.open(content).format.lower()
        if mime not in allow_formats:
            raise IOError()
    except IOError:
        flask.abort(400)
    c = dict(
        content=bson.binary.Binary(content.getvalue()),
        mime=mime,
        time=datetime.datetime.utcnow(),
    )
    db.files.save(c)
    return c['_id']

@app.route('/f/<fid>')
def serve_file(fid):
    try:
        f = db.files.find_one(bson.objectid.ObjectId(fid))
        if f is None:
            raise bson.errors.InvalidId()
        if flask.request.headers.get('If-Modified-Since') == f['time'].ctime():
            return flask.Response(status=304)
        resp = flask.Response(f['content'], mimetype='image/' + f['mime'])
        resp.headers['Last-Modified'] = f['time'].ctime()
        return resp
    except bson.errors.InvalidId:
        flask.abort(404)
    然后, 得弄个脚本把数据库里面已经有的图片给加上时间戳.
    顺带吐个槽, 其实 NoSQL DB 在这种环境下根本体现不出任何优势, 用起来跟 RDB 几乎没两样.

利用 SHA-1 排重

    与冰箱里的可乐不同, 大部分情况下你肯定不希望数据库里面出现一大波完全一样的图片. 图片, 连同其 EXIFF 之类的数据信息, 在数据库中应该是惟一的, 这时使用略强一点的散列技术来检测是再合适不过了.
    达到这个目的最简单的就是建立一个 SHA-1 惟一索引, 这样数据库就会阻止相同的东西被放进去.
    在 MongoDB 中表中建立惟一索引, 执行 (Mongo 控制台中)

db.files.ensureIndex({sha1: 1}, {unique: true})

    如果你的库中有多条记录的话, MongoDB 会给报个错. 这看起来很和谐无害的索引操作被告知数据库中有重复的取值 null (实际上目前数据库里已有的条目根本没有这个属性). 与一般的 RDB 不同的是, MongoDB 规定 null, 或不存在的属性值也是一种相同的属性值, 所以这些幽灵属性会导致惟一索引无法建立.
    解决方案有三个
  • 删掉现在所有的数据 (一定是测试数据库才用这种不负责任的方式吧!)
  • 建立一个 sparse 索引, 这个索引不要求幽灵属性惟一, 不过出现多个 null 值还是会判定重复 (不管现有数据的话可以这么搞)
  • 写个脚本跑一次数据库, 把所有已经存入的数据翻出来, 重新计算 SHA-1, 再存进去
    具体做法随意. 假定现在这个问题已经搞定了, 索引也弄好了, 那么剩是 Python 代码的事情了.
import hashlib

def save_file(f):
    content = StringIO(f.read())
    try:
        mime = Image.open(content).format.lower()
        if mime not in allow_formats:
            raise IOError()
    except IOError:
        flask.abort(400)

    sha1 = hashlib.sha1(content.getvalue()).hexdigest()
    c = dict(
        content=bson.binary.Binary(content.getvalue()),
        mime=mime,
        time=datetime.datetime.utcnow(),
        sha1=sha1,
    )
    try:
        db.files.save(c)
    except pymongo.errors.DuplicateKeyError:
        pass
    return c['_id']
    在上传文件这一环就没问题了. 不过, 按照上面这个逻辑, 如果上传了一个已经存在的文件, 返回 c['_id'] 将会是一个不存在的数据 ID. 修正这个问题, 最好是返回 sha1, 另外, 在访问文件时, 相应地修改为用文件 SHA-1 访问, 而不是用 ID.
    最后修改的结果及本篇完整源代码如下
import hashlib
import datetime
import flask
import pymongo
import bson.binary
import bson.objectid
import bson.errors
from cStringIO import StringIO
from PIL import Image

app = flask.Flask(__name__)
app.debug = True
db = pymongo.MongoClient('localhost', 27017).test
allow_formats = set(['jpeg', 'png', 'gif'])

def save_file(f):
    content = StringIO(f.read())
    try:
        mime = Image.open(content).format.lower()
        if mime not in allow_formats:
            raise IOError()
    except IOError:
        flask.abort(400)

    sha1 = hashlib.sha1(content.getvalue()).hexdigest()
    c = dict(
        content=bson.binary.Binary(content.getvalue()),
        mime=mime,
        time=datetime.datetime.utcnow(),
        sha1=sha1,
    )
    try:
        db.files.save(c)
    except pymongo.errors.DuplicateKeyError:
        pass
    return sha1

@app.route('/f/<sha1>')
def serve_file(sha1):
    try:
        f = db.files.find_one({'sha1': sha1})
        if f is None:
            raise bson.errors.InvalidId()
        if flask.request.headers.get('If-Modified-Since') == f['time'].ctime():
            return flask.Response(status=304)
        resp = flask.Response(f['content'], mimetype='image/' + f['mime'])
        resp.headers['Last-Modified'] = f['time'].ctime()
        return resp
    except bson.errors.InvalidId:
        flask.abort(404)

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    sha1 = save_file(f)
    return flask.redirect('/f/' + str(sha1))

@app.route('/')
def index():
    return '''
    <!doctype html>
    <html>
    <body>
    <form action='/upload' method='post' enctype='multipart/form-data'>
         <input type='file' name='uploaded_file'>
         <input type='submit' value='Upload'>
    </form>
    '''

if __name__ == '__main__':
    app.run(port=7777)
]]>
PLY 构造词法分析工具 http://blog.bitfoc.us/?p=513 http://blog.bitfoc.us/?p=513 Aug 03 2013 - 11:18:01 +0000 PLY 需要安装一份. 可以直接通过 pip 安装

# pip install ply

    这东西并非一个扩展的正则表达式工具, 而是一个完备的编译器构造工具, 不过这篇文章只打算讨论其词法分析器构造部分.

基本例子

    PLY 很魔法的一点是它使用到了模块内部反射. 也就是说在产生一个词法分析器时, 并不是把词法规则传递给 PLY 的接口, 而是依次将一些指定名字的变量或函数定义在 py 文件中.
    下面给出第一个例子, 从文本中抓出十进制数值.
import ply.lex

tokens = (
    'NUMBER',
)

t_NUMBER = r'\d*[.]?\d+'

def t_error(t):
    t.lexer.skip(1)

ply.lex.lex()
ply.lex.input('''
    The Chinese mathematician Zu Chongzhi, around 480 AD, calculated that
        pi ~= 355/113
    (a fraction that goes by the name Milv in Chinese), using Liu Hui's
    algorithm applied to a 12288-sided polygon. With a correct value for its
    seven first decimal digits, this value of 3.141592920... remained the most
    accurate approximation of pi available for the next 800 years.

    <From Wikipedia:Pi>
''')

for token in iter(ply.lex.token, None):
    print token.type, token.value
    输出

NUMBER 480
NUMBER 355
NUMBER 113
NUMBER 12288
NUMBER 3.141592920
NUMBER 800

    上面的代码有这么一些要点
  • 文件中定义了 tokens 表示可能的词元类型; 在官方例子中, 其中的取值通常以全大写的形式出现
  • 定义词元规则 t_NUMBER, 其名字是 token 变量中的成员 'NUMBER' 加上前缀 t_; 在构造词法分析器时, PLY 会将以 t_ 开头的所有定义收集起来
  • 词元规则 t_NUMBER 的取值是正则表达式, 用来匹配所有的数值
  • 定义 t_error 函数, 如果什么奇怪的东西混进来, 这个函数会被调用; 不过现在只是抓取数值, 无视其它符号, 所以实现只是跳过一个字符 (skip 的参数是字符数量)
  • 调用 ply.lex.lex 构造词法分析器
  • 调用 ply.lex.input 喂一些输入进去
  • ply.lex.token 获得词法分析的结果

利用分词输出

    从这个基本例子迈向一个用于简单表达式计算的词法分析器并不困难. 如果按照之前一篇文章里所演示的那个功能 (请将该文章中最后一段代码保存在 expr_eval.py 中以供这次使用), 需要至少以下这些词元类型
  • 二元算符 */^
  • 二元或一元算符 +-
  • 括号
  • 整数
    以及, 尽量地, 应该忽略空格换行等字符. 这个在 PLY 中可以通过定义 t_ignore 来实现.
    并且, 这次不是将结果打印出来完事, 而是要构造一个能用的词元序列. 因此需要一个将 PLY 词元转换为在 expr_eval.py 中定义的 Token 类实例的函数. Token 对象构造时, 除了词元字符串值参数外, 还需要两个值表示是否为数值以及是否可能是前置一元运算符, 这两个参数都可以根据词元类型获取.
    下面是对应的代码
import ply.lex
import expr_eval

tokens = (
    'BINARY_OP', 'UNARY_OR_BINARY_OP', 'OPEN_PAREN', 'CLOSE_PAREN', 'INTEGER',
)

t_BINARY_OP = r'[*/^]'
t_UNARY_OR_BINARY_OP = r'-|\+'
t_INTEGER = r'\d+'
t_OPEN_PAREN = r'('
t_CLOSE_PAREN = r')'
t_ignore = ' '

def t_error(t):
    raise ValueError('invalid character: ' + t.value[0])

def create_token(token):
    if token.type in ['OPEN_PAREN', 'CLOSE_PAREN', 'BINARY_OP']:
        return expr_eval.Token(token.value, False, False)
    if token.type in ['UNARY_OR_BINARY_OP']:
        return expr_eval.Token(token.value, False, True)
    return expr_eval.Token(token.value, True, False)

ply.lex.lex()
if __name__ == '__main__':
    ply.lex.input('''-(6 * 5) + (4 ^ 3) ^ 2 - 1''')
    expr = expr_eval.buildExpression([
        create_token(token) for token in iter(ply.lex.token, None)
    ])
    print expr.evaluate()
    print -(6 * 5) + (4 ** 3) ** 2 - 1
需要注意的是, t_ignore 取值并不是一个正则表达式 (并非 r'[ ]+'); 这是个坑, 如果不慎写成了这种形式, 输入字符串中所有的加号也会被忽略

在获取词元时转换

    create_token 的实现显得非常直截了当, 但并不很优雅. 而实际上 PLY 提供其它的机制令开发者绕开这种笨拙的映射, 这一机制的实现是将词元规则定义为函数而不是一个字符串. 比如
def t_UNARY_OR_BINARY_OP(token):
    r'-|\+'
    token.value = expr_eval.Token(token.value, False, True)
    return token
    匹配词元的正则表达式成为了这个函数的文档字符串; 而在这个函数中, 传入参数的 tokenvalue 属性被修改为了期望的词元对象, 因此, 在 create_token 中, 对应类型的词元不需再次转换了
def create_token(token):
    if token.type in ['OPEN_PAREN', 'CLOSE_PAREN', 'BINARY_OP']:
        return expr_eval.Token(token.value, False, False)
    if token.type in ['UNARY_OR_BINARY_OP']:
        return token.value
    return expr_eval.Token(token.value, True, False)
    当然, 如果所有的词元类型都这么处理了, create_token 这个赘余就不再需要了, 也就是说代码被修改成这样
import ply.lex
import expr_eval

tokens = (
    'BINARY_OP', 'UNARY_OR_BINARY_OP', 'OPEN_PAREN', 'CLOSE_PAREN', 'INTEGER',
)

def t_BINARY_OP(token):
    r'[*/^]'
    token.value = expr_eval.Token(token.value, False, False)
    return token

def t_UNARY_OR_BINARY_OP(token):
    r'-|\+'
    token.value = expr_eval.Token(token.value, False, True)
    return token

def t_INTEGER(token):
    r'\d+'
    token.value = expr_eval.Token(token.value, True, False)
    return token

def t_OPEN_PAREN(token):
    r'('
    token.value = expr_eval.Token(token.value, False, False)
    return token

def t_CLOSE_PAREN(token):
    r')'
    token.value = expr_eval.Token(token.value, False, False)
    return token

t_ignore = ' '

def t_error(t):
    raise ValueError('invalid character: ' + t.value[0])

ply.lex.lex()
if __name__ == '__main__':
    ply.lex.input('''-(6 * 5) + (4 ^ 3) ^ 2 - 1''')
    expr = expr_eval.buildExpression([
        token.value for token in iter(ply.lex.token, None)
    ])
    print expr.evaluate()
    print -(6 * 5) + (4 ** 3) ** 2 - 1
    冗余代码仍旧很多, 有兴趣可以考虑试试装饰器.
]]>
越俎代庖 - 文件系统权限设置与进程的用户身份 http://blog.bitfoc.us/?p=512 http://blog.bitfoc.us/?p=512 May 11 2013 - 15:49:33 +0000 sudo 执行需要 root 权限的程序时, 输入的是当前用户的口令而不是 root 的?

    看一下 sudo 的 manpage, 描述是 "execute a command as another user". 注意并不一定是以 root 身份跑程序, 而是可以用任何其他身份. 这做好事不留名干坏事不怕差评利器真是太方便了. 比如, 偷偷输出某个用户的 SSH RSA 私钥之类的. 在桌面机上很少有人会建多个用户, 那么现在创建一个 (建议接下来的试验都新建用户进行, 避免遗留安全隐患; 另外, 当前用户必须已经被添加到 sudo 白名单中)
sudo useradd -m furude
sudo passwd furude # 这一步最好设置一个与当前用户不同的口令
su - furude
furude $
    这样切换到试验用户身份, 然后创建 ssh key, 并确认生成的密钥
ssh-keygen
Generating public/private rsa key pair.

Enter file in which to save the key (/home/furude/.ssh/id_rsa): Created directory '/home/furude/.ssh'.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/furude/.ssh/id_rsa.
Your public key has been saved in /home/furude/.ssh/id_rsa.pub.
The key fingerprint is:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The keys randomart image is:
+--[ RSA 2048]----+
| ............... |
+-----------------+
ls .ssh
id_rsa id_rsa.pub
    现在另开一个 shell, 以非 furude 身份登入, 执行
ls /home/furude/.ssh
会看到错误, 不允许列举该目录. 这是当然了, 要是连密钥都能随便看, 就没什么安全感了.

    下面就轮到 sudo 登场了. 还是当前用户身份登入, 执行
sudo ls /home/furude/.ssh
id_rsa id_rsa.pub
sudo -u furude ls /home/furude/.ssh
id_rsa id_rsa.pub
sudo -u `whoami` ls /home/furude/.ssh
ls: cannot open directory /home/furude/.ssh/: Permission denied
    第一个是以 root 身份执行, root 最大嘛, 所以当然可以毫无压力偷看一切文件或目录了; 接下来 -u furude 参数则是指定以 furude 这个用户身份执行, 自己当然可以看自己的东西了; 最后一个则仍然是以当前用户身份执行, 所以被驳回了.
    在上面试验中, 即使以 furude 的身份使用 sudo, 要求输入的口令仍然是当前用户的口令而不是 furude 用户的 (最好新开一个终端试试, 连续使用 sudo 时口令会被缓存下来). 那么, 开头的问题应该是这样的
  • 为何用 sudo 临时以另一用户身份执行程序时, 要求输入的是当前用户的口令, 而不是被指定的那个用户?
    这个问题的答案不在 sudo 的源代码中, 而在于文件系统对文件权限设置的一个不常见设置. 一般在谈到文件权限设置时, 都会说到如 751 或者 644 这样的选项, 对应的权限分别是 rwxr-x--xrw-r--r--, 详细的含义和构成这里就不讲了, 很多地方都有参考. 下面看看 sudo
ls -l `which sudo`
-rwsr-xr-x 2 root root /usr/bin/sudo*
    第一部分用户权限这里写的不是 `rwx` 而是 `rws`, 这个就略猎奇了. 在文件系统中, 用户权限中的可执行位 x 如果被标记为 s (含义是 "用户设置"), 则这个程序在启动时, 无论由谁启动, 将该进程对应的用户设置为该可执行文件的所有者.
    比如, 下面再来做个试验, 创建下面的 C 源代码文件 print_private_key.c
/* print_private_key.c */

#include <stdio.h>

int main(void)
{
    FILE* f = fopen("/home/furude/.ssh/id_rsa", "r");
    if (NULL == f) {
        fprintf(stderr, "Unable to open the file\n");
        return 1;
    }
    char buffer[81];
    while(fgets(buffer, 80, f) != NULL) {
        printf("%s", buffer);
    }
    return 0;
}
并以 furude 用户身份编译之
gcc print_private_key.c -o p.out
然后运行它.
    以 furude 的身份的话, 当然运行这个程序是没问题的. 但是, 如果以一般其它用户运行, 在打开文件那一步就会出错, 输出 "Unable to open the file" 然后灰溜溜地退出. 这一点当然毫不令人惊讶. 下面在编译生成的可执行程序上施加一点魔法 (以文件所有者 furude 的身份)
chmod 4751 p.out
    这个取值 4xxx 显得有点高调, 最前面那个 4 就表示对 "用户设置" 位置位. 现在看看 p.out, 它的权限是 -rwsr-x--x. 这时再随便找个用户运行 p.out (不会提示输入 furude 的口令) 都能看到 furude 用户的密钥.
    因此这是一件非常非常危险的事情!

    那么之前那个问题一般到此解答了, 为什么运行 sudo 不用输入假身份的口令, 但还没解决的是为何要输入真身的口令.
    实际上, 任何普通用户在都能执行 sudo, 启动 sudo 进程后, 其身份已然是 root 用户, root 想看谁想删谁想引爆电脑都可以. 只是在这之前, 要核实一下当前用户是否在白名单里, 并且要求用户输入一次口令. 这个检查的操作要借助一个系统调用 getuid 来完成; 而说到这个 API 又不得不说另一个与之类似的 geteuid (这俩好基友在 manpage 里面都是占一个坑的). 保存下面的源代码
#include <stdio.h>
#include <stdlib.h>
#include <pwd.h>

int main(void)
{
    uid_t uid = geteuid();
    struct passwd* pw = getpwuid(uid);
    printf("Efficient user: %s\n", pw->pw_name);

    uid = getuid();
    pw = getpwuid(uid);
    printf("Real user: %s\n", pw->pw_name);

    return 0;
}
    然后编译之, 并将生成的可执行文件按照之前一样的方式置上 "用户设置" 位. 以任何用户身份执行这个程序, 有效用户都是 furude, 而真实用户则显示了实际执行程序的用户. 这也就是为何 sudo 能判断出到底是谁在执行, 该输入谁的口令的方法.
]]>
ASCII Art 字体 Tukasans http://blog.bitfoc.us/?p=511 http://blog.bitfoc.us/?p=511 May 11 2013 - 15:38:41 +0000 _________ _________ _________  _______
|       | |   |   | |   |   | /       \
|_     _| |   |   | |      /  |       |
  |   |   |       | |      \  |   -   |
  |   |   |       | |       | |   _   |
  |___|   |_______| |___|___| |__| |__|
 ________  _______  ____ ____  ________
|       | /       \ |   \|  | |       |
|    ---| |       | |    |  | |    ---|
|       | |   -   | |       | |       |
|---    | |   _   | |  |    | |---    |
|_______| |__| |__| |__|\___| |_______|

=============================================================================
 _______        _______  _________ _________  ________ _________
/       \      /       \ |   |   | |_     _| /       | |   |   |
|       |      |       | |   |   |   |   |   |       | |      /
|   -   |      |   +   | |       |   |   |   |     --  |      \
|   _   |      |       \ |       |  _|   |_  |       | |       |
|__| |__|      \_____\_/ |_______| |_______| \_______| |___|___|
________  ________   _______  _________ ____ ____
|       \ |       \ /       \ |  |  | | |   \|  |
|  --   | |   -   | |       | |  |  | | |    |  |
|      -  |       / |   O   | |       | |       |
|  --   | |   _   \ |       | |       | |  |    |
|_______/ |__| \__| \_______/ |_______| |__|\___|
_________  _______  ____ ____
|       | /       \ |   |   |
|     --| |       | |       |
|       | |   O   |  -     -
|     --  |       | |       |
|_____|   \_______/ |___|___|
  _______ _________ _________ ________   ________
  |     | |   |   | |       | |       | |       |
  |     | |   |   | |       | |   -   | |    ---|
 _/     | |       | |       | |      _| |       |
|       | |       | |  |  | | |     |   |---    |
|_______/ |_______| |__|__|_| |_____|   |_______|
 _______  _________ _________ ________       _________ ___   ___ _________
/       \ |   |   | |       | |       \      |       | |  |_|  | |       |
|       | |   |   | |     --| |   -   |      |_     _| |       | |     --|
|   O   | |       | |       | |       /        |   |   |       | |       |
|       |  \     /  |     --| |   _   \        |   |   |   _   | |     --|
\_______/   \___/   |_______| |__| \__|        |___|   |__| |__| |_______|
_______    _______  _________ ____ ____      ________   _______   ________
|     |   /       \ |       | |   |   |      |       \ /       \ |       |
|     |   |       | |---    | |       |      |       | |       | |   ____|
|     |_  |   -   | |       |  \     /       |   D   | |   O   | |  |    |
|       | |   _   | |    ---|   |   |        |       | |       | |   --  |
|_______| |__| |__| |_______|   |___|        |_______/ \_______/ |_______|

=============================================================================
 _______   ________  _______   ________ ____ ____
/       \ /       | /       \ /       | |  | |  |
|       | |_      | |_      | |--     | |  |_|  |
|   0   |   |     |  /     /  |       | |       |
|       |   |     | |     /__ |--     | |_____  |
\_______/   |_____| |_______| \_______|      |__|
________   ________ _________  _______  ________
|       | /       | |       | /       \ |       \
|     --  |    ---| |___    | |   O   | |   O   |
|       \ |       |    |    | |       | |       |
|--     | |   O   |    |    | |   O   | |---    |
|_______/ \_______|    |____| \_______/ |_______/

FAQ

这有何用?

卖萌.

可以怎么用?

与任何 Bit Focus Blog 中内容一样, CC 3.0 署名.

符号呢

完整版.

这字体分不清数字零与字母欧, 简直弱爆了

Tukasans 中数字零的中间是个数字零, 字母欧中间是个字母欧. 分不清是字体设置的问题.
]]>
多国语言环境下 Jinja2 与 strftime 互动异常退治纪要 http://blog.bitfoc.us/?p=510 http://blog.bitfoc.us/?p=510 Apr 13 2013 - 09:21:26 +0000 字符串类型设置不对而直接抛运行期异常.
    常在河边走, 湿鞋是顺理成章的事情. 这次遇到的情况简报如下
# encoding=utf-8

import jinja2
import datetime

now = datetime.datetime.utcnow()

print jinja2.Template(u'''当前月份 {{ date.strftime('%Y 年 %m 月') }}''').render(date=now)
运行这一段代码, Python 直接扔出来一坨
Traceback (most recent call last):
  File "test.py", line 8, in <module>
    print jinja2.Template(u'''当前月份 {{ date.strftime('%Y 年 %m 月') }}''').render(date=now)
  File "/usr/local/lib/python2.7/dist-packages/Jinja2-2.6-py2.7.egg/jinja2/environment.py", line 894, in render
    return self.environment.handle_exception(exc_info, True)
  File "<template>", line 1, in top-level template code
UnicodeEncodeError: 'ascii' codec can't encode character u'\u5e74' in position 3: ordinal not in range(128)
    简单地说, 就是 Jinja2 在刷什么东西的过程中挂了, 因为字符串里面混入了什么奇怪的东西.

    一番尝试并寻找之后, 首先发现第一个问题, datetime.datetime.strftime 函数接受奇怪的字符串会出问题, 比如先来试试看这个
now = datetime.datetime.utcnow()
print now.strftime('%Y 年 %m 月')
    结果什么问题都没有, 突然有人品爆了的感觉, 这个好像很不科学的样子啊. 再仔细对比代码找找茬才发现要这样才能挂掉程序
now = datetime.datetime.utcnow()
print now.strftime(u'%Y 年 %m 月')
    这前缀 uunicode 类型怎么说也坑太深了的感觉吧. (别扯什么 Python strunicode 类型异与同 21 天从入门到精通什么的, 别的语言都没这问题 Python 确有, 这应该就是 Python 的问题了吧.) 在这种情况下如果要用 unicode 还得转一道
now = datetime.datetime.utcnow()
print now.strftime(u'%Y 年 %m 月'.encode('utf-8'))
    之所以有这个搞法是因为可能拿到的格式化字符串是 unicode 类型, 所以加一下 encode.
    这看起来简直像是不明来历的野生 API, 连自家的 unicode 都不支持么. 可是注意 Jinja2 模板字符串里面那个格式化字符串并没有加任何前缀. 而貌似 Jinja2 也觉得 Python unicode 是个坑, 因此并不需要放字符串前缀, 相反放了还出错 (u'string' 会被认为是变量 u 与字符串 'string' 放一起中间没加二元运算符).

    搞了这么久问题还是没进展, 所以得采用其它方式更深入地调教一下. 那么, 把格式化函数外面套一层, 然后把套在外面的一层也搅进 Jinja2, 如下
# encoding=utf-8

import jinja2
import datetime

def strftime(dt, fmt):
    print '0'
    x = dt.strftime(fmt)
    print '1'
    return x

now = datetime.datetime.utcnow()

print jinja2.Template(u'''当前月份 {{ strftime(date, '%Y 年 %m 月') }}'''
                        ).render(date=now, strftime=strftime)
    简单诊断发现问题出在 x = dt.strftime(fmt) 这句. 好吧这 API 不知道适可而止一点么, 还是说喂过去的参数有什么问题? 那么看看从 Jinja2 传过来的东西到底是什么东西
def strftime(dt, fmt):
    print type(fmt)
    return dt.strftime(fmt)
    结果就被控制台上迎面一记 <type 'unicode'> 击倒. Jinja2 你这是要跟 strftime 合起来玩我啊. 好吧, 那只能这样了
def strftime(dt, fmt):
    print '0'
    x = dt.strftime(fmt.encode('utf-8'))
    print '1'
    return x
    好消息是这一来 0 跟 1 都打出来了, 而坏消息是, 还是挂. 这熊孩子模板库到底是要闹哪样啊!

    行了, 那一个一个地攻略, strftime 你先一边去
def strftime(dt, fmt):
    return '2013 年 4 月'
挂. 而
def strftime(dt, fmt):
    return u'2013 年 4 月'
正常.
    被抓到了尾巴了吧. Jinja2 不接受含有非 ASCII 的 str 而只能返回 unicode. 好吧, 那这么一来, 线索又回到 strftime 了, 这函数一定是得出了什么不对劲的东西. 可以如下做个简单试验
now = datetime.datetime.utcnow()
s = now.strftime('%Y 年 %m 月')
print type(s)
    结果竟然是 <type 'str'> 啊, 一瞬三观尽毁的感觉, 不带这么玩脱的吧. 行, 那么正确的打码方式是在返回的 str 上调用 decode 函数, 得到 unicode 再塞给 Jinja2. 完整代码如下
# encoding=utf-8

import jinja2
import datetime

def strftime(dt, fmt):
    return dt.strftime(fmt.encode('utf-8')).decode('utf-8')

now = datetime.datetime.utcnow()

print jinja2.Template(u'''当前月份 {{ strftime(date, '%Y 年 %m 月') }}'''
                        ).render(date=now, strftime=strftime)
    多谢 @kavinyao 同学给了一个更专业的解答: 弄一个 Jinja2 过滤器. 如下
# encoding=utf-8

import jinja2
import datetime

def strftime(dt, fmt):
    return dt.strftime(fmt.encode('utf-8')).decode('utf-8')

env = jinja2.Environment(loader=jinja2.DictLoader(
            dict(test=u'''当前月份 {{ date|strftime('%Y 年 %m 月') }}''')))
env.filters['strftime'] = strftime
t = env.get_template('test')
print t.render(date=datetime.datetime.utcnow())
]]>
Flask 出坑记 http://blog.bitfoc.us/?p=509 http://blog.bitfoc.us/?p=509 Apr 05 2013 - 02:49:05 +0000 Flask 是个 Python Web 框架. 网站上文档例子都很详尽, 这里就不废话了, 只是来扯两个使用中需要注意的地方.

获取 POST 请求体

    21 世纪的 Web 交互中服务器跟浏览器互相丢 JSON 已经成了司空见惯的事情. 在 Flask 框架作成的服务器上要搞到 JSON 数据当然是直接访问 POST 请求体了, 如
import flask
import functools

app = flask.Flask(__name__)

@app.route('/wtf', methods=['POST'])
def wtf():
    return 'Received: ' + flask.request.data

def main():
    app.run(port=7777)

if __name__ == '__main__': main()
    按文档的说法, flask.request.data 包含请求数据字符串. 但其实这也是个坑, 默认情况下根本取不到请求数据
curl -d "[1,1,2,3,5,8]" http://localhost:7777/wtf
Received:
    熊孩子你把拿到的字符串给吃了吧? 实际上如果去看看那文档会看到并不如上面所说的那样, 而是
  • Contains the incoming request data as string in case it came with a mimetype Flask does not handle.
    后面这个状语从句真是着急, 那到底什么 mimetype 会使得 Flask does not handle 呢? 根本没说清楚啊. 扫一眼文档后面, 还有个东西可以用: flask.request.json, 但这货一般是 None, 只有当请求 mimetype 被设置为 application/json 的时候才有用, Flask 你真心是跟 mimetype 过不去啊. 也就是说得这样发请求
curl -d "[1,1,2,3,5,8]" localhost:7777/wtf
Received: null
curl -d "[1,1,2,3,5,8]" -H "Content-Type:application/json" localhost:7777/wtf
Received: [1, 1, 2, 3, 5, 8]
# Server codes

import json
import flask
import functools

app = flask.Flask(__name__)

@app.route('/wtf', methods=['POST'])
def wtf():
    return 'Received: ' + json.dumps(flask.request.json)

def main():
    app.run(port=7777)

if __name__ == '__main__': main()
    问题是现在前端攻城狮都被浏览器兼容性折腾得满世界买表, 哪还有心情检查每个请求的 content-type 对不对. 况且这还只对 JSON 有效, 如果是山寨协议又怂了.
    好吧, 如果实在不行, 就挖到 WSGI 里面去好了, 比如这样
def request_data():
    d = flask.request.data
    if not d:
        return ''.join(flask.request.environ['wsgi.input'].readlines())
    return d
    这样 (在特定的 WSGI 环境中, 比如配合 gevent 使用时) 能获取请求数据 (这不还是坑么). 或者看看这个万能的方法. 好了, 请求字符串快到碗里来!

装饰器对被装饰函数的名字是敏感的 [已修正]

    Flask 更新到 0.10 之后以下问题已经修正. 现在定义同名的请求处理函数会直接报错, 程序退出.

    如官网上的例子
import flask
app = flask.Flask(__name__)

@app.route('/')
def hello():
    return 'Hello World'

if __name__ == '__main__': app.run(port=7777)
    这个装饰器挂在哪个函数上, 哪个函数就成为一个处理函数. 这个特性让那些看多了 django 或者 tornado 起手先一大堆类定义的人一下子全高潮了, 大呼简单函数拯救世界. 不过这东西有时候相当坑. 先来看一个熊孩子特性, 把上面代码改成这样
import flask
app = flask.Flask(__name__)

app.route('/')(lambda: 'Hello World')

if __name__ == '__main__': app.run(port=7777)
    然后试着 curl 一下 http://localhost:7777, 没问题, 还是返回 'Hello World'. 好, 加一句
import flask
app = flask.Flask(__name__)

app.route('/')(lambda: 'Hello World')
app.route('/wtf')(lambda: 'I bought a watch last year')

if __name__ == '__main__': app.run(port=7777)
    再来一发
curl http://localhost:7777/
I bought a watch last year
curl http://localhost:7777/wtf
I bought a watch last year
    怎么都是「I bought a watch last year」?! 我去年买了个表!
    查了一通文档才发现 Flask 会索引被装饰函数的名字, 并根据这些名字来派发请求. 好了, 结论是不要在 Flask 里玩 lambda, 因为 Python 里面所有 lambda 名字都一个样
>>> x = lambda : None
>>> x.__name__
'<lambda>'
>>> y = lambda m, n: m + n
>>> y.__name__
'<lambda>'
    傲娇程序员的第一反应可能是「才不会到处用 lambda 只是偶尔写一个换换口味」. 且慢, 倒不是说 lambda 有问题, 而是下面这种用况会出事
import flask

app = flask.Flask(__name__)

def handler_logger(f):
    def g(*args, **kwargs):
        print 'before request'
        r = f(*args, **kwargs)
        print 'after request'
        return r
    return g

@app.route('/')
@handler_logger
def root():
    return 'Hello World'

@app.route('/wtf')
@handler_logger
def wtf():
    return 'I bought a watch last year'

if __name__ == '__main__': app.run(port=7777)
    同样的结果, 访问两个 URL 看到的都是后一个函数的结果.
    刚才已经说了 Flask 对被包装函数的名字是敏感的, 所以解决上述问题的方法便是
import flask
import functools

app = flask.Flask(__name__)

def handler_logger(f):
    @functools.wraps(f)
    def g(*args, **kwargs):
        print 'before request'
        r = f(*args, **kwargs)
        print 'after request'
        return r
    return g

@app.route('/')
@handler_logger
def root():
    return 'Hello World'

@app.route('/wtf')
@handler_logger
def wtf():
    return 'I bought a watch last year'

def main():
    app.run(port=7777)

if __name__ == '__main__': main()
]]>