关于基于输入规模的排序算法时长平均困惑及代码性能优化问询

Hey there! Let's work through optimizing your sorting algorithm benchmark and getting those average runtime calculations right. It's totally normal for these kinds of benchmarks to drag if you're not optimizing the test setup, so let's break down the fixes and best practices:

First, Why Your Current Code Might Be Slow #

Chances are, you're either:

• Generating a new random array for every single sort run (wasting cycles on array creation)
• Running too many iterations for larger array sizes (insertion sort gets slow fast with bigger n, so repeating it hundreds of times adds up)
• Not using high-precision timing, which can lead to inaccurate results and unnecessary overhead

Optimized Benchmark Strategy & Code #

Here's a revised approach that cuts down on unnecessary work while keeping your results accurate. I'll use Python as an example (adjust syntax for your language as needed):

import time
import random

# Your existing array generator
def generateArray(num):
    return [random.randint(0, 10000) for _ in range(num)]

# Assume these are your implemented sorting functions
def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]  # Use middle element as pivot to avoid worst-case scenarios
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

def heapsort(arr):
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and arr[i] < arr[l]:
            largest = l
        if r < n and arr[largest] < arr[r]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr.copy()  # Return a copy to avoid modifying the original array

def insertionsort(arr):
    arr_copy = arr.copy()
    for i in range(1, len(arr_copy)):
        key = arr_copy[i]
        j = i - 1
        while j >= 0 and key < arr_copy[j]:
            arr_copy[j+1] = arr_copy[j]
            j -= 1
        arr_copy[j+1] = key
    return arr_copy

def run_benchmark():
    min_size = 1
    max_size = 100
    
    # Dynamic iteration counts: small arrays need more runs for stable averages, large arrays need fewer
    def get_iterations(n):
        if n <= 20:
            return 1000
        elif n <= 50:
            return 500
        else:
            return 200
    
    # Store results: key = algorithm name, value = {size: average_time}
    algo_results = {
        "mergesort": {},
        "quicksort": {},
        "heapsort": {},
        "insertionsort": {}
    }
    
    for size in range(min_size, max_size + 1):
        iterations = get_iterations(size)
        # Pre-generate all test arrays once per size (reuse across all algorithms)
        test_arrays = [generateArray(size) for _ in range(iterations)]
        
        # Test each algorithm
        for algo_name, sort_func in [("mergesort", mergesort), ("quicksort", quicksort), ("heapsort", heapsort), ("insertionsort", insertionsort)]:
            total_runtime = 0.0
            for arr in test_arrays:
                # Use high-precision timer
                start = time.perf_counter()
                sort_func(arr)
                end = time.perf_counter()
                total_runtime += (end - start)
            
            # Calculate average time for this size
            avg_time = total_runtime / iterations
            algo_results[algo_name][size] = avg_time
        
        print(f"Finished benchmarking size {size}/{max_size}")
    
    # Calculate overall average across all sizes 1-100 for each algorithm
    overall_averages = {}
    for algo in algo_results:
        size_avg_times = list(algo_results[algo].values())
        overall_averages[algo] = sum(size_avg_times) / len(size_avg_times)
    
    # Print final results
    print("\n=== Overall Average Runtime (Sizes 1-100) ===")
    for algo, avg_time in overall_averages.items():
        print(f"{algo}: {avg_time:.8f} seconds")
    
    return algo_results, overall_averages

if __name__ == "__main__":
    run_benchmark()

Key Optimizations Explained #

1. Pre-generate Test Arrays
   Instead of making a new array for every sort call, generate all arrays for a given size once, then reuse them across all four algorithms. This cuts down on the overhead of generateArray significantly.

2. Dynamic Iteration Counts
   Small arrays (1-20 elements) sort so fast that individual run times are noisy—we run them 1000 times to get a stable average. Larger arrays (80-100) take longer, so we only run them 200 times to save time without losing accuracy.

3. High-Precision Timing
   time.perf_counter() (Python) is designed for short-duration timing and is far more accurate than wall-clock time functions like time.time(). Use the equivalent in your language (e.g., System.nanoTime() in Java).

4. Avoid Side Effects
   Make sure your sorting functions either return a copy of the sorted array or you pass a copy to them. If you sort the original array in-place, subsequent runs will use a pre-sorted array, which skews results (especially for insertion sort, which is fast on sorted data).

Extra Tips for Even Faster Benchmarks #

• Parallelize Tests: Use multi-threading/multi-processing to run multiple algorithms at the same time (just make sure your sorting functions are thread-safe).
• Optimize Sort Implementations: For quicksort, use a pivot selection strategy like "median-of-three" to avoid worst-case O(n²) runtime. For insertion sort, add an early exit if the current element is already in place.
• Minimize Output: Printing progress updates every few sizes instead of every single one can save a surprising amount of time.

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