如何高效实现带重叠的序列分块？现有方案性能优化求助

Great question! Your current split_overlap works flawlessly for small sequences, but the performance drop on larger datasets makes total sense—you’re repeatedly slicing and copying subsections of the original sequence, which leads to O(n²) time complexity for long inputs. Each seq = seq[size-overlap:] creates a new copy of the remaining sequence, and that overhead adds up fast with big lists.

Let’s break down why your test showed gen_split_overlap as the top performer for long sequences, and formalize that optimized approach.

The Optimal Implementation: Generator-Based Indexing #

The key fix is to avoid modifying and copying the original sequence entirely. Instead, calculate the start indices of each chunk directly and slice only when needed (using a generator to avoid loading all chunks into memory at once):

def gen_split_overlap(seq, size, overlap):
    '''(seq,int,int) => generator yielding chunks
    Split a sequence into chunks of a specific size and overlap. Works also on strings!
    Examples:
    >>> list(gen_split_overlap(seq=list(range(10)),size=3,overlap=2))
    [[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7], [6, 7, 8], [7, 8, 9]]
    >>> list(gen_split_overlap(seq=range(10),size=3,overlap=2))
    [range(0, 3), range(1, 4), range(2, 5), range(3, 6), range(4, 7), range(5, 8), range(6, 9), range(7, 10)]
    '''
    if size < 1 or overlap < 0:
        raise ValueError('"size" must be >= 1 and "overlap" must be >= 0')
    
    step = size - overlap
    if step <= 0:
        # Prevent infinite loops if overlap >= size
        raise ValueError('"overlap" must be less than "size" to avoid repeated chunks')
    
    # Calculate how many full chunks we can generate
    full_chunks = (len(seq) - overlap) // step
    # Yield each full chunk
    for i in range(full_chunks):
        start = i * step
        yield seq[start:start + size]
    
    # Check for a final partial chunk (if any elements remain after full chunks)
    final_start = full_chunks * step
    if final_start < len(seq):
        yield seq[final_start:]

Why This Is Faster #

• No repeated sequence copying: We only slice the original sequence when we need a chunk, instead of creating a new sub-sequence in every loop iteration.
• Generator memory efficiency: For huge sequences, this doesn’t load all chunks into memory at once—you iterate through chunks on demand, which is critical for datasets that don’t fit in RAM.
• O(n) time complexity: Each element is accessed exactly once (slice operations are O(k) where k is chunk size, but overall this is linear time vs. your original O(n²)).

Matching Your Original Function’s Output #

If you need the exact same behavior as your original split_overlap (returning a list instead of a generator), just wrap the generator:

def split_overlap_optimized(seq, size, overlap):
    return list(gen_split_overlap(seq, size, overlap))

Context on Your Test Results #

Looking at your benchmarks:

• Your original split_overlap is fastest for short sequences because generators have a tiny startup overhead, which gets lost in the noise for small inputs.
• gen_split_overlap pulls ahead on long sequences because it eliminates the massive copying overhead of your original approach.
• Other tested functions like nwise_overlap and split_overlap_Moinuddin had incorrect outputs (extra chunks with None or truncated elements), so they’re invalid for your use case.

Final Notes #

• This implementation preserves support for lazy sequences like range (just like your original function)—slicing a range returns a new range object instead of copying elements, making it even more efficient.
• If you ever need to handle sequences where len() isn’t available (like custom iterators), you’d need a different approach using sliding windows with itertools, but for all indexable sequences (lists, strings, tuples, ranges), this is the fastest approach.

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