0

我有以下算法：我有一个图和一个相关我有一个拓扑排序（在图论中，“有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于每个有向边 uv 来自顶点u 到顶点 v，u 在排序中排在 v 之前。")。给定 astart_position和 an end_position（与 start_one 不同），我想验证是否将列表中的元素移动start_position到end_position保留拓扑顺序，即，如果在移动之后我仍然有拓扑顺序。

有两种情况：left_shift（如果start_position> end_position）和 right_shift（否则）。

在此处输入图像描述 在此处输入图像描述

这是我的尝试：

    def is_insert_ok(from_position:int, to_position:int, task_list:List[str], instance:pb.Problem): 
    # Problem has an attribute of all the tasks.
    # it's a dictionnary whose keys are str and values are task objects
        if from_position < to_position :
            # right_shift 
            for task_temp in task_list[from_position+1:to_position+1]:
                if task_list[from_position] in instance.all_tasks[task_temp].predecessors.keys():
                    return False
            return True

        if  to_position < from_position :
            # left shift
            for task_temp in task_list[to_position:from_position]:
                if task_temp in instance.all_tasks[task_list[from_position]].predecessors.keys():
                    return False
            return True

那个代码有什么问题？出色地。这是事情，如果我有一些列表并且我想计算

列表中每个元素的每个可能的移位，如下面的函数所示：

def compute_neighbors(instance:pb.Problem, schedule:sl.Solution):
    first_non_dummy_position = len(instance.orders) #there is some elements to ignore at the begining of the list because they can't be shifted
    current_schedule = schedule
    neighbors_list = []
    task_list = current_schedule.activity_list.copy()
    for first_task in task_list[first_non_dummy_position:]:
        from_position = task_list.index(first_task)
        for second_task in task_list[first_non_dummy_position:]:
            task_list = current_schedule.activity_list.copy()
            to_position = task_list.index(second_task)
            if to_position != from_position:
                if is_insert_ok(from_position,to_position, task_list, instance):
                    insert(from_position, to_position, task_list, instance) #see below the function insert
                    if task_list not in neighbors_list:
                        neighbors_list.append(task_list)

def insert(from_position:int, to_position:int, task_list:List[str], instance:pb.Problem):
    element_to_insert  = task_list.pop(from_position)
    task_list.insert(to_position, element_to_insert)

当我有一个长度为 2000 的列表时，它花了很长时间。关于如何使它更快的任何想法？

我欢迎任何尝试。如果您不理解我的代码中的某些内容，请随时问我。

4

1 回答 1

1
  • 你一遍又一遍地做同样的事情。如果您知道，您不能将项目向右移动 20 位，那么您也不能将其移动 40 位。绝对不是2458个地方。
  • 如果您知道，您可以将项目向右移动 100 个位置，那么在下一次运行中，您测试是否可以将其移动 101 个位置并再次开始测试这 100 个项目。为什么，您在之前的循环中测试了它们。
  • if task_list not in neighbors_list这会很昂贵。出现重复的唯一情况是向右移动和向左移动 1 个位置。只需跳过这两种情况之一。
  • 即使您不需要它，您也可以制作该列表的副本。在您测试插入是否正常并且您确实需要它之后制作一份副本。

你应该重新安排程序，不要一次又一次地做同样的事情，只做你需要的事情。

于 2020-08-30T04:30:01.623 回答