Python高效读取指定长度列表输入及排序的最优方法咨询

Hey there! Let's tackle how to optimize your input handling and sorting for those huge datasets with large numbers—IO and memory efficiency are usually the main bottlenecks here, so let's break down the best tweaks you can make.

1. Optimize Input Reading (Biggest Win for Large Datasets) #

Your current approach uses input() twice, which triggers multiple slow IO operations. For massive inputs, reading all data at once with sys.stdin is way faster, since it minimizes system calls. Here's how to adjust your code:

import sys

# Read all input in one go (way faster than line-by-line)
raw_data = sys.stdin.read().split()
n = int(raw_data[0])

# Extract the two lists directly from the flattened data
m = list(map(int, raw_data[1 : n+1]))
q = list(map(int, raw_data[n+1 : 2*n+1]))

Why this works: IO operations are expensive, especially when dealing with millions of elements. By reading everything at once, you cut down on the overhead of multiple input() calls. The split operation is also more efficient on a single large string than on multiple smaller lines.

2. Make Sorting as Efficient as Possible #

Python's built-in list.sort() uses Timsort—a highly optimized hybrid sorting algorithm with an average and worst-case time complexity of O(n log n), which is the theoretical lower bound for comparison-based sorting. You can't beat that for general-purpose sorting, but you can tweak how you store your data to make it even faster:

Use array.array for Memory Efficiency #

If your elements are all integers, using the array module instead of a regular list reduces memory overhead. A compact memory layout means better cache hit rates, which speeds up sorting significantly for huge datasets:

import sys
import array

raw_data = sys.stdin.read().split()
n = int(raw_data[0])

# 'l' denotes signed long integers—adjust the type code if needed (e.g., 'Q' for unsigned 64-bit)
m = array.array('l', map(int, raw_data[1 : n+1]))
q = array.array('l', map(int, raw_data[n+1 : 2*n+1]))

m.sort()
q.sort()

Skip Unnecessary Slicing (If You Can) #

If your input is guaranteed to have exactly n elements per list (no extra data), you can omit the [:n] slicing. Slicing creates a new list, which adds unnecessary memory and time overhead. The code above already extracts the exact ranges you need, so slicing isn't needed here.

3. Avoid Overcomplicating with Parallelism #

You might be tempted to use multiprocessing to sort both lists at once, but don't bother unless your datasets are extremely large (10M+ elements). Python's Global Interpreter Lock (GIL) limits CPU parallelism for threads, and spawning processes adds significant communication overhead. Timsort is already optimized to use CPU cache efficiently, so single-threaded sorting will almost always be faster for most use cases.

Quick Benchmark Tip #

To verify the speedup, use timeit to compare your original and optimized code with a large test input (redirect a big data file to stdin when running):

import timeit

def original_approach():
    n = int(input())
    m = list(map(int, input().split()))[:n]
    q = list(map(int, input().split()))[:n]
    m.sort()
    q.sort()

def optimized_approach():
    import sys
    raw_data = sys.stdin.read().split()
    n = int(raw_data[0])
    m = list(map(int, raw_data[1:n+1]))
    q = list(map(int, raw_data[n+1:2*n+1]))
    m.sort()
    q.sort()

# Run once with your large input
print("Original time:", timeit.timeit(original_approach, number=1))
print("Optimized time:", timeit.timeit(optimized_approach, number=1))

You'll likely see a huge difference in input reading time, especially with very large datasets.

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