拓扑排序列表移位合法性验证及大列表性能优化求助

Let’s break down why your compute_neighbors function is running so slowly for large task lists, and walk through practical, actionable optimizations to speed it up:

1. Ditch Repeated list.index() Calls (O(n) → O(1) per access) #

Right now, you’re looping over task elements and calling task_list.index(first_task)/task_list.index(second_task) every time. Each index() call scans the entire list from the start to find the element—this is O(n) per call, and with 2000 elements, that’s 2000×2000 = 4,000,000 expensive scans.

Fix: Iterate directly over indices instead of elements. This lets you get from_position and to_position for free:

def compute_neighbors(instance: pb.Problem, schedule: sl.Solution):
    first_non_dummy_position = len(instance.orders)
    original_task_list = schedule.activity_list
    neighbors_list = []
    neighbors_set = set()  # For duplicate checks later
    
    # Preprocess predecessor sets for O(1) lookups (see optimization 3)
    pred_sets = {task: set(instance.all_tasks[task].predecessors.keys()) 
                 for task in original_task_list}
    
    # Iterate over valid from positions
    for from_pos in range(first_non_dummy_position, len(original_task_list)):
        # Iterate over valid to positions
        for to_pos in range(first_non_dummy_position, len(original_task_list)):
            if from_pos == to_pos:
                continue  # Skip no-op moves
            
            # Check if the move is valid (using optimized is_insert_ok)
            if is_insert_ok_optimized(from_pos, to_pos, original_task_list, pred_sets):
                # Only copy the list when we know we need a neighbor
                new_task_list = original_task_list.copy()
                insert(from_pos, to_pos, new_task_list, instance)
                # Use a tuple for set lookup (lists are unhashable)
                new_tuple = tuple(new_task_list)
                if new_tuple not in neighbors_set:
                    neighbors_set.add(new_tuple)
                    neighbors_list.append(new_task_list)

2. Cut Redundant List Copies #

Your original code copies the entire task list every time you loop over second_task, even if the move isn’t valid. For 2000 elements, each copy is O(n), and doing this 4 million times is catastrophic for performance.

Fix: Only copy the original list after you confirm the move is valid (via is_insert_ok). This eliminates thousands of unnecessary copies.

3. Speed Up is_insert_ok with Precomputed Sets #

The is_insert_ok function currently checks membership in a dictionary’s .keys() view, which is O(k) per check (k = number of predecessors). By precomputing a set of predecessors for each task, you can drop this to O(1) per membership check.

Optimized is_insert_ok:

def is_insert_ok_optimized(from_pos: int, to_pos: int, task_list: List[str], pred_sets: Dict[str, Set[str]]):
    moving_task = task_list[from_pos]
    if from_pos < to_pos:  # Right move
        # Check all tasks between from+1 and to: none can have moving_task as a predecessor
        for pos in range(from_pos + 1, to_pos + 1):
            if moving_task in pred_sets[task_list[pos]]:
                return False
        return True
    else:  # Left move
        # Check all tasks between to and from-1: none can be a predecessor of moving_task
        for pos in range(to_pos, from_pos):
            if task_list[pos] in pred_sets[moving_task]:
                return False
        return True

4. Replace Slow Duplicate Checks with a Set #

Your original code uses if task_list not in neighbors_list: to avoid duplicates. Checking membership in a list is O(m) (m = number of neighbors found so far), which gets slower as the neighbor list grows.

Fix: Use a set to store tuples of valid neighbor lists (since lists are unhashable, tuples work). Checking membership in a set is O(1), which drastically speeds up duplicate checks.

5. Prune Unnecessary Iterations (Optional) #

If you want to go further, you can prune iterations where moving a task won’t produce a valid neighbor:

• For right moves: If the task has no successors in the range from_pos+1 to to_pos, you can skip some checks (though the set optimization already makes this fast).
• For left moves: Similarly, skip moves where the task has no predecessors in the target range.

Even without this pruning, the first four optimizations will bring your runtime from O(n³) down to O(n²), which is night-and-day for 2000-element lists.

内容的提问来源于stack exchange，提问作者Best_fit