如何用Python3.6基于值-出现次数字典计算数据集中位数？

Problem Statement #

I have a dictionary in the following form (much larger in practice):

data = { 100: 8, 110: 2, 1000: 4, 2200: 3, 4000: 1, 11000: 1, }

Where each key-value pair represents value: occurrence_count in the dataset. I need to calculate the median of this dataset using Python 3.6. Note: Due to the large size of the dataset, I don't want to generate a full list (which is why I'm using a dictionary in the first place) and am looking for an alternative approach.

Solution #

Hey there, totally get why you don't want to expand the dictionary into a full list—with large datasets, that's a huge waste of memory. Let's solve this by calculating the median using cumulative frequencies directly from the frequency dictionary, no full list required.

Here's a step-by-step breakdown of the approach:

• Calculate the total number of elements in the dataset by summing all the frequency values.
• Determine the position(s) of the median:
  • If the total count is odd, the median is the element at position (total + 1) // 2
  • If even, it's the average of elements at positions total // 2 and total // 2 + 1
• Sort the unique values from the dictionary, then iterate through them while accumulating frequencies. Stop when the cumulative count covers the median position(s) we need.

Python 3.6 Implementation #

def calculate_median(freq_dict):
    # Calculate total number of elements in the dataset
    total_elements = sum(freq_dict.values())
    
    # Determine which positions we need to find for the median
    median_positions = []
    if total_elements % 2 == 1:
        median_positions.append((total_elements + 1) // 2)
    else:
        median_positions.append(total_elements // 2)
        median_positions.append(total_elements // 2 + 1)
    
    # Sort the unique values to process them in numerical order
    sorted_values = sorted(freq_dict.keys())
    cumulative_count = 0
    median_candidates = []
    
    for val in sorted_values:
        count = freq_dict[val]
        cumulative_count += count
        
        # Check if current cumulative count covers any of the remaining median positions
        for pos in median_positions[:]:  # Use slice to avoid modifying list during iteration
            if pos <= cumulative_count:
                median_candidates.append(val)
                median_positions.remove(pos)
        
        # Exit early once all required positions are found
        if not median_positions:
            break
    
    # Compute the final median (average if even number of elements)
    return sum(median_candidates) / len(median_candidates)

# Test with your sample data
data = {100: 8, 110: 2, 1000: 4, 2200: 3, 4000: 1, 11000: 1}
print(calculate_median(data))  # Output: 110.0

Explanation #

• For your sample data, the total number of elements is 8+2+4+3+1+1=19 (odd), so we need the 10th element.
• When we iterate through sorted values:
  • After processing 100 (count 8), cumulative count is 8 (not enough for position 10)
  • Processing 110 (count 2) brings cumulative count to 10, which covers position 10—so 110 is our median.
• This approach is efficient because we only sort the unique values (not the entire dataset), and stop iterating as soon as we find the required positions. The time complexity is dominated by sorting the unique values: O(k log k) where k is the number of unique values, which is way better than O(n) memory usage for a full list.

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