Ήρθαν πάλι οι εποχές της προετοιμασίας και με πιάσαν ξανά τα υπαρξιακά μου
![Mr. Green :mrgreen:](./images/smilies/icon_mrgreen.gif)
Ένα παράδειγμα από τον Κροατικό διαγωνισμό του Νοεμβρίου (φρεσκαδούρα), που προφανώς απαιτεί 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;
}