python - Python 中的高效排类

Question

我目前正在为一家模范出租车公司做一些类次安排模拟。公司运营着 350 辆出租车，每天都在使用。司机每人工作 5 类，每类 12 小时，每天有四类重叠。 3:00-15:00、15:00-3:00、16:00-4:00、4:00-16:00轮类。本来是用Python开发的，因为需要快速开发，觉得性能可以接受。原始参数只需要一天两类(3:00-15:00 和 15:00-3:00)，虽然性能不是很好，但足以满足我的使用需求。它可以在大约 8 分钟内为司机制定每周时间表，使用简单的蛮力算法(评估所有潜在的交换以查看情况是否可以改善。)

由于四个重叠类次，性能绝对糟糕。做每周计划需要一个多小时。我已经使用 cProfile 进行了一些分析，看起来主要的罪魁祸首是两种方法。一种是确定在安排司机换类时是否存在冲突的方法。它确保他们不会在同一天轮类服务，或者在之前或之后的轮类服务。一天只有两类倒，这很容易。只需确定司机是否已被安排在紧接之前或之后的类次工作。随着四个重叠类次，这变得更加复杂。第二个罪魁祸首是确定轮类是白类还是夜类的方法。同样，对于最初的两个类次，这就像确定类次编号是偶数还是奇数一样简单，类次编号从 0 开始。第一个类次(第 0 个类次)被指定为夜类，下一个类次是白天，并且等等等等。现在前两个是night，后两个是，等等。这些方法相互调用，所以我将它们的主体放在下面。

def conflict_exists(shift, driver, shift_data):
    next_type = get_stype((shift+1) % 28)
    my_type = get_stype(shift)

    nudge = abs(next_type - my_type)

    if driver in shift_data[shift-2-nudge] or driver in shift_data[shift-1-nudge] or driver in shift_data[(shift+1-(nudge*2)) % 28] or driver in shift_data[(shift+2-nudge) % 28] or driver in shift_data[(shift+3-nudge) % 28]:
        return True
    else:
        return False

请注意，get_stype 返回类次类型，0 表示它是夜类，1 表示它是白类。

为了确定类次类型，我使用了这种方法:

def get_stype(k):
    if (k / 4.0) % 1.0 < 0.5:
        return 0
    else:
        return 1

这是 cProfile 的相关输出:

     ncalls  tottime  percall  cumtime  percall
     57662556   19.717    0.000   19.717    0.000 sim8.py:241(get_stype)
     28065503   55.650    0.000   77.591    0.000 sim8.py:247(in_conflict)

有没有人对我如何改进这个脚本的性能有任何明智的建议或提示？任何帮助将不胜感激!

干杯，

蒂姆

编辑:抱歉，我应该澄清一下，每个类次的数据都存储为一个集合，即 shift_data[k] 是集合数据类型。

编辑 2:

根据下面的请求添加主循环，以及调用的其他方法。有点乱，对此我深表歉意。

def optimize_schedule(shift_data, driver_shifts, recheck):
    skip = set()

    if len(recheck) == 0:
        first_run = True
        recheck = []
        for i in xrange(28):
            recheck.append(set())
    else:
        first_run = False

    for i in xrange(28):

        if (first_run):
            targets = shift_data[i]
        else:
            targets = recheck[i]

        for j in targets:
            o_score = eval_score = opt_eval_at_coord(shift_data, driver_shifts, i, j)

            my_type = get_stype(i)
            s_type_fwd = get_stype((i+1) % 28)

            if (my_type == s_type_fwd):
                search_direction = (i + 2) % 28
                end_direction = i
            else:
                search_direction = (i + 1) % 28 
                end_direction = (i - 1) % 28 

            while True:
                if (end_direction == search_direction):
                    break
                for k in shift_data[search_direction]:

                    coord = search_direction * 10000 + k 

                    if coord in skip:
                        continue

                    if k in shift_data[i] or j in shift_data[search_direction]:
                        continue

                    if in_conflict(search_direction, j, shift_data) or in_conflict(i, k, shift_data):
                        continue

                    node_a_prev_score = o_score
                    node_b_prev_score = opt_eval_at_coord(shift_data, driver_shifts, search_direction, k)

                    if (node_a_prev_score == 1) and (node_b_prev_score == 1):
                        continue

                    a_type = my_type
                    b_type = get_stype(search_direction)

                    if (node_a_prev_score == 1):
                        if (driver_shifts[j]['type'] == 'any') and (a_type != b_type):
                            test_eval = 2
                        else:
                            continue
                    elif (node_b_prev_score == 1):
                        if (driver_shifts[k]['type'] == 'any') and (a_type != b_type):
                            test_eval = 2
                        else:
                            test_eval = 0
                    else:
                        if (a_type == b_type):
                            test_eval = 0
                        else:
                            test_eval = 2

                    print 'eval_score: %f' % test_eval

                    if (test_eval > eval_score):

                        cand_coords = [search_direction, k]
                        eval_score = test_eval
                        if (test_eval == 2.0):
                            break
                else:
                    search_direction = (search_direction + 1) % 28
                    continue

                break

            if (eval_score > o_score):
                print 'doing a swap: ',
                print cand_coords,

                shift_data[i].remove(j)
                shift_data[i].add(cand_coords[1])

                shift_data[cand_coords[0]].add(j)   
                shift_data[cand_coords[0]].remove(cand_coords[1])

                if j in recheck[i]:
                    recheck[i].remove(j)

                if cand_coords[1] in recheck[cand_coords[0]]:               
                    recheck[cand_coords[0]].remove(cand_coords[1])

                recheck[cand_coords[0]].add(j)
                recheck[i].add(cand_coords[1])

            else:
                coord = i * 10000 + j
                skip.add(coord)

    if first_run:
        shift_data = optimize_schedule(shift_data, driver_shifts, recheck)

    return shift_data



def opt_eval_at_coord(shift_data, driver_shifts, i, j):
    node = j
    if in_conflict(i, node, shift_data):
        return float('-inf')
    else:
        s_type = get_stype(i)

        d_pref = driver_shifts[node]['type']

        if (s_type == 0 and d_pref == 'night') or (s_type == 1 and d_pref == 'day') or (d_pref == 'any'):
            return 1
        else:
            return 0

Answer 1

没有什么会明显减慢这些函数的速度，事实上它们并不慢。他们只是经常接到电话。你说你正在使用蛮力算法——你能写一个不尝试所有可能组合的算法吗？或者是否有更有效的方法，例如按驾驶员而不是轮类存储数据？

当然，如果您需要即时加速，在 PyPy 等解释器中运行或使用 Cython 将关键部分转换为 C 可能会有所帮助。