Optimização

[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)

[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.

[soniculture]

Sim demora a correr  😁

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.

[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 😁

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++) {

[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.

[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" 😁

Mesmo assim não se torna possível.

Sim isto é um desafio que encontrei.

Obrigado pela dica 🙂

[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" 😁

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"

[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 😁

Por isso pedi as vossas sugestões!

Obrigado 🙂

[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 😁

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?

[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? 😁

[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).

[soniculture]

Vi no net empregos!

[soniculture]

Imagino que seja trivial 😁

Vou pensar mais um bocado 🙂

[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.

[soniculture]

É pelo desafio!

Já trabalho há muito tempo.

[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?

[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.

[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.

[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.

[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... 😁 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.