昨天笔者的博客《疑难杂症:申请点内存怎么这么慢》曾经对于这个旅游规划问题进行过介绍，这其实是一个邻接矩阵的问题，这个程序在笔者的电脑上之所以慢，主要还是在于内存申请与释放机制的问题，这点前文介绍过，这里不加赘述。而在与邹欣老师沟通之后，我突然发现原来这个PTA平台的旅游规划问题(https://pintia.cn/problem-sets/15/problems/717)
需要在线提交代码，其中提供给java进程的内存最大只有64m，最长的运行时间只有800ms，这也就是说我之前给出的加largepage和限定初始jvm内存参数的方法根本不好用了 -XX:+UseLargePages -Xmx512m -Xms512m
我们知道目前java的运行环境动辙上G，64m对于配备了虚拟机和垃圾回收机制的java来说，就几乎是最低的运行时要求了，在这样的底线附近编程还要在时间复杂度与空间复杂度都有要求的条件下进行，这真的比较挑战。当然最终完成了这个挑战，
这里就带各位读者复盘一下整个历程。首先要再读一遍题。
再次读题
有了一张自驾旅游路线图显示了城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式
:4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:3 40
在一行里输出路径的长度和收费总额。
再读完一遍题目，我们进入下一阶段。
定方向，先满足空间复杂度，再优化时间复杂度
一般来说在实战中很少有时间与空间复杂度同时都有较高要求的情况，要不是时间场景内存较充裕对于时间复杂度要求高，要不就是备份场景时间时间充裕但对空间复杂度要求高。
而当遇到既要快又要省内存的情况，一定要先满足内存的要求，因为内存刚性较强，用超过了就要溢出崩溃，但是时间挤挤总是有的。后期一般有优化的方法。
最先排掉的解决方案，面向对象的设计。我们知道面向对象中的各种类成员，函数，本身就有对齐及垃圾回收的要求，比原生类型更耗内存。我们再回归到题目本身，所谓邻接矩阵就是顶点与边的集合.以四顶点的邻接矩阵为例:
在边关系不稀疏的情况下二维数据也能够替代通过类来实现的邻接矩阵，比如a[0][1]就代表的0号节点与1号节点的距离。而这道题目中也没有限定边的条数，因此只能按照n^2条边申请。
代到题目当中就是500*500=250000个元素，那么每条边上又有两个权重值要存，一个权重值最大只有500，500小于2的9次方512也就是可以用9位长的数据表示，两个500其实只需要18位长，画重点这里用int不合适，因为int在java中是32位的，太浪费了。
这里还有一个方案是用16位的short与四个布尔值进行移位操作存取，也就是short的高9位表示距离，低5位与四位布尔表示费用，不过这种移位方案没有什么实践价值，纯属炫技的方案，因此没有采取这个方案。当我把所有内存都按照最小化的方式申请好之后，jvm的内存使用并没有扩张，这我就可以放心安排算法了。
代码导读
先通过n值也就是城市总个数，初始化领接矩阵，所有边默认设为不可能达到的距离的501，再通过城市间距离与高速费用的定义，将领接矩阵的值设定好。
-
for (i =
0;i < n;i++) {
-
for (j =
0;j < n;j++) {
-
g[i][j][
0] = INF;
-
g[i][j][
1] = INF;
-
}
-
}
再初始化节点是否遍历过的标志known数据
-
for(i=
0;i<known.length;i++){
-
-
known[i]=
false;
-
-
}
组以及出发城市到对应城市的高速公路距离。
-
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;
最后迭代递归通过目前最短距离与经当前节点的距离进行比较，若小则更新距离数组，若一样大则根据高速费用更新。
-
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]);
-
}
-
}
-
}
-
}
经过n^2次遍历dis数组记录出发节点到对应标号节点的最短距离，那么dis[d]也就是出发节点到目的地d的最短距离，同理pay[d]是最小花费，输出即是结果。
-
if(dis[d] < INF)
-
System.out.println(
"Distance is "+String.valueOf(dis[d])+
",The cost is "+String.valueOf(pay[d]));
通过计算样例输入2c8g的阿里云普通型ecs机型可在160ms左右完成任务,详见开头的截图。
完整的代码如下：
-
-
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));
-
-
}
-
}
-
思考题
最后给大家留两道思考题，以检测一下学习的效果：
1如果输入中城市1与城市2的高速公路被定义为双向可过的应该如何处理，代码如何修改
2如果城市数量的上限n变为1000那么内存还够吗，如果够代码如何调整。
欢迎留言写下你的答案
转载：https://blog.csdn.net/BEYONDMA/article/details/115606833