Python AST 编译原理 表达式

以下代码均可直接粘贴运行, 在Python3.7中测试通过

问题引入

先前遇到了一个排序问题, 具有不同属性的对象, 需要根据其中一些属性 进行排序, 比如对一系列的评论进行排序, 有评论者, 点赞数, 发布时间这些 特征, 这些特征可能所占的比重不同, 而后根据计算的结果进行排序.

假如有下面这样一些评论:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import datetime
topics = [
{
    "content": "这是评论1",  # 评论内容
    "likes": 10,        # 点赞数
    "user_weight": 10,  # 用户权重
    'time': datetime.datetime(2019, 2, 20, 19, 31, 58, 412000),  # 发布时间
},
{
    "content": "这是评论2",  # 评论内容
    "likes": 5,        # 点赞数
    "user_weight": 20,  # 用户权重
    'time': datetime.datetime(2019, 2, 20, 19, 41, 58, 412000),  # 发布时间
},
{
    "content": "这是评论1",  # 评论内容
    "likes": 20,        # 点赞数
    "user_weight": 5,  # 用户权重
    'time': datetime.datetime(2019, 2, 20, 20, 1, 58, 412000),  # 发布时间
}
]

打算使用这样的表达式计算权值:

用户权重 * 5 + 点赞数 * 1 + 发布距今秒数 * -0.02

用户权值占的比值较大, 用户权值越高, 越靠前; 发布越早的帖子的权值越低, 越靠后

初级的解决思路

我们会写一个for循环, 遍历这个数组, 进行计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import time
# 由于时间过去久远, time.time()实在太大了, 所以简单取一个值, 这里只是为了说明计算
cur_time = 1550664218.0

for topic in topics:
    topic['weight'] = 5 * topic['user_weight'] + topic['likes'] + \
        (cur_time - time.mktime(topic['time'].timetuple())) * -0.02

# topics 就会变成下面这样, 你可以对weight值进行排序了(文中不涉及排序).

[{'content': '这是评论1',
  'likes': 10,
  'user_weight': 10,
  'time': datetime.datetime(2019, 2, 20, 19, 31, 58, 412000),
  'weight': 22.0},
 {'content': '这是评论2',
  'likes': 5,
  'user_weight': 20,
  'time': datetime.datetime(2019, 2, 20, 19, 41, 58, 412000),
  'weight': 79.0},
 {'content': '这是评论1',
  'likes': 20,
  'user_weight': 5,
  'time': datetime.datetime(2019, 2, 20, 20, 1, 58, 412000),
  'weight': 43.0}]

这样写的一个好处就是快, 以及准确. 无论如何, 只要你把单元测试也写对, 上面的写法是不可能出错的.

进阶写法

想象一下, 如果你把上面的过程写完了, 发现运营给你提出了新的需求, 甚至加入了新的 字段. 那么你就要不停的维护上面这一段代码. 每次加上了新的字段, 你需要不断的与运营 的同学对接. 好吧, 我承认渲染的有些过分了, 毕竟产品的排序算法也不会很快的变来变去. 但是不可否认, 确实有一种可以简化操作的写法.

让我们回想上面的表达式:

1
用户权重 * 5 + 点赞数 * 1 + 发布距今秒数 * -0.02

这不就是一个表达式的求值问题吗, 只要程序帮我们把这个表达式解析了, 然后套入 数据就可以了.

这个过程需要分两步进行:

  1. 使程序理解表达式是什么, 该怎么计算
  2. 告诉程序, 表达式中的每个元素如何获取

如何让程序理解计算式

想到这个部分, 我不知道有多少人做过简单的计算器, 其中有什么中缀表达式转后缀. 其实想想转来转去还是挺难的. 自从学习了编译原理, 什么东西都想借助词法, 语法分析一波. 就像下面的表达式树, 就是语法分析之后的结果.

表达式树

表示了一个(a+b)*(c-d))这样的算式, 只要给出abcd的值, 就可以遍历得出.

