Προβληματισμός (ξανά) με την απόδοση (To vector or not?)

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Προβληματισμός (ξανά) με την απόδοση (To vector or not?)

Δημοσίευση από switch »

Hello World!

Ήρθαν πάλι οι εποχές της προετοιμασίας και με πιάσαν ξανά τα υπαρξιακά μου :mrgreen:

Ένα παράδειγμα από τον Κροατικό διαγωνισμό του Νοεμβρίου (φρεσκαδούρα), που προφανώς απαιτεί BFS (κατά πλάτος προσπέλαση δένδρου), το έκανα με vector και push_back/erase και το αποτέλεσμα δεν πέρασε από χρόνο στον δικό μου υπολογιστή.

Το έβαλα με plain C++ χωρίς std (βασικά C είναι με λίγες πινελιές C++) και είχα μεγάλη διαφορά.

Ξέρω ότι η std έχει πάρα πολλές εφαρμογές με τα vector/algorithm κλπ, αλλά ψάχνω τι φταίει και έχω τόσο μεγάλη διαφορά χρόνου.

Δοκίμασα να κάνω compile με /O2 (ακόμα και με /Οχ aggresive optimization σε MS C++) για να μην έχω debug πληροφορίες.

Μήπως είναι δικιά μου χαζομάρα και έχω δουλέψει λάθος τη vector? Δηλαδή θα έπρεπε να κάνω κάτι άλλο που να μην έχει alloc/free?
Έχω λάθος υλοποίηση του BFS?

Το πρόβλημα υπάρχει στην σελίδα 4 του αρχείου προβλημάτων Νοεμβρίου στο Κροατικό site: http://hsin.hr/coci/contest3_tasks.pdf

Το προγραμματάκι που έκανα που εκτελεί και τις δυο μεθόδους στη σειρά (δεν χρειάζεται αρχείο εισόδου, ούτε δημιουργεί αρχείο εξόδου):

Κώδικας: Επιλογή όλων

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

int X,Y;//input matrix dimensions
char S[2001][2001];	//input matrix
char best[4001];	//best solution string
int moves = 0;		//depth in tree (0==root)

void run_StdVector(){//προσπέλαση δένδρου κατα πλάτος με χρήση vector
	struct cell { 
		int y,x,ch; 
		cell(int yy,int xx,char cc) { y = yy; x = xx; ch = cc; }
		cell() { y = x = ch = 0; }
	};
	vector <cell> list;
	#define addL(y,x,c)	do{ list.push_back(cell(y,x,c)); }while(0)
	#define delL(a)		do{ assert(list.size()); a=list[0]; list.erase(list.begin()); }while(0)

	memset(best,0,sizeof(best)); moves=0;
	addL(0,0,S[0][0]);
	//
	while(list.size()){
		int n = list.size();
		for(int i=0;i<n;i++){
			cell a; 
			delL(a);
			assert(a.x<X && a.y<Y);
			char test = a.ch;
			if(test>=0){
				if(best[moves]==0 || best[moves]>test)
					best[moves] = test;
				if(test==best[moves]){
					//add its next moves to the end of list
					if(a.y+1<Y && S[a.y+1][a.x]>0){
						addL(a.y+1,a.x,S[a.y+1][a.x]);
						S[a.y+1][a.x] = 0;//mark cell as handled (do not bother again)
					}
					if(a.x+1<X && S[a.y][a.x+1]>0){
						addL(a.y,a.x+1,S[a.y][a.x+1]);
						S[a.y][a.x+1] = 0;//mark cell as handled (do not bother again)
					}
					//there is no need for termination condition, because
					//the [Y-1][X-1] is the last position accepted AND
					//the final destination simultaneously
				}
			}//test>=0
		}
		moves++;
	}
	#undef addL
	#undef delL
}

void run_HandMadeQueue(){//προσπέλαση χωρίς vector, με χρήση queue (χωρίς τo overhead από τα new/free του vector)
	int head=0,tail=0,size=0;
	#define NL	4001
	static struct ListNode {
		int y,x,ch;
		ListNode(int yy,int xx,int cc) { y=yy;x=xx;ch=cc; }
		ListNode() { y=x=ch=0; }
	} L[NL];
	#define addL(y,x,c)	do{ size++; L[tail] = ListNode(y,x,c); if(tail++>=NL) tail=0; }while(0)
	#define delL(a)		do{ assert(size); a = L[head]; size--; if(head++>=NL) head=0; }while(0)
	memset(best,0,sizeof(best)); moves=0;

	addL(0,0,S[0][0]);

	while(size){
		int n = size;
		for(int i=0;i<n;i++){
			ListNode a; 
			delL(a);
			assert(a.x<X && a.y<Y);
			char test = a.ch;
			if(test>=0){
				if(best[moves]==0 || best[moves]>test)
					best[moves] = test;
				if(test==best[moves]){
					//add its next moves to the end of list
					if(a.y+1<Y && S[a.y+1][a.x]>0){
						addL(a.y+1,a.x,S[a.y+1][a.x]);
						S[a.y+1][a.x] = 0;//handled
					}
					if(a.x+1<X && S[a.y][a.x+1]>0){
						addL(a.y,a.x+1,S[a.y][a.x+1]);
						S[a.y][a.x+1] = 0;//handled
					}
					//there is no need for termination condition, because
					//the [Y-1][X-1] is the last position accepted AND
					//the final destination simultaneously
				}
			}//test>=0
		}
		moves++;
	}
	#undef addL
	#undef delL
}

void read1(){
	FILE *in = fopen( "pohlepko.in" , "r" ) ;
	assert(in);
	fscanf(in,"%d %d\n",&Y,&X);
	cout << "x:" << X << " y:" << Y << endl ;
	for(int y = 0 ; y < Y ; y++){
		fscanf(in,"%s",S[y]);
		assert(strlen(S[y])<=2000);
	}
	fclose(in);
}
	
void read2(){
	memset(S,'c',sizeof(S));
	X=Y=2000;
	S[4][4] = 'b';
	S[10][30] = 'a';
	S[50][50] = 'z';
}

int main()
{
	//FILE *out = fopen( "pohlepko.out" , "w" ) ;
	//assert(out);
	
	cout << "starting BFS with std::vector usage" << endl ;
	read2();
	run_StdVector();
	for(int i=0;best[i];i++)
		if(best[i]!='c')
			printf("%4d is %c\n",i,best[i]);
	
	cout << "starting BFS with hand made queue" << endl ;
	read2();
	run_HandMadeQueue();
	for(int i=0;best[i];i++)
		if(best[i]!='c')
			printf("%4d is %c\n",i,best[i]);

	cout << "Finito" << endl ;
		
	//fprintf(out,"%s\n",best);
	//fclose(out);
	return 0;
}

userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Προβληματισμός (ξανά) με την απόδοση (To vector or not?)

Δημοσίευση από userresu »

Χρησιμοποιείς το vector με μη αποδοτικό τρόπο. Το erase σε vector που κάνεις έχει πολυπλοκότητα Θ(N), και αυτό κάνει την πολυπλοκότητα του αλγορίθμου σου τετραγωνική αντί για γραμμική. Γενικά σε vector είναι αποδοτική η εισαγωγή και αφαίρεση στοιχείων μόνο στο τέλος. Αυτό που χρειάζεσαι είναι μία ουρά (queue της STL).
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Προβληματισμός (ξανά) με την απόδοση (To vector or not?)

Δημοσίευση από switch »

Οκ κατάλαβα, ευχαριστώ.
Χρόνια πολλά και καλή χρονιά σε όλους.
Απάντηση