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

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.

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

Δημοσίευσηαπό switch » Δευτ Δεκ 05, 2016 8:58 pm

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;
}

Άβαταρ μέλους
switch
 
Δημοσιεύσεις: 24
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am

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

Δημοσίευσηαπό userresu » Δευτ Ιαν 02, 2017 2:28 pm

Χρησιμοποιείς το vector με μη αποδοτικό τρόπο. Το erase σε vector που κάνεις έχει πολυπλοκότητα Θ(N), και αυτό κάνει την πολυπλοκότητα του αλγορίθμου σου τετραγωνική αντί για γραμμική. Γενικά σε vector είναι αποδοτική η εισαγωγή και αφαίρεση στοιχείων μόνο στο τέλος. Αυτό που χρειάζεσαι είναι μία ουρά (queue της STL).
userresu
 
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

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

Δημοσίευσηαπό switch » Τετ Ιαν 04, 2017 5:11 pm

Οκ κατάλαβα, ευχαριστώ.
Χρόνια πολλά και καλή χρονιά σε όλους.
Άβαταρ μέλους
switch
 
Δημοσιεύσεις: 24
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am


Επιστροφή στο Εξάσκηση και προετοιμασία

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης

cron