如何告诉程序每个元素的值

我在下面直接贴出了代码, 请注意看data值如何被使用

下面就是一小段Python代码了, Python中有AST模块, 我们可以借助这个模块进行语法树 的构建, 而后自己去遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import ast
import operator

BINOPS = {
    ast.Add: operator.add,
    ast.Sub: operator.sub,
    ast.Mult: operator.mul,
    ast.Div: operator.truediv,
    ast.Mod: operator.mod,
}
_node = ast.parse('(a+b)*(c-d)', mode='eval')

_data = {
    'a': 2,
    'b': 3,
    'c': 4,
    'd': 5,
}

def make_calculate(node, data):
    # 递归的遍历这棵语法树
    def _eval(node):
        if isinstance(node, ast.Expression):
             return _eval(node.body)
        elif isinstance(node, ast.Name):  # 检查到名称(在这里就是a,b,c,d), 给出相应的值
           return data[node.id]
        elif isinstance(node, ast.Num):  # 检查到数字
            return node.n
        elif isinstance(node, ast.BinOp):  # 检查到二元操作符, + - * /
            return BINOPS[type(node.op)](_eval(node.left), _eval(node.right))
        else:
            raise Exception('Unsupported type {}'.format(node))
    return _eval(node)

make_calculate(_node, _data)  # 可以得到结果为 -5

重新看看输入, 我们给定了表达式(a+b)*(c-d), 又给定了a,b,c,d的值, 就可以计算得到结果, 那么放在刚刚的评论系统中, 权值的求解要怎么进行呢?

正式的解决方案

我们可以列出这样的表达式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
weight_expr = """
'user_weight' * 5 + 'likes' + (0 - 1) * 0.02 * 'time_offset'
"""

# 一些函数调用, 获取属性值
def get_user_weight(topic):
    return topic['user_weight']

def get_likes(topic):
    return topic['likes']

def get_time_offset(topic):
    cur_time = 1550664218.0  # 实际中应该使用 time.time()
    return cur_time - time.mktime(topic['time'].timetuple())

# 存储了一些函数指针
TOPIC_UNIT = {
    'likes': get_likes,
    'user_weight': get_user_weight,
    'time_offset': get_time_offset,
}

# 构建表达式树
_node = ast.parse(weight_expr, mode='eval')

def make_calculate(node, topic):

    def _eval(node):
        if isinstance(node, ast.Expression):
            return _eval(node.body)
        elif isinstance(node, ast.Str):
            # node.s 在这里是'user_weight', 'likes', 或是 'time_offset',
            # 再利用get_user_weight, get_likes 函数, 获取对应评论的属性值
            return TOPIC_UNIT[node.s](topic)
        elif isinstance(node, ast.Num):
            return node.n
        elif isinstance(node, ast.BinOp):
            return BINOPS[type(node.op)](_eval(node.left), _eval(node.right))
        else:
            raise Exception('Unsupported type {}'.format(node))
    return _eval(node.body)


for _topic in topics:
    _topic['weight'] = make_calculate(_node, _topic)

# 毫无疑问, 也可以得到刚刚的结果

本段代码将属性值的获取, 从用户手动调用变成了由程序自动调用. 未来, 假如我们想要增加属性(例如dislikes), 仅仅需要完成下面几件事:

  1. 创建get函数, 例如get_dislikes;
  2. 在TOPIC_UNIT中, 插入 ‘dislikes’: get_dislikes;
  3. 在表达式中增加对’dislikes’的使用;

总结

这次的问题是针对某个对象, 对它的不同属性给予不同的权值来考量其比重, 很适合 使用表达式进行计算, 正好Python自带有的ast库, 可以方便的构建表达式树. 但我还是希望大家能够再理解一下编译原理中的思想: 让程序去理解人类.

各位学弟学妹, 不论老师如何, 你还是可以认真学习一下编译原理的.