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: 如果日志高达十亿行放不下内存如何迁移该算子?
💡
实战一句话记忆口诀
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 分钟攻破认知盲区!