Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

soniculture

Optimização

Mensagens Recomendadas

soniculture

Olá a todos!

Estou com um problema de optimização.

Tenho um "nested loop" que demora muito a compilar.

Alguma sugestão de optimização?

Aqui vai o código:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int main (void) {
int64_t c, r, x, y, aux;
c=0;
aux=0;
r = 968790360;
for(x=-r;x<=-1;x++){
for(y=-r;y<=-1;y++){
	c+=((x*x)+(y*y)<=(r*r));
	if (c>aux) {
		c=c-y;
		aux=c;
		break;
	}
}
printf("%lld\n",x);
}
c=4*c+5;
printf("%lld\n",c);
c = (c * 0x671659AD2B395A35LLU) ^ 0x6A657B39259F7846LLU; 
printf("%.8s", (char *) &c); 
return 0;
}

Edit: GeSHi adicionado (pmg)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

tenho as minhas dúvidas que demore a compilar ... não quererás dizer a correr ?

ps : espero que apareça alguém com vontade porque com variável com esse nome e zero de comentário não me vou dar ao trabalho de ler o código.


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
soniculture

Sim demora a correr  :cheesygrin:

O código é simples ele avalia esta expressão

c+=((x*x)+(y*y)<=(r*r));

E se for verdade soma um se não soma zero lol

Só quero uma forma de fazer com que aqueles ciclos corram depressa!

Obrigado.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

r*r nao varia dentro do ciclo -- podes calcular uma vez e aproveitar o resultado

x*x só varia dentro do ciclo "x" -- podes calcular uma vez por ciclo "x" e aproveitar o resultado

ver http://en.wikipedia.org/wiki/Loop-invariant_code_motion

Mas um bom compilador já faz isso sózinho. Certifica-te que estás a compilar com as optimizações todas: -O2 ou -O3 no gcc.

Outra coisa: em vez de "%lld" para imprimires valores de tipo int64_t, faz o #include correcto e usa a macro PRId64

#include <inttypes.h>

/* ... */

printf("a conta deu %" PRId64 " valores\n", val64);

Mais uma coisa: os espaços há muito tempo que ficaram baratos. Poupar nos espaços dentro do código não aumenta a performance do código ... e diminui (e muito) a performance do programador :cheesygrin:

Compara

for(x=-r;x<=-1;x++){
        for(y=-r;y<=-1;y++){

for (x = -r; x <= -1; x++) {
        for (y = -r; y <= -1; y++) {


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Estás sinceramente à espera que o teu computador seja capaz de correr dois loops encaixados cada um com ~10^9 iterações (i.e. ~10^18) num tempo razoável?

Imaginemos que o ciclo interior fazia apenas uma operação simples e que o teu computador conseguia fazer 3*10^9 operações por segundo (3GHz), tens que fazer em cada ciclo interior pelo menos 3 operações: comparar y com -1, fazer y++, fazer a "operação simples" dentro do ciclo, ou seja, tens que fazer ~ 3*10^18 operações. Isto dá cerca de 10^9 segundos ou seja, mais de 31 anos.

O problema não está na optimização do ciclo interior mas sim na quantidade de operações completamente ridícula que estás a tentar fazer.

Olhando para a forma como o código está escrito (sobretudo a parte final em que faz um produto e xor com hexadecimal seguido de um print do inteiro como se fosse uma string) tem todo o ar de ser um desafio (i.e. perceber o que o código "quer fazer" e encontrar o resultado certo num tempo exequível, usando o cérebro e não o teclado) mas posso dar-te uma dica:

No fim dos dois ciclos encaixados, c corresponde à soma de -y+1, para todos os (x,y) com -r <= x <= -1, -r <= y <= -1, dentro do círculo de raio r.  Para cada x é possível encontrar o maior valor (absoluto) de y tal que (x,y) está dentro desse círculo em O(1). Se este for ymax então todos os valores de y em {ymax, ymax+1, ..., -1} correspondem a pontos dentro do círculo. A soma de valores consecutivos tem uma fórmula bem conhecida (que Gauss descobriu quando tinha 10 anos) portanto também O(1). Sendo assim, podes encontrar o valor de c e resolver o teu problema em O®, =)

EDIT: Para cada x apenas se soma -y+1 em que y é o menor tal que (x,y) está no círculo, não tinha reparado no break dentro do if.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
soniculture

Mas isso é o que está a fazer o If!

Quando ele encontra para um valor x um valor y que retorna true, ele faz todos os valores igual a 1 e soma-os ao "c" :cheesygrin:

Mesmo assim não se torna possível.

Sim isto é um desafio que encontrei.

Obrigado pela dica :)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Mas isso é o que está a fazer o If!

Quando ele encontra para um valor x um valor y que retorna true, ele faz todos os valores igual a 1 e soma-os ao "c" :cheesygrin:

Sim, isso é o que está a fazer o if. A diferença é que, como te expliquei o tempo de execução desse código é O(r^2) que não é possível de fazer com um computador pessoal. O único desafio está em perceber o que faz o código, e convertê-lo num algoritmo que execute num tempo razoável.

EDIT: Tinha-me enganado, o problema é mais simples ainda porque tem um break dentro do if em que eu não tinha reparado, i.e. podes esquecer a conversa toda sobre o Gauss e etc. ele limita-se a somar, para cada x,  y+1 em que y é o maior (em termos absolutos) -r <= y <= -1 tal que (x,y) está no círculo de raio r.

P.S.: "welldone"


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
soniculture

Aquilo que acontece é que se por exemplo se x = 10 e y = 11 retorna 1; x = 11 e y = 10 também!

Ou seja estou a duplicar as operações!

Estou à procura de um método para evitar isso :cheesygrin:

Por isso pedi as vossas sugestões!

Obrigado :)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Aquilo que acontece é que se por exemplo se x = 10 e y = 11 retorna 1; x = 11 e y = 10 também!

Ou seja estou a duplicar as operações!

Estou à procura de um método para evitar isso :cheesygrin:

Por isso pedi as vossas sugestões!

Obrigado :)

