• 周三. 2月 28th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

How to complete tourism planning by Java in 64M memory environment

[db:作者]

1月 5, 2022

 

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

《How to complete tourism planning by Java in 64M memory environment》有12个想法
  1. Прогон сайта с использованием программы “Хрумер” – это способ автоматизированного продвижения ресурса в поисковых системах. Этот софт позволяет оптимизировать сайт с точки зрения SEO, повышая его видимость и рейтинг в выдаче поисковых систем.

    Хрумер способен выполнять множество задач, таких как автоматическое размещение комментариев, создание форумных постов, а также генерацию большого количества обратных ссылок. Эти методы могут привести к быстрому увеличению посещаемости сайта, однако их надо использовать осторожно, так как неправильное применение может привести к санкциям со стороны поисковых систем.

    Прогон сайта “Хрумером” требует навыков и знаний в области SEO. Важно помнить, что качество контента и органичность ссылок играют важную роль в ранжировании. Применение Хрумера должно быть частью комплексной стратегии продвижения, а не единственным методом.

    Важно также следить за изменениями в алгоритмах поисковых систем, чтобы адаптировать свою стратегию к новым требованиям. В итоге, прогон сайта “Хрумером” может быть полезным инструментом для SEO, но его использование должно быть осмотрительным и в соответствии с лучшими практиками.

  2. Стяжка – существенный шаг в строительстве. Выравнивание пола способствует добиться ровное основание для дальнейших работ.

    Специалисты выполняют стяжка пола под ключ с оглядкой на всех требований и нормативов. Выравнивание пола осуществляется с использованием современных материалов, которые гарантируют устойчивость и качество.

    Покрытие пола даёт возможность сформировать идеальное основание для любых видов отделки. В столице выравнивание пола проводят опытные специалисты.

  3. Машинная штукатурка — современный метод проведения штукатурных работ.
    Суть его заключается в внедрении штукатурных станций, как правило, немецкого производства, благодаря которым смесь приготавливается и наносится на стену автоматически и с давлением.
    Механизированная штукатурка москва С подтвержденной гарантией До 32 процентов выгоднее обычной, Можно клеить обои без шпаклевки от кампании mehanizirovannaya-shtukaturka-moscow.ru
    Следовательно, усовершенствуется сцепление с поверхностью, а время работ снижается в 5–6 раз, в по сравнению с ручным способом. За счет механизации и облегчения труда цена механизированной штукатурки становится более выгодной, чем в случае традиционного способа.
    Для машинной штукатурки используются специализированные смеси, цена которых меньше, чем по сравнению с ручным методом примерно на 30%. При соответствующих навыках и опыте специалистов, а так же при соблюдении всех технологических правил, поверхность, покрытая штукатуркой оказывается абсолютно ровной (СНиП 3.04.01–87 «Высококачественная штукатурка») и глянцевой, поэтому последующая обработка шпатлевкой не не обязательна, что обеспечивает дополнительные средства для заказчика.

  4. Смешанная стяжка – строительная операция выравнивания пола. Устройство полусухой стяжки способствует подготовить ровное основание для последующей отделки.
    устройство полусухой стяжки Мы сделаем супер ровную стяжку пола. 7 лет опыта работы От 500 рублей за квадратный метр
    Уход за полусухой стяжкой включает в себя постоянный контроль и устранение недостатков с использованием специализированных инструментов.

    Специализированные инструменты для полусухой стяжки способствует осуществить процесс устройства с высокой точностью. Частично сухая стяжка пола представляет собой эффективный вариант для обеспечения качественного основания для последующих процедур.

  5. Девушки легкого поведения из Москвы готовы подарить вам незабываемые моменты. Эксклюзивное объявление: мне 18 лет, и я готова подарить тебе невероятный минет в машине. Ощути магию настоящего наслаждения! секс объявление. Эскорт-леди ждут вашего звонка. Узнайте, что такое настоящее удовлетворение в компании любовниц из столицы.

  6. Оцифровка документов цена за лист — это наше направление. Мы предоставляем услуги перевода на цифровой носитель с использованием новейших методов. Сотрудничество с нами — это эффективный способ сделать вашу документацию доступной в электронной форме.

  7. купить хостинг
    Когда речь заходит о создании своего собственного сайта, выбор хостинга играет огромную роль. Ведь именно хостинг будет определять доступность и быстродействие вашего сайта для пользователей. Если вы находитесь в Беларуси и ищете надежного хостинг-провайдера, то BestHost.BY – это отличный выбор. BestHost.BY – одна из ведущих хостинг-компаний в Беларуси, предоставляющая высококачественные услуги уже на протяжении 15 лет.

  8. 1xbet официальный сайт – это популярная букмекерская компания, предлагающая широкий выбор ставок на спорт, казино и многое другое. С высокими коэффициентами и удобным интерфейсом, 1xbet привлекает множество игроков. Он также предоставляет возможность онлайн-трансляций событий. 1xbet создает захватывающий игровой опыт для своих пользователей.

  9. 1xbet зеркало рабочее на сегодня – это популярная букмекерская компания, предлагающая широкий выбор ставок на спорт, казино и многое другое. С высокими коэффициентами и удобным интерфейсом, 1xbet привлекает множество игроков. Он также предоставляет возможность онлайн-трансляций событий. 1xbet создает захватывающий игровой опыт для своих пользователей.

  10. играть казино– это популярная букмекерская контора, предоставляющая широкий выбор ставок на спорт и казино. Сайт обладает удобным интерфейсом, мобильной версией и приложением для удобства пользователей. 1xBet также известен разнообразными акциями и бонусами, делая игровой опыт более захватывающим.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注