面试题：带重复名字取最新值规则的滚动均值计算

问题需求 #

给定包含time（时间点）、names（姓名）、val（数值）的数据集，需要计算截至每个时间点的均值：

• 同一姓名仅保留当前时间点及之前的最新数值（比如时间2的Andy取5，而非时间1的1）
• 要求解法高效，避免重复计算均值，不限定使用Pandas

纯Python高效解法 #

核心思路是用字典追踪每个姓名的最新数值，同时维护累计总和和有效元素数量，每处理一条数据仅做常数时间的更新，无需重复遍历历史数据：

def calculate_running_mean(data):
    # 先按时间排序（若原数据已按时间有序可省略）
    sorted_data = sorted(data, key=lambda x: x["time"])
    latest_values = {}
    total_sum = 0
    unique_count = 0
    time_mean = {}

    for entry in sorted_data:
        time, name, val = entry["time"], entry["names"], entry["val"]
        
        if name in latest_values:
            # 替换旧值：总和减去旧值
            total_sum -= latest_values[name]
        else:
            # 新增姓名：计数加1
            unique_count += 1
        
        # 更新最新值与总和
        latest_values[name] = val
        total_sum += val
        
        # 同一时间的所有条目处理完后，记录最终均值
        time_mean[time] = total_sum / unique_count

    return time_mean

# 测试用例
sample_data = [
    {"time": 1, "names": "Andy", "val": 1},
    {"time": 1, "names": "Bob", "val": 2},
    {"time": 1, "names": "Karen", "val": 3},
    {"time": 2, "names": "Andy", "val": 5},
    {"time": 2, "names": "Matt", "val": 6},
    {"time": 2, "names": "Sim", "val": 8},
]

print(calculate_running_mean(sample_data))
# 输出：{1: 2.0, 2: 4.8}

效率说明

• 时间复杂度：若原数据无序则为O(n log n)（排序开销），若数据已按时间有序则为O(n)
• 空间复杂度：O(k)，k为不同姓名的数量，仅存储每个姓名的最新值，内存占用低
• 完全避免重复计算：每次仅更新总和与计数，无需重新遍历所有历史数据计算均值

Pandas 高效解法 #

如果需要基于Pandas数据集处理，同样沿用字典追踪的思路，结合迭代实现高效计算：

import pandas as pd

def pandas_running_mean(df):
    # 按时间排序确保处理顺序正确
    sorted_df = df.sort_values("time")
    latest_values = {}
    total_sum = 0
    unique_count = 0
    results = []

    for _, row in sorted_df.iterrows():
        time, name, val = row["time"], row["names"], row["val"]
        
        if name in latest_values:
            total_sum -= latest_values[name]
        else:
            unique_count += 1
        
        latest_values[name] = val
        total_sum += val
        results.append({"time": time, "mean": total_sum / unique_count})

    # 去重保留每个时间点的最终均值（同一时间的多条目处理完后均值才稳定）
    result_df = pd.DataFrame(results).drop_duplicates("time", keep="last").set_index("time")
    return result_df

# 测试用例
data = pd.DataFrame({
    'time': [1, 1, 1, 2, 2, 2],
    'names': ["Andy", "Bob", "Karen", "Andy", "Matt", "Sim"],
    'val': [1, 2, 3, 5, 6, 8]
})

print(pandas_running_mean(data))
# 输出：
#       mean
# time     
# 1      2.0
# 2      4.8

核心逻辑总结 #

两种方法的核心都是动态维护状态：

1. 用字典记录每个姓名的最新数值，避免重复存储历史数据
2. 实时更新累计总和与唯一姓名计数，每次计算均值仅需总和/计数，无需重新遍历所有数据

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