OO Unit3 Summary

架构设计梳理：

HW9:

重点架构设计：

第一次作业整体上难度不大，但是需要对jml的实现细节考虑周全，对于一些开销较大的方法需要动态维护以降低时间复杂度，容器尽量使用HashMap等速度较快的。以下列出一些重点方法的实现。

iscircle:

采用朴素bfs加一个visited的map实现去重访问。

queryTripleSum :

采用动态维护，对于添加关系和删除关系，相当于增加或者删除了两人的公共好友数量的三元环。

queryBestAcquaintance:

加入时动态维护最大值，删除时如果删除了最大值重新遍历得到最大值。

getAgeavg/var

方差和平均数动态维护,注意方差的书写需要考虑整除带来的影响

1	return (agesquaresum - 2 * agesum * mean + n * mean * mean) / n;

bug分析和遇到的问题：

第一次测试和舍友对拍了许多测试点，公测功能没出现问题，性能卡了一个点，原因是queryTripleSum一开始采用一种将无向图根据度数转换为有向图的方法，复杂度为O($n\sqrt{n}$)，且在稠密图会退化为O($n^2$)。

互测：

互测重点从100人的完全图入手，大量询问queryTripleSum卡性能。对于功能测试使用测评机大量测试。

HW10:

重点架构设计：

query_shortest_path：

采用朴素bfs加一个visited的map实现去重访问。

query_best_contributor：

动态维护,同queryBestAcquaintance

received_articles：
arraylist顺序存，倒叙输出，实现按照时间顺序输出。

query_tag_value_sum：

对每个person在不同tag中的，情况缓存为一个map，索引为其ownerid 和 tagid的字符串拼接的hash，防止不同人中的相同tagid，键值为bool。在循环遍历相加时，使用缓存减少计算复杂度，在加入删除时置为true，计算过一次最新值后置为false，当修改两个人之间的关系（增加删除修改），将两人的map里所有元素（实际上共存tag，为了简化逻辑直接饱和覆盖）都置为true。

public int getValueSum() {
        if (persons.isEmpty()) {
            return 0;
        }
        int valuesum = 0;
        HashSet<Integer> personIds = new HashSet<>(persons.keySet());
        for (Person p : persons.values()) {
            if (!p.getfortagischange(ownerid,id)) {
                valuesum += valuesummap.get(p);
            }
            else {
                int singlevaluesum = 0;
                for (HashMap.Entry<Integer, Integer> entry : p.getValues().entrySet()) {
                    int otherId = entry.getKey();
                    if (personIds.contains(otherId)) {
                        singlevaluesum += entry.getValue();
                    }
                }
                valuesum += singlevaluesum;
                valuesummap.put(p,singlevaluesum);
                p.tagchange(ownerid,id,false);
            }
        }
        return valuesum;
    }

bug分析和遇到的问题：

第二次作业公测挂了两个点，原因是modifyRelation方法对于value减小到小于等于0之后删除关系时没有更新map，因而导致错误，增加两行后修复。

互测：

互测重点从100人的完全图入手，大量询问query_tag_value_sum卡性能。对于功能测试使用测评机大量测试。

HW11:

重点架构设计：

queryReceivedMessages：
arraylist顺序存，倒叙输出，实现按照时间顺序输出。

deleteColdEmoji：
采用堆维护EmojiHeatList，删除时间减少很多

private final PriorityQueue<Integer> emojiHeap = new PriorityQueue<>(
        Comparator.comparingInt(emojiHeatList::get));
...
...
...
while (!emojiHeap.isEmpty() && emojiHeatList.get(emojiHeap.peek()) < limit) {
            emojiHeatList.remove(emojiHeap.poll());
        }

注意红包均分时除数为零的情况和整除的正确计算方法

if (message instanceof RedEnvelopeMessageInterface) {
    if (tag.getSize() > 0) {
        RedEnvelopeMessageInterface redEnvelopeMessage =
            (RedEnvelopeMessageInterface) message;
        int money = redEnvelopeMessage.getMoney() / tag.getSize();
        person1.addMoney(-money * tag.getpersons().size());
        for (Person p : tag.getpersons().values()) {
            p.addMoney(money); 
        } 
    } 
}

queryReceivedArticles:

通过构造大量同一账号下的用户和文章，删除文章可能导致CTLE但是第二次作业并没有出现这样的强测点，同时发现由于转发消息的存在可能出现重复文章。

给出一种解决方案：

使用时间戳记录每个文章，封装一个含有id和time的article类，利用关于时间戳的双向链表维护文章顺序，removearticle更新有效时间戳，尝试获取文章时顺带删除已经移除的id，时间是无效的文章，类似于延迟删除。同一组测试样例时间从50s降至3s。

