当前位置： 首页 > java >正文

【字节跳动】数据挖掘面试题0003：有一个文件，每一行是一个数字，如何用 MapReduce 进行排序和求每个用户每个页面停留时间

java 2025/7/3 16:36:42

MapReduce 是一种适合处理大规模数据的分布式计算框架，其核心思想是将计算任务分解为 Map（映射）和 Reduce（归约）两个阶段。
对文件中的数字进行排序，可以利用 MapReduce 的特性来实现。

要使用 MapReduce 对文件中的数字进行排序，需要实现一个 MapReduce 作业，将数字作为键处理，利用 Hadoop 的默认排序机制对键进行排序。
以下是实现步骤和示例代码：

文章大纲

    • 题目一：有一个文件，每一行是一个数字，如何用 MapReduce 进行排序
      • 实现思路
        • 具体实现步骤
        • 关键点说明
      • 示例代码
      • 执行命令
      • 代码说明
    • 题目二：求每个用户每个页面停留时间
      • **实现思路**
      • **示例代码**
        • 实现思路
      • **输出示例**
      • **关键说明**
      • **注意事项**

题目一：有一个文件，每一行是一个数字，如何用 MapReduce 进行排序

实现思路

  1. Mapper：将每行的数字转换为整数键，值可以设为空或占位符。
  2. Shuffle 阶段：MapReduce 框架自动对键进行排序，确保相同键或不同键按顺序发送到 Reduce 节点。
  3. Reducer：直接输出键（已排序），忽略值。
  4. 排序机制：Hadoop 默认会对 Mapper 输出的键进行排序，因此无需额外处理。
具体实现步骤
  1. Map 阶段
    • 输入：每行一个数字（如：10\n5\n8\n3）。
    • 处理：将每行数字转换为整数作为键，值设为1（或任意常量）。
    • 输出：<key=数字, value=1>。
  2. Shuffle 阶段
    • MapReduce 自动按键排序，确保所有键按升序发送到 Reduce 节点。
  3. Reduce 阶段
    • 输入：排序后的键值对（如：< 3,1>, <5,1>, <8,1>, <10,1>）。
    • 处理：直接输出键，忽略值。
    • 输出：排序后的数字（每行一个）。
关键点说明
  • 1.排序机制
    • MapReduce 默认按键的字典序排序。若处理整数，需确保 Map 输出的键为数值类型（而非字符串），否则会按字符串排序（如：10会排在5前面）。
  • 2.全排序 vs 分区排序
    • 全排序：若要全局有序，需确保所有数据进入同一个 Reduce 任务（设置numReduceTasks=1），但这会导致单点性能瓶颈。
    • 分区排序：若数据量极大，可通过自定义分区函数将数据分到多个 Reduce 任务，每个任务内部有序（如：键1-100到 Reduce1，101-200到 Reduce2）。
  • 3.优化技巧
    • 使用 Combiner 在 Map 端预聚合，减少网络传输。
    • 若数据分布不均，可使用二次排序或采样分区避免数据倾斜。

示例代码

下面是一个完整的 Python 实现，使用 Hadoop Streaming：

# mapper.py
import sysfor line in sys.stdin:line = line.strip()if line:  # 跳过空行try:num = int(line)print(f"{num}\t1")  # 输出格式: 数字<TAB>1except ValueError:continue  # 忽略非数字行

# reducer.py
import sysfor line in sys.stdin:line = line.strip()if line:try:num, _ = line.split('\t', 1)print(num)  # 直接输出数字except ValueError:continue  # 忽略格式错误的行

执行命令

假设输入文件为 numbers.txt，可以使用以下 Hadoop Streaming 命令执行排序：

hadoop jar $HADOOP_HOME/share/hadoop/tools/lib/hadoop-streaming-*.jar \
-input numbers.txt \
-output output \
-mapper "python3 mapper.py" \
-reducer "python3 reducer.py" \
-numReduceTasks 1  # 确保所有数据在一个 reducer 中排序

代码说明

  • Mapper：读取每一行，转换为整数作为键，值设为 1（占位符）。
  • Reducer：读取键值对，直接输出键（排序后的数字）。
  • 排序保证：Hadoop 会自动对 Mapper 输出的键进行排序，因此 Reducer 接收到的键已经是有序的。

这个实现利用了 Hadoop 的默认排序机制，确保最终输出的数字是有序的。如果输入文件非常大，可以增加 Reducer 数量，但需要额外处理分区以保证全局有序。

利用 MapReduce 的默认排序特性，通过简单的 Map 和 Reduce 函数即可实现数字排序。核心是将数字作为键，让框架自动完成排序工作，最终由 Reduce 输出有序结果。这种方式适用于 TB 级数据的分布式排序。

题目二：求每个用户每个页面停留时间

有一张网页访问日志表，记录了user_id，session_id，page_id，timestamp用户在每点击一个连接跳转，就会记录一个时间戳，并且page_id排序后与时间戳的排序一致，现要求每个用户的每个页面所停留的时间。
比如：
1 1 1 10:00 1 1 3 12:00

页面停留时间的计算方式： 用户在页面的停留时间 = 下一个页面的访问时间 - 当前页面的访问时间。

要计算每个用户在每个页面上的停留时间，需按用户和会话分组，对页面访问记录按时间排序，然后计算相邻页面之间的时间差。以下是实现思路和示例代码：

实现思路

    1. 数据预处理：按 user_id、session_id 分组，并按 timestamp 排序（确保页面访问顺序正确）。
    1. 计算停留时间：对每个用户的每个会话，用后一个页面的 timestamp 减去当前页面的 timestamp，得到停留时间。
    1. 处理边界情况：最后一个页面的停留时间可设为 0，或根据业务需求估算（如平均停留时间、页面退出率等）。

