OO Unit 3 Summary
The training goal of the third unit of OO is normalized program design.
In short, the course team first used JML (Java Modeling Language) instead of natural language to describe the requirements, and then I strictly followed the various conditions and side effects requirements of the specification, in the On this basis, optimize the algorithm and data structure level. How to implement a high-performance program that meets the specifications is the focus of this unit.
Architecture design
The training goal of this unit is to design programs according to the specifications. The course team gives the methods to be implemented in the form of interfaces and abstract classes, and uses JML for specification description. And our task is to create a new class to implement the interface or inherit the abstract class and complete the methods in it.
- For interfaces, use the implements keyword:
public class MyPerson implements Person - For abstract classes, use the extends keyword:
public class EqualRelation extends EqualRelationException
The Emoji class needs to implement the methods in the interface EmojiMessage given by the course group, and EmojiMessage inherits the Message interface, so the Emoji class needs to implement the methods in the Message interface. I made the Emoji class inherit the MyMessge class implemented by me, saving a lot of code.
public interface EmojiMessage extends Message // official course package public class MyMessage implements Message public class Emoji extends MyMessage implements EmojiMessage
I created an exception counter class Counter that counts the number of exceptions associated with a particular person. Define the static attribute counter in the exception class: private static final Counter counter = new Counter();, you can correctly store and get the every time you create a new exception object >Number of historical exceptions.
public class Counter {<!-- -->
private final HashMap<Integer, Integer> exceptionTimes;
public Counter() {<!-- -->
exceptionTimes = new HashMap<>();
}
public int getTimes(int id) {<!-- -->
if (exceptionTimes.computeIfPresent(id, (key, value) -> value + 1) == null) {<!-- -->
exceptionTimes. put(id, 1);
}
return exceptionTimes. get(id);
}
}
Since the classes that need to be implemented and the hierarchical relationship between them have been determined, there is not much room for development in the overall architecture, so our focus is on how to optimize the method accomplish. One of the keys is how to construct and maintain various information of the social network graph.
The following is an introduction to graph optimization ideas starting from the requirements of each job.
Hw9
In the Network class, JML gives the attribute Person[] people of the class, that is, the collection of people in the social network. Without thinking about the translation specification, we can use the container ArrayList to storage.
But in the actual implementation, I found that it is often necessary to find a specific person through the id of the person. When using ArrayList, it can only be searched by traversing and comparing id, and the time complexity is O(n). Therefore, I use HashMap to store person information. The key is id, and the value is Person object. You can directly find the corresponding Person object through id. Since the methods in the Network class operate generally based on the id of the Person, it can save a lot of time and is very concise.
private final HashMap<Integer, Person> people;
public boolean contains(int id) {<!-- -->
return people.containsKey(id);
}
public Person getPerson(int id) {<!-- -->
return people. getOrDefault(id, null);
}
The time complexity of both contains() and getPerson() methods is O(1).
and check set
Union check set is a tree data structure used to deal with the merging of disjoint sets. The union lookup maintains a collection family consisting of multiple disjoint collections, and each collection is identified by a representative element. Its basic operations are Merge and Find.
- look up
It is used to determine the set that an element belongs to. You can use the root node to determine whether two elements belong to the same set, that is, the connectivity between them. It is usually implemented in a recursive or iterative manner, and the time complexity is O(logn).
Path compression is used here, that is, during the search process, all nodes on the path are directly connected to the root node, thereby reducing the height of the tree.
public int find(int id) {<!-- -->
int root = id;
Stack<Integer> stack = new Stack<>();
while (root != parent. get(root)) {<!-- -->
stack. push(root);
root = parent. get(root);
}
while (!stack.isEmpty()) {<!-- -->
parent.put(stack.pop(), root); // path compression
}
return root;
}
- merge
Merges two disjoint sets into one set. Merge by rank refers to connecting the smaller height tree to the larger height tree, avoiding the excessive depth of the tree. A HashMap height is used here to store the height of each root node, and a height of 0 indicates that the node is a leaf node.
public void union(int id1, int id2) {<!-- -->
int root1 = find(id1);
int root2 = find(id2);
if (root1 == root2) {<!-- -->
return;
}
int height1 = height. get(root1);
int height2 = height. get(root2);
if (height1 < height2) {<!-- --> // merge by rank
parent. put(root1, root2);
height. remove(root1);
} else {<!-- -->
if (height1 == height2) {<!-- -->
height. put(root1, height1 + 1);
}
parent. put(root2, root1);
height. remove(root2);
}
}
After maintaining and querying each time a relationship is established, the isCircle() method for querying connectivity can be quickly resolved, and the number of connected blocks can be queried The queryBlockSum() method. It can be seen that Union Find is very elegant in solving the connectivity problem of the graph.
public boolean isCircle(int id1, int id2) {<!-- -->
return disjointSet.find(id1) == disjointSet.find(id2);
}
public int queryBlockSum() {<!-- -->
return disjointSet. getHeight(). size();
}
Triple Sum
TripleSum means that there are three people in the social network, they know each other two by two, and count the number of such three-person groups. A method of violent search is to traverse everyone’s friends, and then traverse all their friends. If the person knows the first person, the number of threesomes will be increased by one. However, the time complexity of such an implementation is O(n^3), which obviously does not meet the performance requirements.
So I adopted the method of dynamic maintenance TripleSum. In the addRelation() method, when a and b establish a relationship, traverse all friends of a, and if they know b, the number of threesomes will be increased by one. In this way, dynamic maintenance every time a relationship is established can reduce the time complexity to O(n).
HashMap<Integer, Integer> acq1 = getPerson(id1).getAcquaintances();
for (int id : acq1.keySet()) {<!-- -->
HashMap<Integer, Integer> acq = getPerson(id).getAcquaintances();
if (acq. containsKey(id2)) {<!-- -->
tripleSum++;
}
}
Hw10
The group function has been added in this assignment, similar to people, use HashMap to store group information, and you can quickly find the corresponding group through the group id: private final HashMap< Integer, Group> groups;
modifyRelation()
In this assignment, there is a demand for relationship changes in social networks, which involves changes in relationship intimacy and deletion, and deleting a relationship is extremely difficult to search and collect Deal with issues.
Therefore, I backup the information of each edge, adding it every time a relationship is established, and removing it when deleting a relationship. In this way, every time a relationship is deleted, it only needs to traverse all the edges in the backup, re-establish and search.
public void rebuild(int id1, int id2) {<!-- -->
height. clear();
for (int id : parent. keySet()) {<!-- -->
parent. put(id, id);
height. put(id, 0);
}
backup. remove(new Pair<>(id1, id2));
for (Pair<Integer, Integer> pair : backup) {<!-- -->
union(false, pair. getKey(), pair. getValue());
}
}
TripleSum also needs to be maintained after the relationship is deleted, just subtract one from the number of triples when traversing.
CoupleSum
CoupleSum means that there are two people in the social network who are best friends and count the number of such people. Since the relationship is constantly changing, it is complicated to dynamically maintain the information of the social network, and the traversal operation during maintenance cannot be avoided. Therefore, I adopted JML’s simple writing method to traverse each person, and if he and his best friend are best friends with each other, the number will be increased by one. The time complexity is O(n^2).
public int queryCoupleSum() {<!-- -->
int ans = 0;
for (int id : people. keySet()) {<!-- -->
Person person = getPerson(id);
if (person. getAcquaintances(). isEmpty()) {<!-- -->
continue;
}
int acq = person. getBestAcq();
if (getPerson(acq).getBestAcq() == id) {<!-- -->
ans + + ;
}
}
return ans/2;
}
Although CoupleSum is not dynamically maintained, everyone’s best friend information can still be dynamically maintained when the relationship changes, and the logic is clearer.
Best Acquaintance
In the Person class, I added an attribute bestAcq to store the id of the person’s best friend, which is convenient for the Network class to query CoupleSum.
- relationship improved
This applies to a newly formed relationship or increased intimacy in a relationship.
If the intimacy of the changed relationship is greater than the intimacy of the original best friend relationship, update the person’s best friend information - relationship sour
There are two possibilities: delete the relationship or decrease the intimacy of the relationship.
If the changed relationship is the person’s best friend relationship, then traverse all friends again, find the relationship with the highest intimacy, and update the best friend information. Maintenance is not needed if it is not the person’s best friend relationship.
public void findBestAcq(int type, int id, int value) {<!-- -->
if (type == 1) {<!-- --> // relationship becomes better
if (value > bestValue || (value == bestValue & amp; & amp; id < bestAcq)) {<!-- -->
bestAcq = id;
bestValue = value;
}
} else {<!-- --> // relationship goes bad
if (id == bestAcq) {<!-- -->
int max = 0;
int minId = 0;
for (int key : acquaintances. keySet()) {<!-- -->
int now = acquaintances. get(key);
if (now > max || (now == max & amp; & amp; key < minId)) {<!-- -->
minId = key;
max = now;
}
}
bestAcq = minId;
bestValue = max;
}
}
}
Hw11
Use HashMap to store emoji information, the key-value pair is private final HashMap
Least Moments
Find the minimum cycle passing through a person in the social network, and the weight of the edge is the intimacy of the relationship. I use the SPFA algorithm to find the shortest path from the source point to other points, and the time complexity is O(n^2), which meets the performance requirements.
A ring needs three different sides, so there are two cases to find the smallest ring from the shortest path:
- The extra edge contains the source point, and the smallest cycle consists of the extra edge and a shortest path of length>=2
- The extra edge does not contain the source point, and the smallest cycle consists of the extra edge and two shortest paths
public int leastMoments(int id) {<!-- -->
int ans = inf;
int index = match. get(id);
spfa(index);
for (int i : matrix.get(index).keySet()) {<!-- --> // extra edge contains source point
if (parent[i] != i) {<!-- -->
ans = Math.min(ans, getValue(index, i) + dis[i]);
}
}
for (int i = 0; i < num; i ++ ) {<!-- --> // extra edge does not contain source
for (int j : matrix. get(i). keySet()) {<!-- -->
if (i != index & amp; & amp; j != index & amp; & amp; findRoot(i) != findRoot(j)) {<!-- -->
ans = Math.min(ans, dis[i] + dis[j] + getValue(i, j));
}
}
}
return ans;
}
Performance optimization
The JML specification only gives the basic restrictions of the method. It often uses writing methods such as loops to constrain the changes before and after the method. If you copy it directly, it will lead to poor performance of the program. Therefore, it is necessary to optimize the algorithm and data structure level based on various conditions of the specification and side-effect requirements.
- Data structure optimization
My usual method is to optimize the storage structure of the data, choose the container HashMap instead of the array writing in JML, set the key to id, so that the search, insert, and Operations such as deleting are more efficient. - algorithm optimization
The methods involving graphs in JML usually use the violent search method of multi-layer traversal, which only guarantees correctness, sacrifices performance, and is not concise enough. Therefore, my optimization idea is to change the static algorithm into dynamic maintenance, or optimize the time complexity of the static algorithm. Specifically, I used the SPFA algorithm to find the shortest path, and search to find connected blocks, dynamic maintenance and other methods to make the program more efficient.
Therefore, we should realize that JML does not represent a specific implementation method, and JML cannot be translated mechanically during implementation, but it is used as a description of requirements, and it is carried out under the conditions that meet its constraints. High performance implementation.
OKTest
The OK test method plays an important role in verifying the consistency between implementation and specification of the code. By using the OK test method, developers can more reliably ensure the consistency of codes and specifications, and improve software quality.
Since the OKTest method does not need to use the attributes in the Network class, I separate it from the Network class and create a separate OK test class, which is stored as a static method.
qts
The full name is queryTripleSumOKTest, which corresponds to the queryTripleSum() method for querying the number of triple groups.
Since the original method is a pure method and does not change any attributes of the class, first check whether there are side effects before and after the method. Then Strictly according to the specification, use the brute force search method with a time complexity of O(n^3) in JML, and compare it with the correct output.
mr
The full name is modifyRelationOKTest, corresponding to the modifyRelation() method of Modify Relationship.
First check if the method expects to throw an exception but does not throw, completing the method normally. Then check whether the method meets the specification requirements, that is, check the post-condition ensure of JML, and check according to the line of JML code. If the ensure condition is not satisfied, return the first unsatisfied Number of lines, if satisfied, returns 0.
dce
The full name is deleteColdEmojiOKTest, which corresponds to the deleteColdEmoji() method of Delete Unpopular Emoji.
This method does not need to throw an exception, and the rest is the same as mr, just check the JML line by line and return the number of error lines.
Experience
There is a big difference between JML and the requirement description using natural language. Through a lot of exercises in this unit, I have cultivated the ability to read JML, and can quickly understand the meaning of JML. In the process, I actively learned some algorithms in graph theory and benefited a lot. shallow.
At the same time, I also learned how to use JML to describe requirements, how to use JML to check the consistency of code implementation and specifications, and have a deeper understanding of software engineering requirements analysis and testing methods.