Acho que não percebeste nada do que escrevi. x e y são sempre negativos nesse código. Ele não "retorna" esses valores simétricos porque a única coisa que ele usa é o maior valor de y, tal que (x,y) está dentro do círculo para cada x. Mesmo que tal acontecesse, o máximo que irias fazer ao eliminar essa simetria era dividir o tempo de execução por 2, e quando a ordem de grandeza é dezenas de anos, é pouco relevante se consegues reduzir o tempo para metade.

P.S.: Onde é que encontraste este desafio?


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
soniculture

Não é isso que ele retorna Pedro!

Ele retorna 1 se o produto do quadrado de x vezes o quadrado de y é menor ou igual ao quadrado de r!

Por isso e indiferente ser negativo ou positivo, certo? :cheesygrin:

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Na expressão c+=((x*x)+(y*y)<=(r*r)); é indiferente o sinal de x e y, mas no código completo não.

Ele percorre todos os x de -r até -1 (negativos). Para cada x, percorre todos os y desde -r até -1 (negativos). Quando encontra um (x,y) que está dentro do círculo de raio r, o valor de c aumenta em 1 e entra no if. Dentro do if soma -y ao c e sai do ciclo dos y.

Isto trocado por miúdos corresponde exatamente ao que eu disse: Para cada x, encontra o y mais negativo tal que (x,y) está dentro do círculo de raio r, e soma 1-y ao valor de c. Tal como está, esse código acha este valor de y fazendo um ciclo desde -r o que é leeeeento. É trivial achar este valor de y para cada x com uma única operação (em vez de um ciclo) e assim fazer com o que o código corra num tempo razoável.

EDIT: Já vi que o encontraste num anúncio de emprego (com erros ortográficos por sinal).


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Se é pelo desafio, ok. Mas se estás a pensar candidatar-te a um emprego sem conseguires resolver um problema tão simples se calhar devias estudar um bocadinho de algoritmia antes.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
brunoais

Eu tb vi, vejo o código mas não vejo o enunciado. O que é que é suposto fazer com o código?

Por a correr e obter o e-mail?


"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Eu tb vi, vejo o código mas não vejo o enunciado. O que é que é suposto fazer com o código?

Por a correr e obter o e-mail?

Penso que o anúncio a que o autor do tópico se está a referir é este:

http://www.net-empregos.com/1411798/desafio-para-programador-em-c-e-c-m-f/

Deves enviar um e-mail com a solução e cv para o e-mail que o código escreve. Obviamente o código que está no pdf demora anos até concluir pelo que tens que calcular o mesmo número de forma eficiente como eu descrevi detalhadamente neste tópico.

P.S.: Embora esteja na dúvida entre apagar ou não. Por um lado a empresa quer pessoas que saibam resolver esse problema "sem ajuda" e como tal isto não é benéfico, por outro lado a solução do problema é pedagógica e esse é também um dos objectivos do fórum. Sinceramente não sei.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
brunoais

^ Já conseguiste resolver?

Nos meus cálculos já reduzi o trabalho para menos de 1/10000 do original mas n estou a ter respostas num tempo razoável (3 minutos). É suposto demorar mais? Eu já tentei algumas outras soluções mas estão, aparentemente, erradas.


"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

^ Já conseguiste resolver?

Nos meus cálculos já reduzi o trabalho para menos de 1/10000 do original mas n estou a ter respostas num tempo razoável (3 minutos). É suposto demorar mais? Eu já tentei algumas outras soluções mas estão, aparentemente, erradas.

