2023.05.24-暑期实习-第二题-海量日志抑制

TaZi SU @ 9 months ago

思路分析

本题要求设计一种算法机制来抑制重复日志，满足以下两个条件：

相同日志的抑制：如果在 10 毫秒内出现相同的日志，则只保留第一个。
相似日志的抑制：如果在 100 毫秒内出现 10 条相似的日志（去除数字后字符相同），则只保留前 9 条。

可以使用两种方法：

暴力双重循环：
- 遍历每个日志时，从前面已读取的有效日志中检查：
  - 10 毫秒内的相同日志数量。
  - 100 毫秒内的相似日志数量。
- 若满足抑制条件，则将日志标记为抑制日志。
- 时间复杂度为 O(n^2)，在最大数据量下可能存在性能问题。
滑动窗口 + 哈希表：
- 采用两个滑动窗口分别记录 10 毫秒和 100 毫秒内的日志信息。
- 使用两个哈希表分别记录 10 毫秒内相同日志的次数，以及 100 毫秒内相似日志的次数。
- 每次读入日志时，更新滑动窗口并维护哈希表。
- 根据哈希表的记录判断日志是否需要抑制。
- 时间复杂度为 O(n)，更适合处理大规模数据。

算法流程

步骤1：读取输入的日志数据。

遍历每一条日志，解析出时间戳和日志内容。
使用辅助函数 remove_digits 去除日志中的数字，以判断相似日志。

步骤2：维护滑动窗口和哈希表。

使用两个滑动窗口：
- 一个窗口记录 10 毫秒内的日志数量，以判断相同日志数量。
- 一个窗口记录 100 毫秒内的日志数量，以判断相似日志数量。
每次读取日志时，根据时间差更新滑动窗口，移除不在窗口范围内的日志，并更新哈希表。

步骤3：判断抑制条件。

若当前日志在 10 毫秒内有相同日志，或 100 毫秒内有 9 条相似日志，则标记为抑制日志。
否则，更新哈希表，将日志加入有效日志集合。

时间复杂度

该方法时间复杂度为 O(n)，其中 n 是日志条数，因为每个日志的判断和窗口更新操作都是常数级别。适合处理大规模数据。

代码实现

Python代码（暴力双重循环）

from collections import defaultdict

# 去除字符串中的数字，判断相似性
def remove_digits(s):
    return ''.join([c for c in s if not c.isdigit()])

n = int(input())
logs = []
suppress_logs = []

# 读取每条日志
for _ in range(n):
    s = input()
    time, content = s.split(':')
    time = int(time)
    content_no_digits = remove_digits(content)
    
    same_count = 0
    similar_count = 0
    
    # 检查是否存在10ms内相同日志，100ms内相似日志
    for log_time, log_content, log_content_no_digits in logs:
        if time - log_time < 10 and log_content == content:
            same_count += 1
        if time - log_time < 100 and log_content_no_digits == content_no_digits:
            similar_count += 1

    # 若满足抑制条件，添加至抑制日志列表
    if same_count == 0 and similar_count < 9:
        logs.append((time, content, content_no_digits))
    else:
        suppress_logs.append(s)

# 输出抑制日志
if suppress_logs:
    print("\n".join(suppress_logs))
else:
    print("None")

Java & C++ 代码

限于篇幅问题，这里只给出提交记录链接

C++ - 双重暴力解法

Java - 双重暴力解法

Python代码（滑动窗口 + 哈希表优化）

from collections import defaultdict

# 从字符串中去除数字，用于判断相似性
def remove_digits(s):
    return ''.join([c for c in s if not c.isdigit()])

n = int(input())
logs = []
suppress_logs = []

# 哈希表记录10ms和100ms内日志出现次数
mp_10 = defaultdict(int)
mp_100 = defaultdict(int)

# 滑动窗口的起点
start_10 = 0
start_100 = 0

# 读取每条日志
for _ in range(n):
    raw = input()
    time, content = raw.split(':')
    time = int(time)
    content_no_digits = remove_digits(content)
    
    # 移除10ms和100ms窗口之外的日志
    while start_10 < len(logs) and time - logs[start_10][0] >= 10:
        mp_10[logs[start_10][1]] -= 1
        start_10 += 1
    while start_100 < len(logs) and time - logs[start_100][0] >= 100:
        mp_100[logs[start_100][2]] -= 1
        start_100 += 1

    # 判断是否抑制
    if mp_10[content] >= 1 or mp_100[content_no_digits] >= 9:
        suppress_logs.append(raw)
        continue

    # 更新哈希表及窗口日志
    mp_10[content] += 1
    mp_100[content_no_digits] += 1
    logs.append((time, content, content_no_digits))

# 输出抑制日志
print("\n".join(suppress_logs))

代码注释说明

remove_digits 函数：该函数用于去除字符串中的数字，以便判断相似日志。只保留字母和符号的顺序。
暴力双重循环：遍历每一条日志时，向前检查是否满足抑制条件。
滑动窗口+哈希表：mp_10 和 mp_100 分别记录 10ms 和 100ms 窗口内的相同和相似日志次数。每次更新窗口时移除超出时间范围的日志记录。
输出结果：最终输出被判定为抑制的日志。

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

模拟

# Submissions

230

Accepted

Uploaded By

TaZi

1 solutions

思路分析

算法流程

时间复杂度

代码实现

Python代码（暴力双重循环）

Java & C++ 代码

Python代码（滑动窗口 + 哈希表优化）

代码注释说明

Information

Status

Development

Support