Algorítmo 3 e desalocação de memória

Algorítmo 3 e desalocação de memória

por Francisco de Melo Viríssimo -
Número de respostas: 10

Professor,

no algorítmo #3, no caso do #edifícios ser ímpar, qual a melhor maneira de construir o algorítmo? Posso fazer a união das metades separadas pelo vetor mediano, uní-las e só depois unir o vetor mediano?

Mais uma pergunta (pensei fazê-la em aula, mas vou aproveitar o espaço do fórum): a primeira vista, a função "união" pareceu-me figurar como o coração do EP. Mas percebi que há algo mais sutil a ser trabalhado neste programa, que é a desalocação de memória (não me parece trivial fazer o programa rodar uma arquivo grande como o que foi disponibilizado). É essa a idéia?

Obrigado.

Att,

Francisco

Em resposta à Francisco de Melo Viríssimo

Re: Algorítmo 3 e desalocação de memória

por Francisco Reverbel -
Caso o número de edifícios seja ímpar (da forma 2k+1), divida o conjunto de edifícios em duas partes com tamanhos "quase iguais": uma parte com k edificios e outra com k+1 edifícios. É isto que o enunciado diz:

Particione o conjunto de edifícios em duas "metades" (Note as aspas!).

O motivo para a palavra "metades" aparecer entre aspas é que no caso de um número ímpar de edifícios as "metades" não são de verdade... Por definição, duas metades deveriam ter tamanhos iguais. Como elas não necessariamente têm tamanhos iguais, então elas não são metades verdadeiras e sim "metades" aproximadas.

A desalocação de memória é muito importante sim. Como diz o enunciado:

Seu programa deve alocar dinamicamente todos os "vetores silhueta" que utilizar. Deve também liberar cada um desses vetores, quando não precisar mais dele. Pense com cuidado em que pontos do programa essas silhuetas têm de ser alocadas e em que pontos elas têm de ser liberadas.

Sem esse cuidado, o programa não funcionará com aquele exemplo de entrada grande. E ele deve funcionar! Melhor dizendo, os algoritmos 1 e 3 devem funcionar com a entrada grande. Já o algoritmo 2 não funcionará com a entrada grande. (Qual será a razão?)

Em resposta à Francisco Reverbel

Algoritmo 2 jamais funcionará para a entrada grande?

por Luciano Ramalho -
Professor, por favor clarifique esta sua frase: "Sem esse cuidado, o programa não funcionará com aquele exemplo de entrada grande. E ele deve funcionar! Melhor dizendo, os algoritmos 1 e 3 devem funcionar com a entrada grande. Já o algoritmo 2 não funcionará com a entrada grande. (Qual será a razão?)"

O senhor está querendo dizer que mesmo tomando todos os cuidados com a alocação e desalocação de memória nos lugares certos, o algoritmo2 do enunciado não conseguirá lidar com a entrada de 2 milhões de edifícios?

Porque atualmente esta é a situação da minha solução: os argoritmos 1 e 3 processam perfeitamente a entrada do exemplo2, mas o meu algoritmo 2 não consegue.

Se um dos objetivos do EP era mostrar que o algoritmo2 não escala, então eu aprendi a lição. Agora se existe um jeito de fazer o algoritmo2 lidar com 2 milhões de prédios, uma dica seria apreciada.

[ ]s
Luciano

Em resposta à Luciano Ramalho

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Francisco Reverbel -
"O senhor está querendo dizer que mesmo tomando todos os cuidados com a alocação e desalocação de memória nos lugares certos, o algoritmo2 do enunciado não conseguirá lidar com a entrada de 2 milhões de edifícios?"

Sim, foi isso que eu disse.

"Se um dos objetivos do EP era mostrar que o algoritmo2 não escala, então eu aprendi a lição."

Sim, esse é um dos objetivos. É importante entender bem o problema com o algoritmo 2 e saber porque esse problema não se manifesta no algoritmo 3!

