火车票购票问题2

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

看过火车票购票问题1
的朋友可能已经发现，还有可以优化的方案

方案1：
在处理购票请求的后期，某些站点区间可用的票数已经为0,
那么后续再有类似请求时，可以直接返回失败

这里的特殊情况是，如果有人退票，则某个站点区间又会有可卖的票，可以通过在购票高峰期限制退票来排除这个特殊情况。

对应文件 sell2.py

# -*- coding: utf-8 -*-
############################################################
# 假定站点编号从 1 ~ 10
# 共20节车厢, 每个车厢20排
# 编号形如
# 1A 1B 1C 1D 1F
# 2A 2B 2C 2D 2F
# ...
# 20A 20B 20C 20D 20F
# 20 * 5 * 20 = 2000个座位
# 其实座位编号完全可以从 0 ~ 1999, 并不影响我们对问题本身的分析
############################################################
import time

MAX_CARRIAGE_NUM = 20
MAX_ROW_NUM = 20
MAX_SITE_INDEX = 10


class Seg(object):
    def __init__(self, carriage_no, seat_no, start_site, end_site):
        # 车厢编号
        self.carriage_no = carriage_no
        # 座位编号
        self.seat_no = seat_no
        # 完整编号
        self.no = str(carriage_no) + '-' + seat_no
        # 能够售卖的开始站序号 int
        self.start_site = start_site
        # 能够售卖的终点站序号  int
        self.end_site = end_site

    def __str__(self):
        return str((self.no, self.start_site, self.end_site))


def init():
    ticket_dict = {}
    for i in range(1, MAX_SITE_INDEX):
        for j in range(i + 1, MAX_SITE_INDEX + 1):
            ticket_dict[(i, j)] = []

    for i in range(1, MAX_CARRIAGE_NUM + 1):
        for row in range(1, MAX_ROW_NUM + 1):
            for col in ['A', 'B', 'C', 'D', 'F']:
                # 每个座位都可以出售从s1 到 s10的车票
                key = (1, 10)
                # print Seg(i, str(row) + col, 1, 10)
                ticket_dict[key].append(Seg(i, str(row) + col, 1, 10))

    return ticket_dict


def sell(ticket_dict, start, end, sellout_dict):
    '''

    :param ticket_dict:
    :param start:  购票的起始站
    :param end: 购票的终点站
    :return:
    '''
    if sellout_dict.get((start, end), False):
        return None

    # 需要找到一个有票的站点区间覆盖目标站点区间
    # 所有可能的起始站
    site_start = []
    x = 1
    while x <= start:
        site_start.append(x)
        x += 1
    site_start.reverse()

    # 所有可能的终点站
    site_end = []
    y = end
    while y <= MAX_SITE_INDEX:
        site_end.append(y)
        y += 1

    ticket = None
    for x in site_start:
        for y in site_end:
            if len(ticket_dict[(x, y)]) > 0:
                ticket = ticket_dict[(x, y)].pop()
            if ticket:
                # 判断一下这个座位的站点区间是否被完全用完了
                # 如果没有还需要把新生成的余票间存回去
                if start > x:
                    temp = Seg(ticket.carriage_no, ticket.seat_no, x, start)
                    ticket_dict[(x, start)].append(temp)
                if y > end:
                    temp = Seg(ticket.carriage_no, ticket.seat_no, end, y)
                    ticket_dict[(end, y)].append(temp)

                return Seg(ticket.carriage_no, ticket.seat_no, start, end)
    # 对于(start, end), 没有可以卖的票
    # 那说明所有覆盖 (start, end) 的站点区间都没有票了
    for x in site_start:
        for y in site_end:
            sellout_dict[(x, y)] = True

    return None

def print_residual(ticket_dict):
    print '------------余票情况-------------'
    for key in ticket_dict:
        if ticket_dict[key]:
            print key, len(ticket_dict[key])

if __name__ == '__main__':
    ticket_dict = init()
    sellout_dict = {}
    t1 = time.time()
    with open('req.csv') as fp:
        for line in fp:
            ll = line.split(',')
            user = ll[0]
            start = int(ll[1])
            end = int(ll[2])
            ticket = sell(ticket_dict, start, end, sellout_dict)
            print '#' * 100
            print line.strip()
            if ticket:
                print user, "bought", ticket

            print_residual(ticket_dict)
            # time.sleep(2)
    t2 = time.time()
    print t2 - t1

经过测试，速度又提升了20% ，处理10w请求只用了1秒多

方案2：考虑多线程并发处理
经过测试，速度反而下降了60倍，很有可能是因为计算量不大，且资源竞争以及频繁的上下文切换，反而影响了性能

对应文件 sell3.py
完整代码地址：
https://github.com/vearne/train_ticket

后记：
本文只是对购票过程的一个模拟，但是将不同的车次分而治之的处理，确实是一个提高并发能力的一个好方法。并且可以考虑内存处理 + 数据库处理相结合的办法，或者直接将数据移植到数据库中进行操作以确保事务性。