Primary Practice h58
fileName 是一个投票的明细记录，里面逐行存放了
1
| 投票的时间（yyyy-MM-dd HH:mm:ss 格式） + \t + 投票的微信ID + \t + 候选人
|
存放按时间递增（但是可能出现同一秒出现若干条记录的情况）
现在需要完成投票统计的过程，具体要求如下：
- 1 个微信 ID 1 分钟内 最多投 1 票 多余的票数无效
- 1 个微信 ID 10 分钟内 最多只能投 5 票 多余的票无效
- 其中微信 ID 不固定，候选人姓名不固定
- 测试的时候要求 10 万行记录处理时间不超过 3 秒
很有趣的一道题，虽然最后的结果始终有 3%～5% 的误差（截止到 2021.5.6 晚 9:58，还是没有找到误差出现的地方）。
和之前分析的文件类似，每一行文本有相同的格式，此处我抽象为一个 Record 类。
假设已经有了 Record 类，根据要求，需要对每位投票者的投票操作进行分析，去除掉那些不符合要求的操作记录。所以投票者也应抽象为一 Voter 类。
0x00 Record
此 Record 类对应文件的一行，所以应有时间、投票者和候选人属性。但整体来看，每条记录可能有效也可能无效，所以再添加一有效性属性：
1
2
3
4
| private Date date;
private final String voterId;
private final String candidate;
private boolean valid;
|
构造方法只需要传入参数，初始化各个属性。难点在于时间 Date 类型的处理，需要引入 DateFormat 和 SimpleDateFormat 类。此时暂且将每一条记录都设为有效：
1
2
3
4
5
6
7
8
9
10
11
| public Record(String date, String voterId, String candidate) {
DateFormat fmt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
try {
this.date = fmt.parse(date);
} catch (Exception e) {
e.printStackTrace();
}
this.voterId = voterId;
this.candidate = candidate;
valid = true;
}
|
定义各种 getter 和 setter：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public Date getDate() {
return date;
}
public String getVoterId() {
return voterId;
}
public String getCandidate() {
return candidate;
}
public boolean isValid() {
return valid;
}
public void setInvalid() {
valid = false;
}
|
最后，由于后续分析记录有效性的主要依据是时间，所以记录之间的先后顺序很重要。故 Record 类需要实现 Comparable 接口，重写 compareTo 方法：
1
2
3
4
5
6
7
| public class Record implements Comparable<Record> {
...
@Override
public int compareTo(Record o) {
return date.compareTo(o.date);
}
}
|
0x01 Voter
最主要的部分，本次实践的核心。
准备
作为一名投票者，区别身份的就是 ID，权利是一系列的投票记录：
1
2
3
| private final String id;
private final List<Record> records = new ArrayList<>();
private static final int MAX_RECORDS_IN_TEN_MINUTES = 5;
|
可能会联想到，Record 类的属性中，关于投票者为什么只存一个 String 而不是 Voter？
因为 Voter 会包含 Record，避免套娃，减少冗余，而且 Record 只是一个中间类，目的是根据 Record 的 voterId 将其添加到对应 voter 的 records 中，所以只需要一个 String。
构造方法只传入 ID：
1
2
3
| public Voter(String id) {
this.id = id;
}
|
文件中同一位投票者的投票记录不一定是连续的，所以投票记录需要逐条添加：
1
2
3
| public void addRecord(Record record) {
records.add(record);
}
|
另外，从整体来看，投票者有若干个，可构成集合，为便于后续获取投票者的集合，此处需实现可序列化接口，重写哈希码和相等方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Voter implements Serializable {
...
@Override
public int hashCode() {
return id.hashCode();
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Voter)) {
return false;
}
return ((Voter) o).id.equals(id);
}
}
|
去除无效记录
核心中的核心。
再次回顾一下，具体要求如下：
- 1 个微信 ID 1 分钟内 最多投 1 票 多余的票数无效
- 1 个微信 ID 10 分钟内 最多只能投 5 票 多余的票无效
为了判断，记录存储必须是按照时间递增的。1 分钟内最多 1 票，这个条件容易判断，只需要记录当前记录的时间，计算出 1 分钟之后的时间，再和下一条记录比对。但是要保证 10 分钟内最多 5 票，就有些困难。一方面，不能先只判断 1 分钟，因为两个条件互相影响，必须按时间顺序逐条判断；另一方面，判断 10 分钟不能按 0～10、10～20 判断，因为要保证任意 10 分钟内都最多只有 5 条，所以我利用 buffer 一次读入 5 条记录，这 5 条记录一定是满足 10 分钟条件的，在此基础上进行 1 分钟条件判断。
2021.5.7 更新
之前读入 5 条记录后只判断了 1 分钟条件，忘记判断 10 分钟条件。即这 5 条记录中可能从中间某一条记录开始，时间已经在第一条的 10 分钟以外，此时这条记录之前的记录一定为有效，且 buffer 应后移相应记录条数。
相应地，移动后应重新判断 1 分钟条件和 10 分钟条件，故定义了 isBufFinish 控制循环。
且，5 条记录内，1 分钟条件应优先于 10 分钟条件，所以加了 break。
修改前：
1
2
3
4
5
| 1007 ms cost!
wang 的误差为：5.09%
zhao 的误差为：4.23%
zhang 的误差为：3.36%
li 的误差为：4.29%
|
修改后：
1
2
3
4
5
| 901 ms cost!
wang 的误差为：4.65%
zhao 的误差为：2.7%
zhang 的误差为：4.57%
li 的误差为：4.05%
|
buffer 内部判断完成，需将 buffer 整体后移。若 buffer 之后的记录还在 10 分钟内，一定为无效。直到找到下一条 10 分钟之外的记录。每次 buffer 只移动一条记录，加 break。
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
58
59
60
61
62
| public void removeInvalidRecords() {
records.sort(Record::compareTo);
List<Record> buffer = new LinkedList<>();
int next = 0;
for (int i = 0; i < Math.min(MAX_RECORDS_IN_TEN_MINUTES, records.size()); i++) {
buffer.add(records.get(next++));
}
do {
int i, j;
Date curDate = buffer.get(0).getDate();
Date oneMinLater = new Date(curDate.getTime() + 60000);
Date tenMinLater = new Date(curDate.getTime() + 600000);
boolean isBufFinish = false;
while (!isBufFinish) {
for (i = 1; i < buffer.size(); i++) {
Date nextDate = buffer.get(i).getDate();
if (nextDate.compareTo(oneMinLater) < 0) {
buffer.get(i).setInvalid();
buffer.remove(i--);
if (next < records.size()) {
buffer.add(records.get(next++));
}
} else {
oneMinLater = new Date(nextDate.getTime() + 60000);
}
}
for (i = 1; i < buffer.size(); i++) {
Date nextDate = buffer.get(i).getDate();
if (nextDate.compareTo(tenMinLater) >= 0) {
tenMinLater = new Date(nextDate.getTime() + 600000);
for (j = 0; j < i; j++) {
buffer.remove(j);
buffer.add(records.get(next++));
}
isBufFinish = false;
break;
} else {
isBufFinish = true;
}
}
}
while (next < records.size()) {
Record nextRecord = records.get(next);
if (nextRecord.getDate().compareTo(tenMinLater) < 0) {
nextRecord.setInvalid();
next++;
} else {
buffer.remove(0);
buffer.add(nextRecord);
next++;
break;
}
}
} while (next < records.size());
}
|
至此，最核心的算法已完成。但 5.7 更新后仍有 4.7% 以下的误差，一定是有边界情况未考虑，待更新。
获取有效记录
用哈希映射存储，遍历有效记录。
1
2
3
4
5
6
7
8
9
10
11
12
| public Map<String, Integer> getCandidates() {
Map<String, Integer> candidates = new HashMap<>();
for (Record record : records) {
if (!record.isValid()) {
continue;
}
String candidate = record.getCandidate();
int count = candidates.getOrDefault(candidate, 0);
candidates.put(candidate, count + 1);
}
return candidates;
}
|
0x02 VoteRecord
顶层类，按行读取文件，每行存一 Record 实例：
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
| public List<Record> readLines(String filename) {
String line = "";
Reader reader = null;
List<Record> result = new ArrayList<>();
try {
reader = new FileReader(filename);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
if (reader == null) {
return null;
}
LineNumberReader lineReader = new LineNumberReader(reader);
try {
while (true) {
line = lineReader.readLine();
if (line == null) {
break;
}
String[] recordItems = line.split("\t");
String date = recordItems[0];
String voterId = recordItems[1];
String candidate = recordItems[2];
Record record = new Record(date, voterId, candidate);
result.add(record);
}
} catch (IOException e) {
e.printStackTrace();
}
return result;
}
|
主体 calcRecording，将读取到的 Record 列表存储，存所有 voter 的 id，存所有 voter，存所有 voterId 和 voter 的对应关系，存所有的候选人和其所得票数：
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
| public Map<String,Integer> calcRecording(String fileName){
List<Record> records = readLines(fileName);
Set<String> voterIds = new HashSet<>();
Set<Voter> voters = new HashSet<>();
Map<String, Voter> voterMap = new HashMap<>();
Map<String, Integer> candidates = new HashMap<>();
for (Record record : records) {
voterIds.add(record.getVoterId());
}
for (String voterId : voterIds) {
Voter voter = new Voter(voterId);
voters.add(voter);
voterMap.put(voterId, voter);
}
for (Record record : records) {
Voter voter = voterMap.get(record.getVoterId());
voter.addRecord(record);
}
for (Voter voter : voters) {
voter.removeInvalidRecords();
Map<String, Integer> oneCandidates = voter.getCandidates();
Set<Map.Entry<String, Integer>> oneCandidatesNameCount = oneCandidates.entrySet();
for (Map.Entry<String, Integer> entry : oneCandidatesNameCount) {
String candidate = entry.getKey();
int count = entry.getValue();
if (candidates.containsKey(candidate)) {
count += candidates.get(candidate);
}
candidates.put(candidate, count);
}
}
return candidates;
}
|
误差待消除
Source code