Ποια τα συν της συναρτησης sort (STL)

[Evgenios1]

Εκανα κατι πειραματα με τις συναρτησεις qsort και std::sort και βλεπω οτι η qsort ειναι 10~ φορες πιο γρηγορη . Και το ερωτημα μου ειναι, ποιος ο λογος να χρησιμοποιησουμε τη std:sort?

[Evgenios1]

Εκανα κατι πειραματα με τις συναρτησεις qsort και std::sort και βλεπω οτι η qsort ειναι 10~ φορες πιο γρηγορη . Και το ερωτημα μου ειναι, ποιος ο λογος να χρησιμοποιησουμε τη std:sort?

[bnvdarklord]

Ισως η sort ειναι γρηγορότερη για καποια μικρα n.

[bnvdarklord]

Ισως η sort ειναι γρηγορότερη για καποια μικρα n.

[V.I.Smirnov]

Mε αφορμή αυτό θα πω κάτι που παρατήρησα για την STL :

Oι περισσότερες container classes της έχουν γραφεί με τρόπο ώστε να είναι οικονομικές και γρήγορες με την ασυμπτωτική έννοια.

Ο κύριος σκοπός της είναι να καλύπτει με βολικό τρόπο μια πληθώρα περιπτώσεων χρήσης δομών δεδομένων.

 

Για εφαρμογές όπου η μέγιστη ταχύτητα είναι το ζητούμενο, όπως οι μηχανές γραφικών, η επιβάρυνση που έχει στην ταχύτητα ενίοτε και στην μνήμη,

την καθιστούν ακατάλληλη και συνήθως πρέπει ο προγραμματιστής να ξαναγράψει μόνος του αυτό που χρειάζεται.

Όταν η μικρότερη ταχύτητα δεν ενοχλεί και δεν αξίζει η φασαρία να γραφεί κάτι που στην STL υπάρχει έτοιμο τότε η STL είναι καλή επιλογή...

[Evgenios1]

Απ'ο,τι διαβασα, η STL "ξερει" απο constr/destructor, αλλα και παλι δεν καταλαβενω το λογο που μια τετια συναρτηση πρεπει να ξερει απο τα παραπανω.

[bxenos]

η qsort μπορεί να δουλεψει με struct αλλά πρέπει να φτιάχνεις compare function για το κάθε struct.

 

