Va rog ajutor optimizare cod sa fie mai rapid

[AlMalalah]

Salut !

Am facut acest cod in c++ :

#include<cstdio>
#include<cstdlib>
#include <iostream>
#include <stdio.h>
#include <fstream>

using namespace std;

ofstream out("output.txt");




int main()
{

	int a[10][7];
	//////////////////////////////////////////////////////////////////////////////////////////////
	a[1][1]=5;	a[1][2]=13;	a[1][3]=26;	a[1][4]=38;	a[1][5]=37;	a[1][6]=25;
	a[2][1]=20;	a[2][2]=32;	a[2][3]=38;	a[2][4]=21;	a[2][5]=5;	a[2][6]=11;
	a[3][1]=32;	a[3][2]=27;	a[3][3]=38;	a[3][4]=11;	a[3][5]=10;	a[3][6]=29;
	a[4][1]=10;	a[4][2]=36;	a[4][3]=31;	a[4][4]=40;	a[4][5]=3;	a[4][6]=38;
	a[5][1]=24;	a[5][2]=11;	a[5][3]=21;	a[5][4]=32;	a[5][5]=22;	a[5][6]=15;
	a[6][1]=32;	a[6][2]=5;	a[6][3]=8;	a[6][4]=7;	a[6][5]=22;	a[6][6]=24;
	a[7][1]=38;	a[7][2]=31;	a[7][3]=11;	a[7][4]=10;	a[7][5]=8;	a[7][6]=37;
	a[8][1]=12;	a[8][2]=25;	a[8][3]=1;	a[8][4]=6;	a[8][5]=22;	a[8][6]=9;
	a[9][1]=35;	a[9][2]=10;	a[9][3]=7;	a[9][4]=17;	a[9][5]=27;	a[9][6]=26;
	/////////////////////////////////////////////////////////////////////////////////////////////
	/* Acestea de mai sus sunt toate extragerile 5 din 40 de la prima si pana in prezent. Am lasat doar 9 dintre ele ca sa fie mai usor de inteles codul insa ultima extragere este asta:
	a[1133][1]=22;	a[1133][2]=36;	a[1133][3]=31;	a[1133][4]=34;	a[1133][5]=7;	a[1133][6]=13;
	Am inlocuit si in cod 1133 cu 9 ca sa mearga dar de fapt in loc de 9 e 1133 iar mai sus in loc de int a[10][7] e de fapt int a[1134][7]. */
//////////////////////////////////////////////////////////////////////////////////////////////////////////


	int g=0;
	int w[13];

	          for(int j=1;j<=29;j++)
	            for (int k=j+1;k<=30;k++)
	             for(int l=k+1;l<=31;l++)
	                for(int m=l+1;m<=32;m++)
	                  for(int n=m+1;n<=33;n++)
						for(int o=n+1;o<=34;o++)
						  for(int p=o+1;p<=35;p++)
							for (int q = p+1; q <=36; q++)
								for (int r = q+1; r <= 37; r++)
									for (int s = r+1; s <= 38; s++)
										for (int t = s+1; t <= 39; t++)
											for (int u = t+1; u <= 40; u++)
											{
												w[1]=j; w[2]=k; w[3]=l; w[4]=m;
												w[5]=n; w[6]=o; w[7]=p; w[8]=q;
												w[9]=r; w[10]=s; w[11]=t; w[12]=u;


												for (int f = 1; f <= 10; f++) //aici am pus 10 in loc de 1133
												{
													int b;
													if (g>=3)
													{
														g=0;
														break;

													}else if ((g<3)&&(b==7))
													{
														g=0;
													}


													for (b = 1; b <= 6; b++)
													{
														if (g>=3)
														{
															break;
														}
														for(int bank=1;bank<=12;bank++)
														{
															if (w[bank]==a[f][b])
															{
																g++;
																break;
															}
															if (g>=3)
															{
																break;
															}
														}

													}
													if ((f==10)&&(b==7)&&(g<3)) //aici la fel
													{
														for (int x=1;x<=12;x++)
														{
															out<<w[x]<<" ";
														}
														out<<endl;

														g=0;
													}


												}
											}


											out.close();					
						}

Ce face acest cod ?

Acest cod cauta toate combinatiile existente de cate 12 numere luate din 40 (de la 1 la 40) care au proprietatea de a avea in comun nu mai mult de 2 numere cu oricare extragere intre cele extrase pana in prezent la 5 din 40 (la 5 din 40 se extrag cate 6 numere).

Programul ia la puricat fiecare extragere si daca gaseste doar una singura care are mai mult de 2 numere in comun cu combinatia de 12 numere generata, atunci se opreste si genereaza urmatoarea combinatie de 12 numere si ia iara de la capat extragerile ca sa vada daca e vreuna care are mai mult de 2 numere in comun cu combinatia de 12 numere nou generata. Si tot asa.

In momentul cand a gasit una pentru care nu exista nici o extragere care sa aiba mai mult de 2 numere in comun cu ea, atunci o ia si mi-o scrie in fisierul output.txt.

Programul merge perfect si face exact ceea ce am spus mai sus.

Problema care e ?

Ar trebui sa il las sa mearga 3-4 zile non stop pana sa ajunga la final.

De asta vreau sa va rog mult de tot pe cei care va pricepeti sa incercati sa-l optimizati, poate nu ii va mai trebui atat de mult timp ca sa isi faca treaba, adica sa fie mult mai rapid.

Multumesc mult de tot !

Edited September 7, 2013 by AlMalalah

[tjt]

Ar putea fi optimizat cu LSH (locality-sensitive hashing ) ,dar e destul de greu de implementat un astfel de algoritm .

