机器翻译

题意

翻译软件的内存按先进先出规则替换，统计读取文章时需要访问外存词典的次数。

思路

集合 memory 用于 $O(1)$ 判断单词是否已缓存，双端队列 order 记录进入先后。未命中时计数；内存满则从队首弹出最早进入的单词，再将新词加入队尾和集合。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from collections import deque

capacity, word_count = map(int, input().split())
words = map(int, input().split())
memory = set()
order = deque()
lookups = 0

for word in words:
    if word in memory:
        continue
    lookups += 1
    if len(order) == capacity:
        memory.remove(order.popleft())
    order.append(word)
    memory.add(word)

print(lookups)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <iostream>
using namespace std;
#define F(i, s, t) for (int i = s; i <= t; ++i)
#define fenc cout << "==========\n"
#define log(a) cout << #a " = " << a << endl
#define maxn 1005
#define maxm 105
int n, m, wds[maxn], num, dicw[maxn], nowf = 1; //n words,m cidian
void init()
{
    cin >> m >> n;
    F(i, 1, n)
    cin >> wds[i];
}

void deal()
{
    F(i, 1, n)
    {
        F(j, 1, m)
        {
            if (dicw[j] == wds[i])
            {
                break;
            }                      //如果找到，直接跳过
            else if (dicw[j] == -1) //如果找到空白，填充
            {
                num++;
                dicw[j] = wds[i];
                // log(j);
                // log(dicw[j]);
                break;
            }
            else if(j==m)
            {
                if (nowf > m)
                    nowf = 1;
                dicw[nowf] = wds[i];
                // log(nowf);
                nowf++;
                // log(dicw[nowf]);
                num++;
            }
        }
    }
}

int main()
{
    for(int i=1;i<=100;++i){
        dicw[i] = -1;
    }
    init();
    deal();
    cout << num << endl;
    return 0;
}

复杂度

平均时间复杂度为 $O(n)$ ，空间复杂度为 $O(M)$ 。

总结

FIFO 缓存模拟通常需要“顺序容器 + 成员集合”两份状态。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结