时间戳

首页 > 解决方案 > 优先队列缓存问题（Java/Python）

python - 优先队列缓存问题（Java/Python）

问题描述

我在在线评估中遇到了这个问题，无法找到最佳解决方案。我在这篇文章的底部写了我尝试过的东西。以下是问题的摘要：

缓存系统使用优先级来决定哪些内存项从主内存移动到缓存。您将获得一个格式为 < 访问时间 > < 项目 ID > 的输入数组。

案例 1 输入数组：callLogs = [[1,1], [2,1], [2,1], [4,2], [5,2], [6,2]]

项目从优先级 0 开始，最低优先级为 0。每访问一个项目，优先级增加 2（如果在同一秒内访问两次，优先级增加 4）。在没有访问项目的情况下每经过一秒，其优先级就会降低 1。如果项目的优先级 > 5，则将其添加到缓存中。如果优先级低于 <= 3，则将其从缓存中删除。

最后返回缓存中的项目

对于案例 1，应该返回 2，因为项目 2 的最后优先级为 6，而项目 1 的最后优先级为 2。

时间 项目 1 访问 优先 项目 2 访问 优先
0 0 0
1 1 2 0
2 2 6 0
3 5 0
4 4 1 2
5 3 1 4
6 2 1 6

我尝试了什么：我创建了一个哈希图，其中键作为项目 ID，值作为时间列表，并且每次循环，检查是否每次都访问了每个项目。但我正在寻找一种更有效的解决方案，并假设它应该使用优先级队列。我使用 Python 进行在线评估，但由于这是一个优先队列问题，Java 可能更适合它吗？

标签： pythonjavacachingpriority-queue

解决方案

有人向我解释了答案。创建哈希映射是一个很好的第一步，但没有必要在循环中单独执行每个时间步骤。如果一个项目在时间 [6, 7, 20, 50] 被访问，我们知道它最后不会在缓存中，因为在时间 50 它的优先级将为 2。

我们可以用这个公式计算当前的优先级

if oldTime == newTime:
  currentPriority += 2
else:
  currentPriority = max(oldPriority - (newTime - oldTime - 1), 0) + 2

循环遍历每个项目并执行此操作，并且还要检查模拟结束时间的优先级，而不仅仅是每个项目的最后一个时间步长

推荐阅读