可变区间数值分箱排序算法技术需求问询

Solution: Assigning Values to Predefined Bins #

Got it, let's walk through a practical, efficient way to solve this problem. The goal is to map each numerical value to its corresponding predefined bin, with no concern for order within bins. Here's a step-by-step approach with code examples.

1. Define Your Bins Clearly #

First, you need to structure your bins to avoid gaps or overlaps. A common approach is to use left-inclusive, right-exclusive ranges (e.g., [0,10) includes 0 but not 10) except for the final bin, which can extend to infinity. For example:

# Format: (lower_bound, upper_bound, bin_label)
predefined_bins = [
    (-float('inf'), 10, '0-9'),
    (10, 20, '10-19'),
    (20, 30, '20-29'),
    (30, float('inf'), '30+')
]

# Sample values to bin
input_values = [5, 12, 25, 30, 7, 19, 42, 9]

2. Basic Iterative Algorithm (Good for Small Datasets) #

For smaller datasets, a straightforward linear scan works perfectly. We'll iterate through each value and check which bin's range it falls into:

def assign_values_to_bins(values, bins):
    # Initialize empty lists for each bin
    binned_results = {label: [] for _, _, label in bins}
    
    for val in values:
        assigned = False
        for lower, upper, label in bins:
            # Handle the final unbounded bin
            if upper == float('inf'):
                if val >= lower:
                    binned_results[label].append(val)
                    assigned = True
                    break
            # Handle standard left-inclusive, right-exclusive bins
            else:
                if lower <= val < upper:
                    binned_results[label].append(val)
                    assigned = True
                    break
        # Optional: Catch values that don't fit any bin
        if not assigned:
            binned_results.setdefault('unassigned', []).append(val)
    
    return binned_results

# Run the function
output = assign_values_to_bins(input_values, predefined_bins)

# Print results
for bin_label, values in output.items():
    print(f"{bin_label}: {values}")

Output:

0-9: [5, 7, 9]
10-19: [12, 19]
20-29: [25]
30+: [30, 42]

3. Optimized Algorithm for Large Datasets #

If you're working with thousands/millions of values, a linear scan per value is inefficient. Instead, use binary search (via Python's bisect module) to find the correct bin in logarithmic time:

import bisect

def fast_bin_assignment(values, bins):
    # Extract bounds and labels for binary search
    bin_upper_bounds = [upper for _, upper, _ in bins]
    bin_labels = [label for _, _, label in bins]
    
    binned_results = {label: [] for label in bin_labels}
    
    for val in values:
        # Find the bin index using bisect_right (matches our left-inclusive logic)
        bin_index = bisect.bisect_right(bin_upper_bounds, val)
        binned_results[bin_labels[bin_index]].append(val)
    
    return binned_results

# Test the optimized version
fast_output = fast_bin_assignment(input_values, predefined_bins)
for bin_label, values in fast_output.items():
    print(f"{bin_label}: {values}")

This reduces the time complexity from O(n*m) (n values, m bins) to O(n log m), which is a huge win for large datasets.

Key Notes #

• Edge Cases: Make sure to define bins that cover all possible input values (or add an "unassigned" bin for outliers). For boundary values (like 10 in our example), decide upfront whether they belong to the left or right bin and adjust your conditions accordingly.
• Order Independence: Since we're just appending values to bins, the order within each bin doesn't matter—no extra sorting is needed unless you explicitly want it.
• Flexibility: You can adapt this logic to any programming language (e.g., Java's Arrays.binarySearch, JavaScript's Array.findIndex).

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