python - 为最短的执行时间重新安排任务

Question

在 Python 2.7 中处理以下任务重新安排问题、发布问题和我的代码。我的具体问题，

1. 有没有更好的优化算法时间复杂度(或空间复杂度)的想法？
2. 当我们发现一个任务不能被安排时(意味着被另一个不同的任务分开，这样就没有额外的等待时间)，我目前的实现是将这样的任务放在任何空闲槽中(引用while counter < f的循环)，并且我想知道我应该做的是 (1) 将剩余的未安排的任务/频率放回堆中，以及 (2) 找到下一个高频任务来处理？

对于公告点 2，我测试过我的代码没问题(没问题意味着我的代码返回最少的执行时间加上等待时间)，但是如果有任何错误，我应该执行 (1) 和 (2) 而不是我当前的实现，欢迎大家指出。

问题

给定一组任务 [A, A, B] 和 int k，这是两个相同任务之间的等待时间。如果允许重新安排任务，请计算最短总执行时间。假设每个单独任务的执行次数为 1。

在上面的例子中A A B, k = 1, 不重排, 执行时间为4:

A wait A B

1  1   1 1

重新排列后，执行时间为 3:

A B A

1 1 1

源代码,

from collections import defaultdict
import heapq


def rearrange_tasks(tasks):
    freq = defaultdict(int)
    for t in tasks:
        freq[t] += 1
    h = []
    heapq.heapify(h)
    result = [0] * len(tasks)
    for t,f in freq.items():
        heapq.heappush(h, (-f, t))
    while len(h) > 0:
        f, t = heapq.heappop(h)
        f = -f
        write_index = 0
        while write_index < len(result) and result[write_index] != 0:
            write_index += 1
        counter = 0
        while write_index < len(result) and counter < f:
            result[write_index] = t
            write_index += 2
            counter += 1
        # write tasks which have to be consecutive
        write_index = 0
        while counter < f:
            if result[write_index] != 0:
                write_index += 1
            else:
                result[write_index] = t
                write_index += 1
                counter += 1
    return result


def calculate_execution_time(tasks, k):
    exec_time = 0
    for i, t in enumerate(tasks):
        if i == 0:
            exec_time += 1
            continue
        if t == tasks[i-1]:
            exec_time += k
            exec_time += 1
        else:
            exec_time += 1
    return exec_time

if __name__ == "__main__":
    tasks = ['A', 'A', 'B']
    result = rearrange_tasks(tasks)
    print result
    print calculate_execution_time(result, 1)

    tasks = ['A', 'A', 'A', 'A', 'C', 'D', 'E', 'E', 'B', 'B', 'B']
    result = rearrange_tasks(tasks)
    print result
    print calculate_execution_time(result, 1)

编辑 1:

使用条件 while write_index < len(result) and counter < f: 修复超出索引的错误, 除了条件 counter < f:

Answer 1

您的代码似乎在某些输入上引发了错误。例如，我试过这个:

['A', 'A', 'B', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C']

...
  File "orig.py", line 22, in rearrange_tasks
    result[write_index] = t
IndexError: list assignment index out of range

以下是一些建议的更改。他们不太关注优化速度，而是更关注算法的清晰度。我有点怀疑您是否应该过分担心速度——您的输入有多大，有多少不同的任务值？该算法似乎主要是线性的，尤其是在不同任务值的数量很少的情况下。

from collections import Counter
from heapq import heapify, heappop, heappush

def rearrange_tasks(tasks):

    # Make a heap of (-FREQ, TASK) tuples.
    freq = Counter(tasks)
    h = [(-f, t) for t, f in freq.items()]
    heapify(h)

    result = []
    prev = None
    while h:
        # Get the most frequent item.
        f, t = heappop(h)

        # If it is a repeat and if there are other items,
        # put it back and grab 2nd most frequent item instead.
        if t == prev and h:
            item = (f, t)
            f, t = heappop(h)
            heappush(h, item)

        # Put selected item back on heap, after adjusting frequency.
        if f < -1:
            heappush(h, ((f + 1), t))

        # Add task to the result.
        result.append(t)
        prev = t

    return result

def calculate_execution_time(tasks, k):
    n = 0
    prev = None
    for t in tasks:
        n += 1 + int(t == prev) * k
        prev = t
    return n

def run(tasks):
    result = rearrange_tasks(tasks)
    assert Counter(tasks) == Counter(result)
    print
    print 'len    =', len(tasks)
    print 'time   =', calculate_execution_time(result, 1)
    print 'result =', ''.join(result)

if __name__ == "__main__":
    run('AAB')
    run('AABCCCCCCCC')
    run('AAAACDEEBBB')
    run('AAAACDEEBBBBBBBBBBBB')