Ήρθαν πάλι οι εποχές της προετοιμασίας και με πιάσαν ξανά τα υπαρξιακά μου
Ένα παράδειγμα από τον Κροατικό διαγωνισμό του Νοεμβρίου (φρεσκαδούρα), που προφανώς απαιτεί 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;
}