Se releres o tópico vês que eu descrevi exatamente a forma como se chega à solução (que tem que ser linear em r para correr num tempo aceitável - 3 minutos é aceitável, já que te permite descobrir o e-mail para o qual deves mandar o currículo). No meu pc (que tem 5 anos) a solução que descrevi neste tópico demora pouco mais de 1 minuto a correr. Usando simetrias do problema é possível fazer apenas um ciclo em que x vai de r/sqrt(2) e r, e que no meu pc corre em cerca de 25 segundos.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mjamado
Usando simetrias do problema é possível fazer apenas um ciclo em que x vai de r/sqrt(2) e r, e que no meu pc corre em cerca de 25 segundos.

Eu percebo que calculas só 45º, e depois fazes alguma magia para encontrar os y correspondentes aos 45º seguintes ao mesmo tempo mas, sinceramente, não estou a ver como. A esta hora também já não funciono lá muito bem... :cheesygrin: Depois mostra como resolveste dessa forma.

De qualquer maneira, da forma mais comum (só um ciclo de x, entre r-1 e 1), corre entre os 31s e os 35s na minha máquina (Core i7 920 @ 2.66). Se houvesse maneira de eliminar aquele sqrt é que era...

Agora, três notas sobre o anúncio.

Em primeiro, esta abordagem de resolver algoritmos deve ser a coisa mais estúpida que as empresas fazem, seja qual for o formato: pré-entrevista, ficam sem saber se a pessoa resolveu mesmo ou se veio para um fórum de programação pedir ajuda :) ; em entrevista, ficam sem saber se a pessoa não sabe ou se bloqueou sob pressão.

Em segundo, para uma empresa "especializada no desenvolvimento de soluções informáticas de gestão e controlo, orientada para o mercado do ponto de venda", colocar um problema que é meramente matemático é absurdo.

Em terceiro, pretendem "alguém que já programa desde muito novo e que começou a programar por iniciativa própria, e que pode assim mostrar projectos que já fez para permitir avaliar a sua qualidade" e que, ao mesmo tempo, tenha "formação superior em Eng. Informática, ciências de computadores ou equivalente". Novamente, isto é absurdo. As duas coisas anulam-se, não se complementam. Ou avaliam a qualidade do portfolio, ou avaliam as notas do curso.

Sinceramente, o maior problema das empresas em Portugal não é a produtividade: é a gestão de recursos humanos, especialmente a captação.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

@mjmado, sim também achei que o anúncio estava bastante fraquinho

Em relação ao problema, a ideia é só tornar o algoritmo linear (para encontrar a resposta) como fizeste. Em relação à sqrt não estou a ver de repente maneira de a tirar da solução,  há algoritmos bastante mais eficientes que o do math.h para fazer sqrt de inteiros, tirando isso não sei.

Em relação ao r/sqrt(2) (i.e. os 45º) a ideia é a seguinte (SPOILER):

Para cada x menor que r/sqrt(2) vamos ter y = (r*r - x*x) > r/sqrt(2) e vice-versa (i.e. ou estamos dum lado ou do outro da linha x=y, a 45º). Se começarmos com x=(int) r/sqrt(2) + 1, vamos obter um determinado valor de y, y1 = (int) (r*r - x*x). Para r/sqrt(2) + 2, vamos obter um valor de  y2, menor.

Para todos os valores y em ]y2 , y1], o maior valor x correspondente é r/sqrt(2)+1. Devido à simetria entre x e y, isto quer dizer que para todos os x em ]y2, y1] o maior valor y é r/sqrt(2)+1. Pelo que para além da soma habitual c+=2*y+1, temos ainda (y1-y2)*(2*(r/sqrt(2) + 1) + 1), (que é como quem diz, vamos realizar a operação c+=2*y+1, para todos os x entre ]y2,y1]). Desta forma, guardando em cada iteração o valor y encontrado na última, conseguimos somar todos os pontos correspondentes aos 0 < x <= r/sqrt(2). Repara que os valores de y que vamos encontrar vão cobrir todo o intervalo ]0, r/sqrt(2)], e assim contamos, os pontos todos.

Tenho a noção que esta explicação está muito manhosa mas se tiveres alguma dúvida diz. O código corre em pouco menos que o limite de tempo do servidor do ideone para utilizadores registados que é 15s (e que tem  este cpu).


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
brunoais

Então é por isso q continua um pesadelo para mim. Isto é matemática pura aplicada à programação. Eu nunca consegui ser muito perspicaz com matemática. Mesmo assim, antes de vir cá hoje já tenho um código que corre em 1 minuto (2,13GHz) mas n funciona. Deve faltar-lhe um promenor...


"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mjamado

@pedrosorio, realmente, a tua explicação não é das melhores do mundo, não... :confused:

Mas percebi o conceito, mais uns rabiscos, e cheguei lá. Funny fact: quando estava a mostrar à minha esposa, ela chamou-me à atenção para o link no teu post que leva... ao código completo. :wallbash:

De qualquer forma, na minha máquina corre em 10 a 12s. Isto foi engraçado.

C360_2012-02-2503-04-31.Share.jpg


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.