My blog yesterday 《 Difficult miscellaneous diseases : Why is it so slow to apply for memory 》 I have introduced this issue of tourism planning , This is actually an adjacency matrix problem , This program is slow on my computer , The main problem is the memory application and release mechanism , This point was introduced earlier , No more details here . After communicating with Mr. Zou Xin , I suddenly found out that this PTA Tourism planning of the platform (https://pintia.cn/problem-sets/15/problems/717)
Need to submit code online , It’s for java The maximum memory of the process is 64m, The longest running time is 800ms, That is to say, the addition I gave before largepage And define the initial jvm The method of memory parameter is not easy to use at all -XX:+UseLargePages -Xmx512m -Xms512m
We know that at present java The operating environment of the company is changing G,64m For those equipped with virtual machine and garbage collection mechanism java Come on , It’s almost the lowest runtime requirement , Near such a bottom line, programming should be carried out under the conditions of both time complexity and space complexity , It’s really challenging . Of course, the challenge was finally accomplished ,
Let’s take you through the whole process . First, read the question again .
Read the question again
There is a road map of self driving travel, showing the length of highways between cities 、 And the toll to be charged on the road . Now you need to write a program , Find the shortest path between the starting point and the destination . If there are several paths that are the shortest , Then you need to output the cheapest path .
Input format
:4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Enter description : Number of input data 1 Line is given 4 A positive integer N、M、S、D, among N(2≤N≤500) It’s the number of cities , By the way, suppose the city number is 0~(N−1);M It’s the number of expressways ;S It’s the city number of the place of departure ;D Is the city number of the destination . And then M In line , Each line gives information about a highway , Namely : City 1、 City 2、 The length of the highway 、 Charge amount , Separate… With spaces in the middle , All numbers are integers and no more than 500. Input guarantees the existence of solutions .
Output format :3 40
The length of the output path and the total charge in a row .
Read the title again , We’re going to the next stage .
Set the direction , First satisfy the spatial complexity , And optimize the time complexity
Generally speaking, in actual combat, there are few cases where both time and space complexity have higher requirements , If the time scene memory is not abundant, the time complexity is required to be high , Otherwise, the backup scene has plenty of time but requires high space complexity .
And when it comes to both fast and save memory , Be sure to meet the memory requirements first , Because memory is more rigid , Use more than will overflow crash , But there’s always a squeeze of time . There are usually optimization methods in the later stage .
The first solution to be eliminated , Object oriented design . We know all kinds of class members in object-oriented , function , There are requirements for alignment and garbage collection , More memory intensive than native types . Let’s go back to the topic itself , An adjacency matrix is a set of vertices and edges . Take the four vertex adjacency matrix as an example :
In the case that the edge relation is not sparse, the two-dimensional data can also replace the adjacency matrix realized by class , such as a[0][1] On behalf of 0 Node and 1 The distance between node two . And there is no limit to the number of edges in this topic , So it can only be done according to n^2 Edge application .
In the title is 500*500=250000 Elements , Then there are two more weight values on each edge , The biggest weight value is 500,500 Less than 2 Of 9 Power 512 That is to say, it can be used 9 Bit length data represents , Two 500 It just needs 18 Bit length , Draw the point here int Don’t fit , because int stay java Medium is 32 Bit , There is too much waste in .
There’s another solution here 16 Bit short Shift access with four Boolean values , That is to say short The height of 9 Bit means distance , low 5 Two and four Booleans represent the cost , However, this kind of displacement scheme has little practical value , It’s a brilliant plan , So we didn’t take this plan . When I’ve applied for all the memory in a minimal way ,jvm There’s no expansion of memory usage , So I can arrange the algorithm safely .
Code guide
Through the first n Value is the total number of cities , Initialize the pick up matrix , All edges are set to an impossible distance by default 501, Then through the definition of distance between cities and high-speed cost , Set the value of the leading matrix .
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
g[i][j][0] = INF;
g[i][j][1] = INF;
}
}
Reinitialize whether the node has been traversed known data
for(i=0;i<known.length;i++){
known[i]=false;
}
Group and the distance from the starting city to the corresponding city .
short [ ][ ] keyInput={
{0,1,1,20},{1,3,2,30},{0,3,4,10},{0,2,2,20},{2,3,1,20}};
while (m-->0) {
i=keyInput[m][0];
j=keyInput[m][1];
t1=keyInput[m][2];
t2=keyInput[m][3];
g[i][j][0] = g[j][i][0] = t1;
g[i][j][1] = g[j][i][1] = t2;
}
for (j = 0;j < n;j++) {
dis[j] = g[s][j][0];
pay[j] = g[s][j][1];
}
dis[s] = 0;
pay[s] = 0;
dis[n] = INF;
Finally, the iterative recursion compares the current shortest distance with the distance passing through the current node , If it is small, update the distance array , If it is the same size, it will be updated according to the high-speed cost .
while (true) {
v = n;
for (i = 0;i < n;i++) {
if (!known[i] && dis[i] < dis[v])
v = i;
}
if (v == n) break;
known[v] = true;
for (i = 0;i < n;i++) {
if (!known[i] && g[v][i][0] < INF) {
if (dis[v] + g[v][i][0] < dis[i]) {
dis[i] = (short)(dis[v] + g[v][i][0]);
pay[i] = (short)(pay[v] + g[v][i][1]);
}
else if (!known[i] && dis[v] + g[v][i][0] == dis[i] && pay[v] + g[v][i][1] < pay[i]) {
pay[i] = (short)(pay[v] + g[v][i][1]);
}
}
}
}
after n^2 Time to traverse the dis The array records the shortest distance from the starting node to the corresponding label node , that dis[d] That is, from the departure node to the destination d The shortest distance , Empathy pay[d] It’s the minimum cost , The output is the result .
if(dis[d] < INF)
System.out.println("Distance is "+String.valueOf(dis[d])+",The cost is "+String.valueOf(pay[d]));
By calculating the sample input 2c8g Alibaba cloud general ecs The model can be installed in 160ms Right and left to complete the task , See the screenshot at the beginning .
The complete code is as follows :
public class TestArray {
public static short N=500;
public static short INF=501;
public static void main (String[] args) {
System.out.println("Total init memory "+Runtime.getRuntime().totalMemory()/(1024*1024));
double timeNow=System.currentTimeMillis();
short [][][] g=new short[N][N][2];
short [] dis=new short[N + 1];
short [] pay=new short[N];
boolean [] known=new boolean[N];
short n, m, s, d, i, j, t1, t2, v;
n=4;
m= 5;
s= 0;
d= 3;
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
g[i][j][0] = INF;
g[i][j][1] = INF;
}
}
short [ ][ ] keyInput={
{0,1,1,20},{1,3,2,30},{0,3,4,10},{0,2,2,20},{2,3,1,20}};
while (m-->0) {
i=keyInput[m][0];
j=keyInput[m][1];
t1=keyInput[m][2];
t2=keyInput[m][3];
g[i][j][0] = g[j][i][0] = t1;
g[i][j][1] = g[j][i][1] = t2;
}
for(i=0;i<known.length;i++){
known[i]=false;
}
for (j = 0;j < n;j++) {
dis[j] = g[s][j][0];
pay[j] = g[s][j][1];
}
dis[s] = 0;
pay[s] = 0;
dis[n] = INF;
while (true) {
v = n;
for (i = 0;i < n;i++) {
if (!known[i] && dis[i] < dis[v])
v = i;
}
if (v == n) break;
known[v] = true;
for (i = 0;i < n;i++) {
if (!known[i] && g[v][i][0] < INF) {
if (dis[v] + g[v][i][0] < dis[i]) {
dis[i] = (short)(dis[v] + g[v][i][0]);
pay[i] = (short)(pay[v] + g[v][i][1]);
}
else if (!known[i] && dis[v] + g[v][i][0] == dis[i] && pay[v] + g[v][i][1] < pay[i]) {
pay[i] = (short)(pay[v] + g[v][i][1]);
}
}
}
}
if(dis[d] < INF)
System.out.println("Distance is "+String.valueOf(dis[d])+",The cost is "+String.valueOf(pay[d]));
System.out.println(System.currentTimeMillis()-timeNow);
System.out.println("Total memory at the end"+Runtime.getRuntime().totalMemory()/(1024*1024));
}
}
Thinking questions
Finally, I’ll leave you two questions , To test the effect of learning :
1 If the input city 1 And the city 2 How to deal with the expressway which is defined as two-way crossing , How to modify the code
2 If the upper limit of the number of cities n Turn into 1000 So is there enough memory , If it’s enough, how to adjust the code .
Welcome to leave a message and write down your answer