JML(Java Modeling Language) 是用于对 Java程序进行规格化设计的一种表示语言。其结合了Effiel的契约式设计与Larch的基于模型的验证方法。OpenJML是一个用于Java的程序验证工具，它允许检查用Java建模语言注释的程序规范。支持的SMT Solver包括Z3、 CVC4与Yices等。第一次作业不怎么需要考虑时间复杂度。
isCircle、queryBlockSum由直接BFS得到，时间复杂度O(|V|+|E|)。queryNameRank由枚举所有用户名获得排名，时间复杂度O(|V|)，这里指出可以使用平衡树O(log|V|)或字典树加速添加和查询。OCavg = Average opearation complexity（平均操作复杂度）
OCmax = Maximum operation complexity（最大操作复杂度）
WMC = Weighted method complexity（加权方法复杂度）
CogC = Cognitive complexity（认知复杂度）
ev(G) = Essential cyclomatic complexity（基本圈复杂度）
iv(G) = Design complexity（设计复杂度）
v(G) = cyclonmatic complexity（圈复杂度）
代码统计
| Source File | Total Lines | Source Code Lines | Source Code Lines[%] | Comment Lines | Comment Lines[%] | Blank Lines | Blank Lines[%] |
|---|---|---|---|---|---|---|---|
| MyEqualPersonIdException.java | 24 | 19 | 79% | 0 | 0 | 5 | 21% |
| MyEqualRelationException.java | 30 | 25 | 83% | 0 | 0 | 5 | 17% |
| MyNetwork.java | 149 | 133 | 78% | 0 | 0 | 16 | 11% |
| MyPerson.java | 63 | 49 | 78% | 0 | 0 | 14 | 22% |
| MyPersonIdNotFoundException.java | 24 | 19 | 79% | 0 | 0 | 5 | 21% |
| MyRelationNotFoundException.java | 31 | 26 | 83% | 0 | 0 | 5 | 16% |
| Total | 722 | 483 | 67% | 136 | 19% | 103 | 14 |
类复杂度
| class | OCavg | OCmax | WMC |
|---|---|---|---|
| com.oocourse.spec1.model.MyNetwork | 2.42 | 4.0 | 29.0 |
| com.oocourse.spec1.model.MyEqualRelationException | 1.5 | 2.0 | 3.0 |
| com.oocourse.spec1.model.MyRelationNotFoundException | 1.5 | 2.0 | 3.0 |
| com.oocourse.spec1.model.MyEqualPersonIdException | 1.0 | 1.0 | 2.0 |
| com.oocourse.spec1.model.MyPerson | 1.0 | 1.0 | 10.0 |
| com.oocourse.spec1.model.MyPersonIdNotFoundException | 1.0 | 1.0 | 2.0 |
| ... | ... | ... | ... |
| Total | 76.0 | ||
| Average | 1.69 | 2.17 | 6.33 |
方法复杂度
| method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| com.oocourse.spec1.model.MyNetwork.queryBlockSum() | 6.0 | 1.0 | 4.0 | 4.0 |
| com.oocourse.spec1.model.MyNetwork.getBlock(Person) | 4.0 | 1.0 | 3.0 | 3.0 |
| com.oocourse.spec1.model.MyNetwork.addRelation(int,int,int) | 3.0 | 4.0 | 1.0 | 4.0 |
| ... | ... | ... | ... | ... |
| Total | 49.0 | 57.0 | 73.0 | 86.0 |
| Average | 1.09 | 1.27 | 1.62 | 1.91 |
通过复杂度分析，本次代码综合复杂度不高。
本次作业暂无BUG。
观察互测屋的代码发现有的同学将部分操作完全按JML规格的代码在写，时间复杂度极高，遂通过提交大数据（即大量的ap、qbs）hack了1人。
本次作业翻车，架构不予置评。
Person)时，没有同时维护年龄和与年龄的平方和。Group)人数上限1111。完成作业过于草率，匆匆写就代码，没能认真阅读与思考。
写完代码后便不闻不问，没有加以检查，错过找出错误的机会。
相关代码的分析评测工作不足，也致使本次作业的不理想。
类图中省略了异常类。
在算法上进行了改进。
getAgeMean、getAgeVar可以维护用户集合的年龄和与年龄平方和，再通过公式\(ageMean=\frac{ageSum}{n},ageVar=\frac{ageSqrSum-2\times ageSum\times ageMean+ageMean^2}{n}\)以时间复杂度O(1)计算得到。getValueSum可以通过对连边大于或小于O(√|V|)的点分别讨论记录，则每次询问时间复杂度稳定不超过O(√|V|)。addRelation使用并查集维护连通块，采取路径压缩与按秩合并，时间复杂度O(log*|V|)。
相关定义：log*n叫做Iterated logarithm，\(log^* n:=\begin{cases}0 &n\le1 \\ 1+log^*(logn) &n\gt1\end{cases}\)，优于O(logn)，略次于O(1)。附表如下。
| n | lg*n |
|---|---|
| (-∞,1] | 0 |
| (1,2] | 1 |
| (2,4] | 2 |
| (4,16] | 3 |
| (16,65536] | 4 |
| (65536,2^65536] | 5 |
queryBlockSum可在添加用户或合并时维护，询问时间复杂度O(1)。
sendIndirectMessage在询问最短路时使用了Dijkstra算法，时间复杂度O(|E|log|V|)，为了加速对询问过的点的单源最短路数据进行缓存，在当前连通块内有加边或者连通块被合并则放弃该连通块的缓存。
代码统计
| Source File | Total Lines | Source Code Lines | Source Code Lines[%] | Comment Lines | Comment Lines[%] | Blank Lines | Blank Lines[%] |
|---|---|---|---|---|---|---|---|
| MyEmojiIdNotFoundException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyEmojiMessage.java | 25 | 19 | 76% | 0 | 0 | 6 | 24% |
| MyEqualEmojiIdException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyEqualGroupIdException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyEqualMessageIdException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyEqualPersonIdException.java | 24 | 19 | 79% | 0 | 0 | 5 | 21% |
| MyEqualRelationException.java | 30 | 25 | 83% | 0 | 0 | 5 | 17% |
| MyGroup.java | 90 | 75 | 83% | 0 | 0 | 15 | 17% |
| MyGroupIdNotFoundException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyMessage.java | 68 | 56 | 82% | 0 | 0 | 12 | 18% |
| MyMessageIdNotFoundException.java | 25 | 20 | 80% | 0 | 0 | 5 | 20% |
| MyNetwork.java | 465 | 421 | 91% | 0 | 0 | 44 | 9% |
| MyNoticeMessage.java | 25 | 19 | 76% | 0 | 0 | 6 | 24% |
| MyPerson.java | 107 | 86 | 80% | 0 | 0 | 21 | 20% |
| MyPersonIdNotFoundException.java | 24 | 19 | 79% | 0 | 0 | 5 | 21% |
| MyRedEnvelopeMessage.java | 25 | 19 | 76% | 0 | 0 | 6 | 24% |
| MyRelationNotFoundException.java | 31 | 26 | 84% | 0 | 0 | 5 | 16% |
| Pair.java | 28 | 22 | 79% | 0 | 0 | 6 | 21% |
| Total: | 2576 | 1746 | 68% | 527 | 20% | 303 | 12% |
类复杂度
| class | OCavg | OCmax | WMC |
|---|---|---|---|
| com.oocourse.spec3.model.MyNetwork | 2.37 | 7.0 | 90.0 |
| com.oocourse.spec3.model.MyGroup | 1.55 | 4.0 | 17.0 |
| com.oocourse.spec3.model.MyEqualRelationException | 1.5 | 2.0 | 3.0 |
| com.oocourse.spec3.model.MyRelationNotFoundException | 1.5 | 2.0 | 3.0 |
| com.oocourse.spec3.model.MyEmojiIdNotFoundException | 1.0 | 1.0 | 2.0 |
| Total | 257.0 | ||
| Average | 1.84 | 3.0 | 8.57 |
方法复杂度
| method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| com.oocourse.spec3.model.MyNetwork.dealMessage(Message) | 8.0 | 1.0 | 7.0 | 7.0 |
| com.oocourse.spec3.model.MyGroup.getValueSum() | 6.0 | 1.0 | 4.0 | 4.0 |
| com.oocourse.spec3.model.MyNetwork.dijkstra(int) | 6.0 | 3.0 | 3.0 | 4.0 |
| com.oocourse.spec3.model.MyNetwork.getMinDist(int,int) | 5.0 | 3.0 | 6.0 | 6.0 |
| com.oocourse.spec3.model.MyNetwork.sendMessage(int) | 5.0 | 4.0 | 5.0 | 6.0 |
| ... | ... | ... | ... | ... |
| Total | 242.0 | 203.0 | 289.0 | 325.0 |
| Average | 1.73 | 1.45 | 2.06 | 2.32 |
通过复杂度分析，Network不可避免地包含了许多方法，但本次代码综合复杂度不高。
本次作业暂无BUG。
提交了一份大数据但是没有hack到任何人，最后互测屋内没有人hack成功。
在第十一次作业的讨论区有一个关于用迭代器和removeIf性能的问题。从直觉上感觉如此巨大的差距有点不思议。诚然具体表现与所使用设备、操作系统、JDK版本与实现、JVM实现等多种因素相关。这里提供一份简陋的测试代码，可在预热后多次测量二者表现。在本机上测试，二者几乎没有性能差距。
package main;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.results.format.ResultFormatType;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import java.util.HashMap;
import java.util.Iterator;
import java.util.concurrent.TimeUnit;
@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 3)
@Measurement(iterations = 10, time = 5, timeUnit = TimeUnit.SECONDS)
@Threads(16)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
public class LambdaTest {
public static HashMap<Integer, Integer> h;
public static int limit;
public static final int N = 5000000;
@Setup(Level.Trial)
public void setupOnTrail() {
limit = -1;
h = new HashMap<Integer, Integer>(N);
for (int i = 0; i < N; ++i)
h.put(i, i);
}
@Benchmark
public void testLambda() {
h.values().removeIf(heat -> heat < limit);
}
@Benchmark
public void testNonLambda() {
for (Iterator<Integer> i = h.values().iterator(); i.hasNext(); )
if (i.next() < limit)
i.remove();
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(LambdaTest.class.getSimpleName())
.result("./jmh_result")
.forks(2)
.build();
new Runner(opt).run();
}
}
本次作业中有10个异常，其功能重合度比较高。于是我思索了一番如何提高代码复用率，而不是复制。
首先Java（以及C#等语言）不支持多继承，即使是Java8开始也只是支持了接口的默认方法。多继承会令继承关系不是树状。多继承带来的便利大约是不如其带来的混乱的。多继承会造成歧义或二义性，比如我们用“蝙蝠“多继承了”哺乳动物“与”飞行动物“，那么“蝙蝠”进食是使用”哺乳动物的嘴”还是“飞行动物的嘴”，“蝙蝠”消化是使用“哺乳动物的胃”还是“飞行动物的胃”？此外，多继承也不能解决这里的需求，以C++为例，多继承后的静态成员并不是属于子类的，而是和父类共用的，那么记录该种异常抛出的次数就不能直接实现了。
面向对象的两种主要派别——Class-based与prototype-based。Class-based的误区在于不假思索地引入继承，并总是过于看重了继承。C++、Java都选择了Class-based。而prototype-based派认为面向对象就是实现了一组特定协议（或者称之为接口）的对象（也就是不存在类这种说法），所以Java与C++还是引入了接口。Class-based的问题还包括继承带来的强耦合与“鼓吹继承”给程序设计带来的思想包袱。而prototype-based只需要想办法支持这个协议就完了。至于怎么做，可以自己从头写，也可以从第三方转发相关调用，也就是继承只是一个语法糖而已。
那么说了这么多，Java因为种种限制，我只能想到类似工厂模式（为什么说类似，因为实际上有区别），用额外的类去帮助记录，因为通过反射获取类的名称与记录时用到了HashMap，这么做还可能有轻微的性能损失。
import java.util.AbstractMap;
import java.util.HashMap;
public class ExceptionRecorder {
private static final HashMap<String, AbstractMap.SimpleEntry<
Integer, HashMap<Integer, Integer>>> table = new HashMap<>();
private final Exception exception;
private final int[] id;
public ExceptionRecorder(Exception e, int... ids) {
exception = e;
id = (ids.length == 2 && ids[0] > ids[1]) ? new int[]{ids[1], ids[0]} : ids;
String key = exception.getClass().getSimpleName();
AbstractMap.SimpleEntry<Integer, HashMap<Integer, Integer>> entry =
table.getOrDefault(key, new AbstractMap.SimpleEntry<>(0, new HashMap<>()));
HashMap<Integer, Integer> little_book = entry.getValue();
little_book.put(id[0], little_book.getOrDefault(id[0], 0) + 1);
if (id.length == 2 && id[1] != id[0])
little_book.put(id[1], little_book.getOrDefault(id[1], 0) + 1);
table.put(key, new AbstractMap.SimpleEntry<>(entry.getKey() + 1, little_book));
}
public void print(String ename) {
AbstractMap.SimpleEntry<Integer, HashMap<Integer, Integer>> entry =
table.getOrDefault(exception.getClass().getSimpleName(),
new AbstractMap.SimpleEntry<>(0, new HashMap<>()));
System.out.println(
String.format("%s-%d, %d-%d%s",
ename,
entry.getKey(),
id[0],
entry.getValue().getOrDefault(id[0], 0),
id.length == 1 ? "" :
String.format(", %d-%d",
id[1],
entry.getValue().getOrDefault(id[1], 0)))
);
}
}
例子，传入参数为一个id。
package com.oocourse.spec3.model;
import com.oocourse.spec3.exceptions.EmojiIdNotFoundException;
public class MyEmojiIdNotFoundException extends EmojiIdNotFoundException {
ExceptionRecorder er;
public MyEmojiIdNotFoundException(int id) {
er = new ExceptionRecorder(this, id);
}
@Override
public void print() {
er.print("einf");
}
}
例子，传入参数为两个id。
import com.oocourse.spec3.exceptions.RelationNotFoundException;
public class MyRelationNotFoundException extends RelationNotFoundException {
private ExceptionRecorder er;
public MyRelationNotFoundException(int id1, int id2) {
er = new ExceptionRecorder(this, id1, id2);
}
@Override
public void print() {
er.print("rnf");
}
}
然而实际上重复写若干遍这种事很适合宏做，而Java并不支持（当然，可以用cpp这个来做C的预处理）。
于是我又用C++17写了一种。这里使用了一种类似装饰模式的思路（为什么说类似，因为实际上有区别），用一个装饰模板包装了原来的抽象类。
template <class T, const char *S>
class MyExceptionDecorator : public T
{
private:
function<void()> write;
static inline int count;
static inline unordered_map<int, int> little_book;
public:
MyExceptionDecorator(int id)
{
write = [&]()
{ cout << S << "-" << count << ", " << id << "-" << little_book[id] << endl; };
++count;
++little_book[id];
}
MyExceptionDecorator(int id1, int id2)
{
if (id1 > id2)
swap(id1, id2);
write = [&]()
{
cout << S << "-" << count << ", " << id1 << "-" << little_book[id1] << ", " << id2 << "-" << little_book[id2] << endl;
};
++count;
++little_book[id1];
if (id1 != id2)
++little_book[id2];
}
void print()
{
write();
}
};
被继承的是抽象函数，这里的代码都假设引入了头文件和using namespace std。
class EmojiNotFoundException : public exception
{
public:
virtual void print() = 0;
};
class RelationNotFoundException : public exception
{
public:
virtual void print() = 0;
};
例子，传入参数为一个id。
const char einf[] = "einf";
using MyEmojiNotFoundException = MyExceptionDecorator<EmojiNotFoundException, einf>;
例子，传入参数为两个id。
const char rnf[] = "rnf";
using MyRelationNotFoundException = MyExceptionDecorator<RelationNotFoundException, rnf>;
可见这样在每个异常类上写的代码更少了。而如果异常发生时的行为进行了变动，相比复制了10遍的方案这个的改动会更加少，遗漏等问题也会减少。
此单元以一种全新的工具JML，将一种程序契约化的理念带给学生，提供了一种新的规格的工程化思路。并且通过几代助教的努力，将课程体验带来了不小的提升。
对于我个人而言，这次课程期间，由于心理与生理上的一些原因，同时加之马虎大意，造成了严重的错误。这里我必须总结一点经验。其一，精神疾病除了有生物学因素与心理因素还与社会因素有关，焦虑症、强迫症、恐惧症等皆为精神疾病范畴。同时，“防御机制”指出，人会拒绝相信自己不愿相信的。其二，人的社会性说明了人与群体有相互作用，离群某种程度上与死亡无异。其三，情绪管理是人的一种能力，无论如何情绪本身不是问题，情绪只是一种解读感受，理性决策还是要靠自我。我觉得越早能参悟解决这些问题，就能越早地投入到解决实际的课程问题上去。接下来说点关于本次课程，总的来说会比之前两单元的内容轻松一点，内容上也是一个社交网络搭配运用几种常见的算法。安排上让学生能读懂规格，组合一些算法，如果有心挖掘还是能搞出不少东西学一学的。
原文：https://www.cnblogs.com/buaa-shy/p/14829244.html