如何为代码设置定时器？测试60秒内binom_coeff_recur计算上限

Hey there! Let's tackle your two questions one by one, since they're related but have different practical solutions.

1. 如何为代码执行设置定时器？ #

There are two common approaches depending on your goal:

• Option 1: Simple execution time tracking
  If you just want to measure how long a piece of code takes to run, use the time module to calculate the difference between start and end times (like the snippet you already started with). Example:

  import time
  start_time = time.time()
  
  # Run your target code
  result = binom_coeff_recur(10, 5)
  
  end_time = time.time()
  print(f"Execution time: {end_time - start_time:.2f} seconds")
  

• Option 2: Enforce timeout termination
  If you need to stop code automatically after it exceeds a specified time (critical for your second question), use the signal module (works best on Linux/macOS; for Windows, we'll use threading as an alternative later).

2. Test the maximum binom_coeff_recur value computable in 60 seconds #

Recursive combination calculation is extremely inefficient due to massive repeated computations. We'll set a 60-second timeout and test incrementally larger n values (we'll use k = n//2 since this is the most computationally intensive case—where the binomial coefficient is largest).

Solution for Linux/macOS (using signal) #

import time
import signal

# Define a custom timeout exception
class TimeoutError(Exception):
    pass

def timeout_handler(signum, frame):
    raise TimeoutError("Code execution timed out")

# Set up the 60-second timeout trigger
signal.signal(signal.SIGALRM, timeout_handler)

def binom_coeff_recur(n, k):
    if k == 0 or k == n:
        return 1
    return binom_coeff_recur(n-1, k-1) + binom_coeff_recur(n-1, k)

def find_max_computable_n():
    max_valid_n = 0
    # Test incrementally larger n values (adjust upper range if needed)
    for n in range(1, 100):
        k = n // 2
        print(f"Testing n={n}, k={k}...")
        signal.alarm(60)  # Activate 60-second timeout for this test
        try:
            start = time.time()
            result = binom_coeff_recur(n, k)
            end = time.time()
            print(f"Success! Result: {result}, Time taken: {end - start:.2f}s")
            max_valid_n = n  # Update the largest valid n
        except TimeoutError:
            print(f"Timeout reached for n={n}, stopping tests")
            break
        finally:
            signal.alarm(0)  # Reset the timeout for the next test
    print(f"\nMaximum n computable in 60 seconds: {max_valid_n} (with k={max_valid_n//2})")

if __name__ == "__main__":
    find_max_computable_n()

Solution for Windows (using threading—since signal.SIGALRM isn't supported) #

import time
import threading

# Global variable to store computation results
computation_result = None

def compute_binomial(n, k):
    global computation_result
    computation_result = binom_coeff_recur(n, k)

def find_max_computable_n_windows():
    max_valid_n = 0
    for n in range(1, 100):
        k = n // 2
        print(f"Testing n={n}, k={k}...")
        # Start computation in a separate thread
        compute_thread = threading.Thread(target=compute_binomial, args=(n, k))
        compute_thread.start()
        
        # Wait for 60 seconds; if thread is still alive, it timed out
        compute_thread.join(timeout=60)
        
        if compute_thread.is_alive():
            print(f"Timeout reached for n={n}, stopping tests")
            break
        else:
            start = time.time()
            print(f"Success! Result: {computation_result}, Time taken: {time.time() - start:.2f}s")
            max_valid_n = n
    print(f"\nMaximum n computable in 60 seconds: {max_valid_n} (with k={max_valid_n//2})")

def binom_coeff_recur(n, k):
    if k == 0 or k == n:
        return 1
    return binom_coeff_recur(n-1, k-1) + binom_coeff_recur(n-1, k)

if __name__ == "__main__":
    find_max_computable_n_windows()

Quick Notes #

• The recursive binom_coeff_recur is very slow—you'll likely hit a timeout around n=35-40 even on modern CPUs. For larger values, use dynamic programming or Python's built-in math.comb() (Python 3.10+) which is exponentially faster.
• Close other CPU-heavy programs during testing to get accurate results.

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