η sort στη c++, σε προστατεύει απο πολλά λάθη (memory leaks), φροντίζει για contructor/destructors οπότε της περνάς αντικείμενα (που μπορεί να είναι αρκετά σύνθετες δομές) και δεν σε νοιάζει τι συμβαίνει απο πίσω. Π.χ. ταξινόμησε αυτοκίνητα σε ένα parking. Τα αντικείμενα κατά την μετακίνηση τους θα ασχολούνται με το ζωγράφισμα/σβήσιμο τους στην οθόνη (που θα τα παρέχει π.χ. ο constructor/destructor, χωρίς να χρειαστεί να κάνεις επιπλέον κλησεις εσυ.

 

Εχεις δοκιμάσει τον release κωδικα και είδες μεγάλη διαφορά σε ταχύτητα;

Σίγουρα υπάρχει διαφορά απο C++ σε C (άλλο να προχωράς ευθεία και άλλο να κάνεις ζικ-ζακ), αλλά μην νομίζεις ότι όλοι οι C++ προγραμματιστές χρησιμοποιούν τα πακετάκια που δίνει το std...

[Mpiritsas3]

Απ'ο,τι διαβασα, η STL "ξερει" απο constr/destructor, αλλα και παλι δεν καταλαβενω το λογο που μια τετια συναρτηση πρεπει να ξερει απο τα παραπανω.

 

παιδια επειδη ενδιαφερομαι να μαθω την γλωσσα προγραμματισμοπυ της STL και επειδη ειμαι καπως ξεκαρφωτος εδω τι πρεπει να κανω ακριβως για να μπορεσω να καταλαβω τι παιζει...

ξερω οτι υπαρχει στην c++ αλλα απο οσο ειδα εχει αρκετες εντολες διαφορετικες...

μπορειτε να μ πειτε στο περιπου τι παιζει?

δλδ χωρις την c++ μπορω να μαθω STL?και αν ναι υπαρχει καποιο βιβλιο η καποιος τροπος να αρχισω εντατικο διαβασμα?

[V.I.Smirnov]

παιδια επειδη ενδιαφερομαι να μαθω την γλωσσα προγραμματισμοπυ της STL και επειδη ειμαι καπως ξεκαρφωτος εδω τι πρεπει να κανω ακριβως για να μπορεσω να καταλαβω τι παιζει...

ξερω οτι υπαρχει στην c++ αλλα απο οσο ειδα εχει αρκετες εντολες διαφορετικες...

μπορειτε να μ πειτε στο περιπου τι παιζει?

δλδ χωρις την c++ μπορω να μαθω STL?και αν ναι υπαρχει καποιο βιβλιο η καποιος τροπος να αρχισω εντατικο διαβασμα?

 

Η STL δεν είναι γλώσσα προγραμματισμού και δεν έχει νόημα έξω από την C++.

Είναι απλώς μια βιβλιοθήκη με κάποιες έτοιμες δομές δεδομένων και χρήσιμα πράγματα για να μην είσαι αναγκασμένος να γράφεις δικά σου.

Ως βιβλιοθήκη είναι στάνταρ πράγμα που εξασφαλίζει συμβατότητα του πηγαίου κώδικα με διάφορους compilers.

 

Απ ότι ξέρω, τα "ευαγγέλια" για τα templates και την STL είναι τα δυο βιβλία του Ν. Jossutis και είναι απαραίτητα για όποιον χρησιμοποιεί την STL. Τα έχω και τα δύο.

Αλλά περιγράφουν μόνον την STL, δεν διδάσκουν C++.

 

Yπάρχουν αρκετά εισαγωγικά βιβλία για C++, άριστα από διδακτική άποψη και κάποια από αυτά εισάγουν ταυτόχρονα και την STL.

Το μόνο που χρειάζεται είναι να πας σε κάποιο βιβλιοπωλείο. Αν πάρεις ένα-δυο τέτοια δεν θα χρειαστεί να ξαναρωτήσεις τίποτε για πολύ καιρό.

[Evgenios1]

η qsort μπορεί να δουλεψει με struct αλλά πρέπει να φτιάχνεις compare function για το κάθε struct.

 

η sort στη c++, σε προστατεύει απο πολλά λάθη (memory leaks), φροντίζει για contructor/destructors οπότε της περνάς αντικείμενα (που μπορεί να είναι αρκετά σύνθετες δομές) και δεν σε νοιάζει τι συμβαίνει απο πίσω. Π.χ. ταξινόμησε αυτοκίνητα σε ένα parking. Τα αντικείμενα κατά την μετακίνηση τους θα ασχολούνται με το ζωγράφισμα/σβήσιμο τους στην οθόνη (που θα τα παρέχει π.χ. ο constructor/destructor, χωρίς να χρειαστεί να κάνεις επιπλέον κλησεις εσυ.

 

Εχεις δοκιμάσει τον release κωδικα και είδες μεγάλη διαφορά σε ταχύτητα;

Σίγουρα υπάρχει διαφορά απο C++ σε C (άλλο να προχωράς ευθεία και άλλο να κάνεις ζικ-ζακ), αλλά μην νομίζεις ότι όλοι οι C++ προγραμματιστές χρησιμοποιούν τα πακετάκια που δίνει το std...

Τι να σου πω... ανοιξα το αρχειο algorithm και δε βρικα κατι που να λεει version author etc.

 

Αυτο με τα αυτοκινητα δε το πολυκαταλαβα. Εστω οτι εχουμε τα objects a & b το a θα ειναι σε καταστηαση a1 και το b σε b1. Τα κανουμε swap με βαση pointer με αποτελεσμα εκει που ηταν το a1 να ειναι το b1. Ποιο το νοημα να παρουμε ενα αντιγραφο απο το a1 να δεσμευσουμε μνημη να το βαλουμε εκει (στη μνημη ) να διαγραψουμε τη μνημη εκει που ηταν κλπ κλπ, εξαλου ενα object εχει standar μεγεθος, οπια και να ειναι η κατασταση του.

 

 

τεσπα το timing το εκανα με το παρακατω

 

 

mian.cpp

>#include "stdafx.h"
#define szARR 0x003fffff
#define testType long
//globals
long *arr;
//-
int compare (const void * a, const void * ;//qsort
void CDFUNC clibSort()
{
qsort(arr,szARR,sizeof(testType),compare);
}
void CDFUNC StlSort()
{
std::sort(arr,arr+szARR);
}
int _tmain(int argc, _TCHAR* argv[])
{
CodeTimer *cd = new CodeTimer();
//iniz arr
srand(0);
   arr = new long[szARR];
for(int i=0;i<szARR;i++)
	arr[i] = rand();
//-
cd->Start(clibSort,1);
printf("C std sort result:%dms\n",cd->GetMilliSeconds());
cd->Release();

//reiniz arr (same values)
srand(0);
for(int i=0;i<szARR;i++)
	arr[i] = rand();
//-
cd->Start(StlSort,1);
printf("C++ std sort result:%dms\n",cd->GetMilliSeconds());

delete[] arr;
delete cd;


getchar();
return 0;
}


int compare (const void * a, const void * 
{
 return ( *(testType*)a > *(testType*)b );
}

codetimer.cc

>#include <time.h>
#define CDFUNC __fastcall 
#define MAX_EXCCOUNT 0xffffffff
#define MID_EXCCOUNT 0x00ffffff
#define LOW_EXCCOUNT 0x0000ffff
class CodeTimer
{
clock_t start, end;
long ms;
float sec;
void _calc()
{
	ms = (end-start);
	sec= ms/1000;
}
public:
CodeTimer(void)
{
	
}
~CodeTimer(void){}
void Start(void (CDFUNC *pFunc)(void),unsigned int exccount)
{
	Start();
	for(unsigned int i=0; i<exccount;i++)
		pFunc();
	Stop();
}
void Start(void)
{
	start =clock();
}
void Stop(void)
{
	end = clock();
	_calc();
}
void Release(void)
{
	end=0;
	start=0;
	ms=0;
	sec=0;
}
long GetMilliSeconds(void)
{
	return ms;
}
float GetSeconds(void)
{
	return sec;
}
};

 

 

[bxenos]

π.χ.

>
class foo {
   unsigned x;
public:
   foo() { putchar('C'); x = rand(); }
   ~foo() { putchar('d'); }
   foo(const foo& t) { putchar('K'); x = t.x; }
   int operator <(const foo& t){ putchar('<'); return x < t.x; }
   int operator >(const foo& t){ putchar('>'); return x > t.x; }
   int operator ==(const foo& t){ putchar('#'); return x == t.x; }
};

int main(){
	srand(0);
	foo *f = new foo[32];
	putchar('\n');
	std::sort(f,&f[32]);
	putchar('\n');
	delete []f;
}

 

δες το αποτέλεσμα για το σορταρισμα (ποσοι copy constructors, destructors, operators κλήθησαν):

>
απο το new foo[32]: CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC (φυσιολογικό)

απο το sort:
K<<dK<<dK<<<<dK<<<dK<<<dK<<<<<dK<<dK<<<<<dK<<<dK
<<<<<<<<<<dK<<<<dK<<<<<<<<<<<<<dK<<<<<<<<<<<<<<dK
<<<<<<dK<<<<<<<dK<<<<<<<<<<dK<<<<<dK<<<<<<<<<<<
<<<<<dK<<<<<<<<<dK<<<<<<<dK<<<dK<<<<<<<dK<<<<<<
<dK<<<<<<<<<<<<dK<<<<<<<<<<<<<<<<<<<<<<<<dK<<<<
<dK<<<<<<<<<<<<<<<<<<<<<<<<<dK<<<<<<<<<<<<<<<<<
<dK<<<dK<<<<<<<<<<<<<<<<<<<<<<<<<<dK<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<d

απο το delete []foo: dddddddddddddddddddddddddddddddd (φυσιολογικό)

 

τωρα θα μου πείς το int έχει copy constructors/destructors/operators; οχι ακριβως σαν συναρτήσεις (είναι inline) αλλά το overhead υπάρχει.