Incearca cu algoritmi bazati pe probabilitati pentru ca sunt mai eficienti atunci cand lucrezi cu un volum de date mare .

[AlMalalah]

Ar putea fi optimizat cu LSH (locality-sensitive hashing ) ,dar e destul de greu de implementat un astfel de algoritm .

Incearca cu algoritmi bazati pe probabilitati pentru ca sunt mai eficienti atunci cand lucrezi cu un volum de date mare .

Cum ? Cum adica ?

[tjt]

@AlMalalah http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

E asemanator cu ceea ce faci tu .Adica trebuie sa cauti grupuri (extrageri in cazul tau ) similare care au : "proprietatea de a avea in comun nu mai mult de 2 numere cu oricare extragere intre cele extrase pana in prezent la 5 din 40 (la 5 din 40 se extrag cate 6 numere)."

[H3xoR]

Încearc? s? faci cu backtrack. Dac? nu reu?e?ti, am s? revin eu mai pe sear? cu codul.

Baft?.

[AlMalalah]

Încearc? s? faci cu backtrack. Dac? nu reu?e?ti, am s? revin eu mai pe sear? cu codul.

Baft?.

Nu prea le am cu algoritmul de backtracking insa stiu ca am facut un test mai demult si am comparat doua programe care faceau acelasi lucru si unu folosea backtracking iar altul niste for-uri imbricate de genul asta si concluzia a fost ca ala cu foruri este muuult mai rapid decat ala care folosea backtracking.

Ma gandesc ca poate la programul asta or fi niste verificari inutile pe undeva sau mai stiu eu ce chestie care ar putea fi eliminata ca sa fie mai rapid... sau, daca conteaza la ceva, as putea sa sortez numerele din fiecare extragere sa fie de la mic la mare, crescator, daca conteaza la ceva.

Alta idee nu mai am cum sa fac ca sa fie cat mai rapid. Spre exemplu aveam un program care verifica daca un numar era prim sau nu si ori faceai cu d%2 etc. ori bagai toate numerele prime dinainte intr-un vector si era mai rapid, aici habar n-am ce sa-i fac ca sa fie mult mai rapid ca 3-4 zile sa-l las sa ruleze mi-e lehamite...

Poate ma poate ajuta cineva cu asta...

[AlMalalah]

@AlMalalah http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

E asemanator cu ceea ce faci tu .Adica trebuie sa cauti grupuri (extrageri in cazul tau ) similare care au : "proprietatea de a avea in comun nu mai mult de 2 numere cu oricare extragere intre cele extrase pana in prezent la 5 din 40 (la 5 din 40 se extrag cate 6 numere)."

M-am uitat asa pe documentul ala si nu stiu ce sa zic. In primul rand acolo nu e nici un algoritm ca exemplu. Eu nici cu backtackingul nu le am bine, il inteleg dar imi vine greu sa creez eu unul, d-apoi cu un algoritm de asta de hasing, LSH etc.

In al doilea rand, nu stiu daca nu cumva acolo este vorba de crearea de hashuri ptr. documente ca sa le recunosti mult mai repede. Functii de hashing, ceva de genul. Ma gandesc ca asa ceva ar fi si mai slow pentru programul meu.

Multumesc pentru ajutor !

[yoyois]

Nu prea vad cum te-ar ajuta backtracking-ul "pur" pe tine.

Ai putea sa-ti storci creierii cu o metoda mai matematica. Similara programarii dinamice.

Sa ordonezi sirurile de numere extrase dupa(sa zicem nr de numere comune) Si sa gasesti o relatie (sau ceva)

care sa te ajute sa elimini mai multe siruri deodata.

Spre exemplu:

Am numerel extrase:

1, 14, 19, 30, 25

1, 14, 12, 28, 21

(aranjate dupa un model matematic pe care trebuie sa-l descoperi tu)

daca verificam sirul 1 pt nr: 1, 14 si aflam ca nu e valid, atunci nici sirul 2 nu e valid, fiind intr-o anumita relatie cu sirul 1.

Asta ar fi un principiu deductiv, Se poate si inductiv... mult mai rapid, dar ,mai complicat din punc de vedere matematic.

Practic se poate optimiza algoritmul insa ar necesita o putere mai mare de calcul din partea "unui creier uman". Si probabil de la un anumit nivel eforturile de a aranja sirurile intr-un mod convenabil ar putea necesita mai multe calcule decat parcurgerea sirurilor.

De asemenea la atatea calcule s-ar putea sa conteze detaliile ca: Nu fa flush la date cand vrei sa le scrii in fisier, retine variabilele utilizate frecvent in memoria procesorului, foloseste cod inline, etc, etc.

[passfig]

Daca vrei sa fie mai eficient trebuie sa folosesti backtrack pentru generare, in nici un caz nu 15 for-uri, algoritmul ruleaza de 29*30*31*...*40 ori..gandeste-te ce inseamna asta. Cauta backtrack-ul pe net pentru ca daca vrei sa programezi ai nevoie sa il intelegi, se preda in liceu in clasa a 11-a. Poate fi facut cu recursivitate si fara.

[minamino]

S-ar putea sa ma insel insa cred ca ai putea sa te uiti putin si peste algoritmi genetici. Cred ca ei rezolva probleme care au foarte multe date

[sevenziparchive]

Nu stiu ce sa zic de C++, dar in Pascal ai Set of (in cazul acesta o sa fie Set of Byte). Faci o lista de seturi cu extragerile de pana acum, si apoi generezi combinatiile pe rand, verifici daca o variabila este in combinatia (Set-ul) respectiva folosind 'In'. Sper ca ti-a fost de folos.