Python大文件场景下，高效检查值是否在起止区间内的方法

Great question! Your two initial approaches work for small datasets, but they fall apart with large files or big interval ranges—let’s fix that with a smarter, more efficient solution.

Why Your Current Ideas Struggle #

First, let’s break down the flaws in your existing approaches:

• 思路1 (Generate all values): If you have an interval like 1 1000000, you’ll end up with a list of 1 million integers—this eats up memory fast, and preprocessing takes forever for large ranges.
• 思路2 (Check each interval every time): Even if you remove the unnecessary range loop (you could just check start <= value <= end directly), you’re still looping through every interval for every value you test. With thousands of intervals and values, this becomes painfully slow.

The Optimal Approach: Sorted Intervals + Binary Search #

Here’s a better plan that balances memory usage and speed:

1. Parse and store only interval pairs: No need to generate every number in the range—just save (start, end) tuples.
2. Sort intervals: Sorting lets us use binary search to jump straight to the relevant interval(s) instead of checking all of them.
3. Merge overlapping/adjacent intervals (optional but recommended): This reduces the number of intervals we need to check, making queries even faster.
4. Use binary search for fast lookups: For each value, we can quickly find the interval that could contain it, then verify if the value falls within that interval’s bounds.

Full Python Implementation #

import bisect

# Step 1: Read and parse the interval file
intervals = []
with open('interval_file.txt', 'r') as file:
    for line in file:
        # Split line into integers, handle any whitespace
        numbers = list(map(int, line.strip().split()))
        # Process pairs of start/end values
        for i in range(0, len(numbers), 2):
            start = numbers[i]
            end = numbers[i + 1]
            # Fix cases where start > end (invalid input)
            if start > end:
                start, end = end, start
            intervals.append((start, end))

# Step 2: Sort intervals by their start value
intervals.sort()

# Step 3: Merge overlapping or adjacent intervals (optional optimization)
merged_intervals = []
for current_start, current_end in intervals:
    if merged_intervals:
        last_start, last_end = merged_intervals[-1]
        # If current interval overlaps or touches the last one, merge them
        if current_start <= last_end + 1:
            merged_intervals[-1] = (last_start, max(last_end, current_end))
            continue
    merged_intervals.append((current_start, current_end))
intervals = merged_intervals

# Step 4: Function to check if a value is in any interval
def value_in_intervals(value, intervals):
    # Extract all interval start values for binary search
    start_points = [interval[0] for interval in intervals]
    # Find the first interval start that's greater than our value
    index = bisect.bisect_right(start_points, value)
    # If index is 0, all starts are larger than the value—no match
    if index == 0:
        return False
    # Check the interval right before the found index
    target_start, target_end = intervals[index - 1]
    return target_start <= value <= target_end

# Test with your example values
test_values = [4, 14, 20]
for val in test_values:
    print("TRUE" if value_in_intervals(val, intervals) else "FALSE")

Why This Works So Much Better #

• Memory Efficiency: We only store interval pairs, so even with 10,000 intervals, we’re just storing 20,000 integers—no matter how big each interval is.
• Speed:
  • Preprocessing: Sorting takes O(n log n) time (n = number of intervals), and merging takes O(n) time.
  • Queries: Each value check uses binary search, which is O(log n) time. For 1,000 values and 10,000 intervals, that’s ~1,000 * 14 = 14,000 operations—way faster than the 10,000,000 operations your思路2 would require.
• Robustness: We handle invalid input (like start > end) and merge overlapping intervals to reduce unnecessary checks.

Quick Notes #

• If your intervals never overlap, you can skip the merging step—it still works fine, just with a few more intervals to check.
• For even faster queries, you could precompute a list of end values alongside start values, but the current implementation is already efficient enough for most use cases.

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