"Agora se existe um jeito de fazer o algoritmo2 lidar com 2 milhões de prédios, uma dica seria apreciada."

Não há jeito de escrever o algoritmo 2 de modo que ele funcione com uma entrada arbitrariamente grande. O que deve ser possível é mexer no ambiente de compilação ou de execução para que o programa rode usando uma pilha com mais espaço. Uma providência assim faria o algoritmo 2 lidar com aquela entrada grande. Mas neste EP vocês não precisam fazer isso! (Não me perguntem como se faz isso, pois eu não sei... Há muito tempo atrás eu sabia esse tipo de coisa, mas hoje não faço idéia de como se especifica o tamanho da pilha de execução.) De qualquer modo, aumentar o tamanho da pilha de execução não é uma solução real. É só uma solução paliativa, pois o problema continuará se manifestando para entradas ainda maiores.

Em resposta à Francisco Reverbel

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Natan Costa Lima -
"Agora se existe um jeito de fazer o algoritmo2 lidar com 2 milhões de prédios, uma dica seria apreciada."

Se estiver usando linux faça:

ulimit -s

vc verá o tamanho máximo da pilha,

ulimit -s VALOR

mudará o valor atual por VALOR.


Se for muito grande ele deixará sem limites.
Basta conferir depois o valor 'setado' com 'ulimit -s'

Isto só funciona para o terminal que você está usando, se você fechá-lo ou abrir outro terminal o ulimit -s mostrará o valor original para ele.

Em resposta à Natan Costa Lima

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Francisco de Melo Viríssimo -

Natan, mas isso garante que o programa rodará sem emitir segmentation fault? Os testes que eu fiz mostraram que, para uma entrada desse tamanho (2 mihões), computadores como o meu (1mb de ram) não suporta a pilha de execução criada pelo algorítmo #2.

Obrigado.

Att,

Francisco

Em resposta à Natan Costa Lima

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Luciano Ramalho -
Muito grato pela dica, Natan, vou testar assim que me recuperar da ressaca.

Agora vou sair para beber muitas cervejas para comemorar a lição aprendida depois de tantas horas tentando entender porque eu encontrava um segmentation fault mas o mallocX não indicava falha de alocação. O problema era no stack, e não no heap...


Em resposta à Francisco Reverbel

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Luciano Ramalho -
Grato pela resposta, professor.

Curiosidade: o sr. chegou a mencionar em aula que o algoritmo 2 não seria capaz de lidar com a massa de dados grande?
Em resposta à Luciano Ramalho

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Francisco de Melo Viríssimo -

Luciano,

a verdadeira razão do algorítmo #2 não funcionar está estritamente atrelada às nossas máquinas. Fizemos as contas e, para rodar o segundo exemplo, seria necessária uma memória absurda (pelo menos umas 10 vezes mais do que nossos computadores residenciais possuem). Dessa maneira, por mais otimizado que seja o seu algorítmo, a pilha de execução sempre excedera as limitações de memória da máquina. Não sei se é possível burlar isto, talvez o professor saiba responder.

Meu amigo disse que conseguiu rodar este algorítmo na máquina dos admins da rede Linux (zillertown, é isso?). Bem, não acho que ele esteja mentindo.

Att,

Francisco

Em resposta à Francisco de Melo Viríssimo

Re: Algoritmo 2 jamais funcionará para a entrada grande?

por Pedro Brandimarte Mendonça -
Oi,

No meu caso, não consigo determinar a silhueta do arquivo grande com o algoritmo 1. Ele roda, mas chega uma certa hora em que não consegue mais alocar memória.

Com o algoritmo 3 roda normal e com o algoritmo 2 dá falha de segmentação, como era esperado.

O problema no algoritmo 1 pode ser por conta do computador que eu estou usando, ou deveria funcionar mesmo sendo um computador fraco?

Obrigado,


Pedro