Python3中缩短栈(Stack)使用时长的优化——ACMICPC 1406题解法优化

Great job starting with the dual-stack approach for this text editor problem—it's exactly the right intuition since all core operations are amortized O(1)! Let's tweak your code to squeeze out more speed in Python, especially when dealing with large input sizes that can slow down naive implementations.

Key Optimizations to Cut Runtime #

Here are the main changes we'll make, targeted at Python's specific performance characteristics:

• Batch Input Reading: Repeated calls to input() can be slow for large numbers of commands because each call involves I/O overhead. Instead, we'll read all input at once using sys.stdin.read(), then split it into lines for processing. This drastically reduces the number of I/O operations.
• Avoid Python-Level Loops for Stack Merging: Your original code loops through every element in the back stack to move it to front. Instead, we can use list slicing (back[::-1]) to reverse the stack in one go, then concatenate it with front. List operations like slicing and concatenation are implemented in C, so they're far faster than equivalent Python loops.
• Simplify Initial Stack Setup: Instead of looping through each character of the input word to append to front, we can convert the string directly to a list with list(word)—this is a single, efficient operation under the hood.
• Use a Main Function: Wrapping your code in a main() function speeds things up slightly because local variable access in Python is faster than global variable access.

Optimized Code #

import sys

def main():
    # Read all input at once for faster processing
    all_lines = sys.stdin.read().splitlines()
    initial_word = all_lines[0]
    command_count = int(all_lines[1])
    commands = all_lines[2:2 + command_count]
    
    front_stack = list(initial_word)
    back_stack = []
    
    for cmd in commands:
        parts = cmd.split()
        if parts[0] == "P":
            front_stack.append(parts[1])
        elif parts[0] == "L":
            if front_stack:
                back_stack.append(front_stack.pop())
        elif parts[0] == "D":
            if back_stack:
                front_stack.append(back_stack.pop())
        elif parts[0] == "B":
            if front_stack:
                front_stack.pop()
    
    # Merge stacks efficiently with slicing
    print(''.join(front_stack + back_stack[::-1]))

if __name__ == "__main__":
    main()

Why This Works Better #

• Faster Input Handling: sys.stdin.read() reads the entire input stream in one go, which is orders of magnitude faster than calling input() hundreds or thousands of times.
• Efficient Stack Merging: back_stack[::-1] creates a reversed copy of the back stack in optimized C code, and concatenating it with front_stack avoids the overhead of a Python while loop.
• Cleaner Initialization: list(initial_word) directly converts the string to a list of characters without manual iteration, saving both code lines and runtime.

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