示例代码

要在 Hive 中计算每个用户在每个页面上的停留时间，可以使用窗口函数对日志数据进行排序并计算相邻记录的时间差。以下是具体的 Hive SQL 实现：

  • 适用于大规模日志数据的分析
实现思路

  • 数据准备：假设已有表 page_views，包含 user_id、session_id、page_id 和 timestamp 字段。

  • 时间转换：将 timestamp 转换为 Hive 可处理的时间格式（如 UNIX_TIMESTAMP）。

  • 窗口函数排序：按 user_id 和 session_id 分组，按时间排序。

  • 计算停留时间：使用 LEAD() 函数获取下一条记录的时间戳，计算差值。

    -- 使用窗口函数计算每个用户在每个页面的停留时间
WITH sorted_views AS (SELECT user_id,session_id,page_id,timestamp,-- 将时间戳转换为 UNIX 时间（秒）UNIX_TIMESTAMP(timestamp, 'HH:mm') AS ts_seconds,-- 获取同一用户和会话的下一条记录的时间戳LEAD(UNIX_TIMESTAMP(timestamp, 'HH:mm'), 1) OVER (PARTITION BY user_id, session_id ORDER BY UNIX_TIMESTAMP(timestamp, 'HH:mm')) AS next_ts_secondsFROM page_views
)
-- 计算停留时间（秒转分钟），最后一页的停留时间设为 0
SELECT user_id,session_id,page_id,timestamp,-- 计算时间差（分钟），最后一页默认为 0COALESCE(ROUND((next_ts_seconds - ts_seconds) / 60, 2), 0) AS time_spent_minutes
FROM sorted_views
ORDER BY user_id, session_id, ts_seconds;

假设使用 Python 和 Pandas 处理日志数据：

import pandas as pd# 示例数据（实际应从日志表读取）
data = [(1, 1, 1, '10:00'),(1, 1, 3, '12:00'),(1, 1, 2, '15:00'),(2, 1, 4, '09:30'),(2, 1, 5, '11:00')
]df = pd.DataFrame(data, columns=['user_id', 'session_id', 'page_id', 'timestamp'])# 将 timestamp 转换为 datetime 类型以便计算时间差
df['timestamp'] = pd.to_datetime(df['timestamp'], format='%H:%M')# 按 user_id、session_id 分组，并按 timestamp 排序
df_sorted = df.sort_values(['user_id', 'session_id', 'timestamp'])# 计算每个页面的停留时间（使用下一个时间戳减去当前时间戳）
df_sorted['time_spent'] = (df_sorted.groupby(['user_id', 'session_id'])['timestamp'].diff(-1)  # 下一行减去当前行.abs()  # 取绝对值（确保时间差为正）.dt.total_seconds() / 60  # 转换为分钟
)# 最后一个页面的停留时间设为 0（或根据业务需求处理）
df_sorted['time_spent'] = df_sorted['time_spent'].fillna(0)# 输出结果
print(df_sorted[['user_id', 'session_id', 'page_id', 'timestamp', 'time_spent']])

输出示例

在这里插入图片描述

关键说明

  1. 时间计算：

    • 使用 diff(-1) 计算当前行与下一行的时间差。
    • fillna(0) 处理最后一个页面（无后续记录）的停留时间。

  2. 数据排序：

    • 必须按 user_id、session_id 和 timestamp 排序，确保时间顺序正确。

  3. 边界处理：

    • 最后一个页面的停留时间可根据业务逻辑调整（如设置默认值、关联退出事件等）。

注意事项

  • 如果日志表数据量大，建议使用分布式计算框架（如 Spark）处理。
  • 确保 timestamp 格式统一，否则需先进行数据清洗。
  • 对于单页会话（只有一个页面访问记录），停留时间会被设为 0，需根据需求调整。
http://www.xdnf.cn/news/14761.html

相关文章：

  • 《P4145 上帝造题的七分钟 2 / 花神游历各国》
  • Google Maps 安装使用教程
  • 客服机器人知识库怎么搭？智能客服机器人3种方案深度对比（含零售落地案例）
  • 【Linux】U-boot常用命令总结
  • 从UI设计到数字孪生实战部署：构建智慧农业的智能灌溉系统
  • 数学建模_图论
  • 桥岛隧大型工程 3D 可视化监测平台
  • 分布式定时任务：xxl-job
  • 洛谷刷题6
  • 拐点的可导性的图像区别
  • AlpineLinux安装部署zabbix
  • 【分明集合】特征函数、关系与运算
  • SpringBoot计时一次请求耗时
  • 应急响应类题练习——玄机第四章 windows实战-emlog
  • [创业之路-458]：企业经营层 - 蓝海战略 - 重构价值曲线、整合产业要素、创造新需求
  • Leetcode力扣解题记录--第49题（map）
  • [Python] -基础篇8-Python中的注释与代码风格PEP8指南
  • mac重复文件清理，摄影师同款清理方案
  • poi设置word表格边框
  • 修改Spatial-MLLM项目，使其专注于无人机航拍视频的空间理解
  • Flink Savepoints 总结
  • 一文详解Modbus协议原理、技术细节及软件辅助调试
  • 【甲方安全建设】敏感数据检测工具 Earlybird 安装使用详细教程
  • PyTorch 中 nn.Linear() 参数详解与实战解析（gpt）
  • 直线模组精度等级是如何划分的？
  • Python 数据分析与机器学习入门 (五)：Matplotlib 数据可视化基础
  • LeetCode Hot100(图论)
  • STM32——DAP下载程序和程序调试
  • 深入理解Webpack的灵魂：Tapable插件架构解析
  • 对selenium进行浏览器和驱动进行配置Windows | Linux