O4EasyPart O · BA→Python 数据科学化与统计算子

无 SQL 窗口函数手写乱序事件流 Session 切分算子

⚡闪卡盲测➔

使用 np.lexsort 对多键(User + Timestamp)乱序日志排好序后一步差分 + cumsum 完成 Session ID 标注并按原顺序还原。

⏱️ 时间复杂度: O(N log N)
💾 空间复杂度: O(N)
🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
import numpy as np
def assign_session_ids(user_ids: np.ndarray, timestamps: np.ndarray, gap_threshold: float) -> np.ndarray:
n = len(user_ids)
if n == 0:
return
order = np.lexsort((timestamps, user_ids))
u_sorted = user_ids[order]
t_sorted = timestamps[order]
is_new = np.zeros(n, dtype=np.int64)
is_new[0] = 1
if n > 1:
user_switch = u_sorted[1:] != u_sorted[:-1]
time_gap = (t_sorted[1:] - t_sorted[:-1]) > gap_threshold
is_new[1:] = (user_switch | time_gap).astype(np.int64)
sess_sorted =
out = np.empty(n, dtype=np.int64)
out[order] = sess_sorted
return out
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: 为什么构建点击流/推荐序列特征时必须先做严格 Session 切分?
Q2: 如果日志高达十亿行放不下内存如何迁移该算子?
下一题: K-Means++ D² 采样初始化(RFM 客群聚类与 Vector Quantization) →
💡

实战一句话记忆口诀

lexsort 次键在前主键在后,差分或切换标记,cumsum 定 Session

📐 核心数学公式与机理推导

$$\text{new\_session}_i = \mathbb{I}\left(u_i \neq u_{i-1} \lor (t_i - t_{i-1}) > \tau_{\text{gap}}\right)$$
SQL 中经典的 SUM(CASE WHEN ts - LAG(ts) > 1800 THEN 1 ELSE 0 END) OVER (PARTITION BY user ORDER BY ts) 切分,对应 NumPy 中的混合键排序 lexsort((ts, user))、错位布尔比对以及一次性前置差分累加 cumsum,最后利用逆置换 out[order] = ... 映射回原始日志行。

🔄 张量维度与形状流转说明

user_ids: (E,), timestamps: (E,) -> lexsort -> session_ids: (E,)

🛡️ 数值稳定性自检与边界要点

  • 注意 np.lexsort((secondary, primary)) 参数中主键在最后,次键在前面
  • 输出必须按 inverse permutation 还原到调用方原始行序,否则后续 join 会错位
  • 处理同一时间戳连续并发事件的稳定排序边界

💻 完整参考代码实现

import numpy as np

def assign_session_ids(user_ids: np.ndarray, timestamps: np.ndarray, gap_threshold: float) -> np.ndarray:
    n = len(user_ids)
    if n == 0:
        return np.array([], dtype=np.int64)
    order = np.lexsort((timestamps, user_ids))
    u_sorted = user_ids[order]
    t_sorted = timestamps[order]
    is_new = np.zeros(n, dtype=np.int64)
    is_new[0] = 1
    if n > 1:
        user_switch = u_sorted[1:] != u_sorted[:-1]
        time_gap = (t_sorted[1:] - t_sorted[:-1]) > gap_threshold
        is_new[1:] = (user_switch | time_gap).astype(np.int64)
    sess_sorted = np.cumsum(is_new) - 1
    out = np.empty(n, dtype=np.int64)
    out[order] = sess_sorted
    return out

🧪 本地测试与正确性断言

可直接复制到本地 Python / Jupyter 验证:

u = np.array([2, 1, 1, 1, 2])
t = np.array([50.0, 10.0, 20.0, 60.0, 10.0])
sid = assign_session_ids(u, t, 30.0)
assert sid[1] == sid[2] and sid[2] != sid[3] and sid[4] != sid[0]
assert len(np.unique(sid)) == 4
print('O4 PASS')

🎯 核心工程追问与标准应答

Q1:为什么构建点击流/推荐序列特征时必须先做严格 Session 切分?
离线日志常因移动端离线批量上报导致乱序;不先用阈值重建 Session 边界会把昨天深夜的曝光与今天早上的点击错认为连续意图序列。
Q2:如果日志高达十亿行放不下内存如何迁移该算子?
只需先按 user_id Hash Sharding 分区落盘或交给 Spark/Flink KeyedStream,各分片内部依然执行完全等价的排序与时间差累积逻辑。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: CUPED 试验方差缩减与全局协方差最优系数估计返回 Part O 与全部 105 题下一题: K-Means++ D² 采样初始化(RFM 客群聚类与 Vector Quantization) →