@Override
    public ArrayList<Integer> getReceivedArticles() {
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Article> del = new ArrayList<>();
        if (!articleHeap.isEmpty()) {
            for (Article a : this.articleHeap) {
                int aid = a.getId();
                if (articles.contains(aid) &&
                    (a.getTime() >= articletime.getOrDefault(aid,0))) {
                    result.add(aid);
                }
                else {
                    del.add(a);
                }
            }
        }
        for (Article a : del) {
            articleHeap.remove(a);
        }

        return result;
    }

    @Override
    public ArrayList<Integer> queryReceivedArticles() {
        int x = 0;
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Article> del = new ArrayList<>();
        if (!articleHeap.isEmpty()) {
            for (Article a : this.articleHeap) {
                int aid = a.getId();
                if (articles.contains(aid) &&
                    (a.getTime() >= articletime.getOrDefault(aid,0))) {
                    result.add(aid);
                    x++;
                }
                else {
                    del.add(a);
                }
                if (x == 5) {
                    break;
                }
            }
        }
        for (Article a : del) {
            articleHeap.remove(a);
        }

        return result;
    }

    public void deleteReceivedArticle(int articleId) {
        this.articles.remove(articleId);
        this.articletime.put(articleId, time);
    }

    public void receiveArticle(int articleId) {

        this.articles.add(articleId);
        this.articleHeap.addFirst(new Article(articleId, time));
        this.articletime.putIfAbsent(articleId, time);
        time++;
    }

bug分析和遇到的问题：

在强测中没有遇到bug，互测也成功满分。

互测：

互测主要测试message相关的操作

测试

对于测试，常见的测试有如下方面：

1. 单元测试（Unit Testing）

核心目标：验证代码中最小的可测试单元（如函数、类、方法）是否按预期工作。对应到这单元就是JUNIT测试。

2. 功能测试（Functional Testing）

核心目标：验证系统的功能是否符合需求规格（从用户视角测试完整流程）。
特点：
- 黑盒测试：不关注内部实现，只关注是否实现了jml的功能实现。
- 覆盖所有可能场景，尽可能涵盖jml规定的异常情况，观察功能实现是否正确。

3. 集成测试（Integration Testing）

核心目标：验证多个模块或服务协同工作时的交互是否正确，可设计不同方法之间的交互数据。
特点：
- 逐步集成：可能采用自顶向下或自底向上的策略。

4. 压力测试（Stress Testing）

核心目标：评估系统在极端负载下的表现（大数据量、边界条件），发现性能瓶颈。
特点：
- 关注指标：响应时间、吞吐量、资源占用率（CPU/内存）、错误率。

5. 回归测试（Regression Testing）

核心目标：确保代码修改（如修复 Bug、新增功能）不会破坏现有功能，可在每个新作业实现后测试前一单元功能是否仍然正确实现。
特点：
- 重复执行：针对已有功能的测试用例重新运行。
- 自动化优先：依赖自动化测试快速覆盖。

JUNIT:

规格的格式在某种意义上指明了测试的思路，规格的层次和不同分支可以看作测试时需要测试的不同情况，构造JUNIT测试时可以层层递进，依据jml的层次设计具体的测试，同时针对可能性较多的测试，采用参数化测试是一个不错的方法，能够更好地覆盖所有情况。对于异常的处理，依据jml书写不同情况的异常判断异常是否都被正确处理是十分必要的。

规格和实现：

jml规格只是规定了你应该实现的功能，对于具体的实现一般不作限制，因此在保证功能不改变的情况下，可以使用不同的数据结构实现效率的提升或者功能的优化，同时也要注意实现过程中是否无意识改变了功能或者不变式约束，以防造成错误。

大模型：

关于大模型使用，如果直接使用其生成所有代码，可能导致功能实现缺失、性能过于低效等问题，应当使用其填充结构，或者生成结构以达到生成清晰代码逻辑的作用；对于冗杂的jml，也可以使用大模型帮助梳理jml层次结构，帮助我们书写具体实现；对于JUNIT测试，大模型可根据jml的要求生成全面的简单测试样例，对于基础功能实现的测试十分方便；同时对于性能问题可以询问大模型有无更好的实现逻辑或者数据结构，帮助我们优化代码速度。

学习体会：

通过本单元的学习，我对规格化设计有了一个基本的认识，体会到了依据规格设计代码带来的便利和周密，同时为了检测实现的正确性，这单元我进行了大量的测试，这也帮助我对代码的测试有了更加深刻的认识，同时为了优化效率，我学习了几个新的数据结构和思想，对我编程能力的提升也有帮助。最后在本单元使用了大模型作为辅助，使我对大模型在未来学习工作中应当如何使用有了更加清晰的认识。

BUAA-OO-unit3

oo-系列：

OO Unit3 Summary

架构设计梳理：

HW9:

重点架构设计：

bug分析和遇到的问题：

互测：

HW10:

重点架构设计：

bug分析和遇到的问题：

互测：

HW11:

重点架构设计：

bug分析和遇到的问题：

互测：

测试

1. 单元测试（Unit Testing）

2. 功能测试（Functional Testing）

3. 集成测试（Integration Testing）

4. 压力测试（Stress Testing）

5. 回归测试（Regression Testing）

JUNIT:

规格和实现：

大模型：

学习体会：