有限内存下无限时长准周期温度采样的最优存储算法问询

我们有一台带温度探头和自动控温功能的颗粒燃料烟熏炉，核心控制单元是仅配备有限内存与运行时间时钟的嵌入式控制器。烹饪时长不固定且无法预先估算，需要存储温度采样数据，以便在烹饪过程中的任意时刻生成时间-温度折线图。

核心需求如下：

• 总内存配额为M单位（1单位用于运行时钟，剩余M-1单位用于存储温度样本）
• 需维护一组时间间隔近似均匀的样本集，且随着烹饪时长增加，能自动筛选、替换冗余样本，尽可能保留最优时间间隔的样本
• 能否实现不移动样本、不额外存储时间戳？

曾考虑过「蓄水池采样」，但不确定是否适配——因为我们不仅需要保留温度值，还需能重建每个样本的采集时间。

目前有一个效果欠佳的方案：

若分配3单位样本内存，按2的幂次时间间隔采集样本并存储在环形缓冲区中：保留25%时长点、50%时长点和最新读数；当总运行时间翻倍后，最旧的25%读数会被替换，原50%读数成为新的25%时长样本，原最新读数变为中点样本。但该方案的时间分辨率严重偏向过去，几乎无法反映近期温度变化。

优化方案：双向对数分层采样（无时间戳、无样本移动） #

核心思路 #

放弃单向的幂次间隔逻辑，改为分层兼顾历史趋势与近期细节：将已运行时间划分为「近期窗口」与「历史分层窗口」，近期窗口保留高密度样本，历史窗口按对数间隔保留关键节点；同时利用样本槽的固定位置隐含时间层级信息，结合当前总运行时间即可推算出每个样本的采集时刻，无需额外存储时间戳。

具体实现（以M-1=3个样本槽为例） #

假设运行时钟记录的总时长为T，我们给3个样本槽分配固定的时间层级：

1. 槽0（历史层）：对应floor(T/4)时刻的样本（当T翻倍时，该槽的时间层级自动升级，无需移动样本）
2. 槽1（中间层）：对应floor(T/2)时刻的样本
3. 槽2（近期层）：始终存储当前最新的温度样本，对应T时刻

更新逻辑

• 初始状态：所有槽位存储初始温度，对应时间0
• 当总时长T达到2^k（k=1,2,3...，即2、4、8、16...）时，将当前温度写入槽1（覆盖原有内容），原槽1的样本自动对应新的历史层级
• 每当T增加1单位时间时，直接更新槽2的内容为当前温度（覆盖原有内容）

时间推算（无需存储时间戳）

当需要生成折线图时，结合当前T与槽位索引即可算出每个样本的准确时间：

• 槽2的时间 = T（最新时刻）
• 槽1的时间 = floor(T/2)（中点时刻）
• 槽0的时间 = floor(T/4)（1/4时长时刻）

扩展到M-1个样本槽的通用逻辑 #

将M-1个样本槽按索引从0到M-2编号，索引越大对应越近的时间层级：

• 槽i（0 ≤ i ≤ M-3）：对应floor(T / 2^(M-1-i))时刻的样本
• 槽M-2：始终存储当前最新样本，对应T时刻

更新规则：

• 每当T达到2^k时，计算目标槽位：(M-2 - (k mod (M-1)))，将当前温度写入该槽位
• 槽M-2每单位时间更新一次，始终保留最新样本

为什么蓄水池采样不适用 #

蓄水池采样的核心是随机选取固定数量的样本，无法保证时间间隔的均匀性；同时，由于没有时间戳，无法通过样本位置或值反推采集时刻，完全不符合我们的需求。

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