Wie heißt das private Array mit dem Inhalt des std::vector?
-
wxSkip schrieb:
Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt
Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?
-
GEFAHR GEFAHR GEFAHR schrieb:
Wenn du dich in die Klassenhierarchie einklinkst, brichst du damit die Kapselung auf. Es mag vielleicht die eleganteste Methode sein, dies zu tun, ändert aber nichts am eigentlichen Problem.
Das Testprogramm ist falsch, weil der Vector keine elemente enthält. Du greifst auf das nullste Element zu, obwohl es nie erzeugt wurde. Ändere die zweite Zeile in einen push_back()-Aufruf. Genau aus diesem Grund raten wir dir hier zu Iteratoren.
Danke, wenn ich den Vektor mit 5 initialisiere, funktionierts!
-
mann ey! schrieb:
wxSkip schrieb:
Nein, ich wollte ja gerade eine eigene Vektor-Klasse machen, die von std::vector erbt
Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?
Dann kann ich mir dort meine eigenen Funktionen machen oder friend-Funktionen deklarieren oder so...
-
Komisch... Mein Quicksort für Vektoren ist schneller als mein Quicksort für C-Arrays mit der Adresse des Arrays aufgerufen, obwohl beide genau denselben Algorithmus nutzen.
-
wxSkip schrieb:
Komisch... Mein Quicksort für Vektoren ist schneller als mein Quicksort für C-Arrays mit der Adresse des Arrays aufgerufen, obwohl beide genau denselben Algorithmus nutzen.
Koenntest du bitte mal Implementierung und Testprogramm posten, damit andere das auch nachvollziehen koennen?
-
Gerne!
template<class Type> inline void vquicksort2(myvector<Type> &in, register int size, register int pos = 0) { register Type tmp; register int right = pos + size - 1; register int left = pos; register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0; while(left < right) { if (in.at(left) > av) { if (av > in.at(right)) { tmp = in.at(left); in.at(left) = in.at(right); in.at(right) = tmp; left++; } right--; } else { if (av <= in.at(right)) right--; left++; } } if(left == right && in.at(left) <= av) left++; if((right = left-pos) < 2)return; else vquicksort2(in, right, pos); if((right = size-left+pos) < 2) return; else vquicksort2(in, right, left - pos); }
-
Du hast das Testprogramm vergessen
-
Ach so, das Programm, was das aufruft...
#include <algorithm> #include <vector> #include <iostream> #include <ctime> #define SIZE 20000000 using namespace std; template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0); inline double getProgramTime() { return clock() / (double)CLOCKS_PER_SEC; } int main() { vector<double> v1(SIZE), v2(SIZE), v3(SIZE); for(int c = 0; c < SIZE; c++) v1[c] = rand(); for(int c = 0; c < SIZE; c++) v2[c] = v1[c]; printf("Start.\n"); register double y = getProgramTime(); sort(v1.begin(), v1.end()); cout << "Sort-Zeit: " << getProgramTime() - y << "s\n"; y = getProgramTime(); vquicksort2(v2, v2.size()); cout << "Vquicksort2-Zeit: " << getProgramTime() - y << "s\n"; } template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0) { register Type tmp; register int right = pos + size - 1; register int left = pos; register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0; while(left < right) { if (in.at(left) > av) { if (av > in.at(right)) { tmp = in.at(left); in.at(left) = in.at(right); in.at(right) = tmp; left++; } right--; } else { if (av <= in.at(right)) right--; left++; } } if(left == right && in.at(left) <= av) left++; if((right = left-pos) < 2)return; else vquicksort2(in, right, pos); if((right = size-left+pos) < 2) return; else vquicksort2(in, right, left - pos); }
-
Ich hab mal simpl std::vector statt myvector verwendet. Damit kompiliert das Progamm auch, allerdings ist das array am Ende nicht richtig sortiert -- ist es das denn wenn du myvector verwendest?
int main(int argc, char** argv) { if (argc != 3) return 0; srand(42); unsigned N = atoi(argv[1]); vector<int> a; for (unsigned i = 0; i < N; ++i) a.push_back(rand()); if (argv[2][0] == 's') std::sort(a.begin(), a.end()); else vquicksort2(a, a.size()); cout << a[0] << '\t' << a[N/2] << '\t' << a[N-1] << '\n'; // compare outputs to see if numbers are identical return 0; }Ausgabe:
g++ -O3 -DNDEBUG test.cpp -o test tom@blulap:~$ time ./test 10000000 c 503 1692224497 205946697 real 0m0.722s user 0m0.550s sys 0m0.120s tom@blulap:~$ time ./test 10000000 s 503 1073448061 2147483606 real 0m1.957s user 0m1.730s sys 0m0.110s
-
Ach ja: "register" hat heutzutage keine Funktion mehr, der Compiler weiss selbst, welche Werte er im Register haelt
'inline' ist vermutlich genauso ueberfluessig.
-
Nein, das ist nicht sortiert... da muss ich noch den Fehler suchen...
-
OK, so gehts:
template <class Type> inline void vquicksort2(vector<Type> &in, register int size, register int pos = 0) { register Type tmp; register int right = pos + size - 1; register int left = pos; register double av = (in.at(pos) + in.at(pos+size-1)) / 2.0; while(left < right) { if (in.at(left) > av) { if (av > in.at(right)) { tmp = in.at(left); in.at(left) = in.at(right); in.at(right) = tmp; left++; } right--; } else { if (av <= in.at(right)) right--; left++; } } if(left == right && in.at(left) <= av) left++; if((right = left-pos) < 2)return; else vquicksort2(in, right, pos); if((right = size-left+pos) < 2) return; else vquicksort2(in, right, left); }
-
Und jetzt ists auch deutlich langsamer
-
Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren
-
Enttäuscht schrieb:
Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren
Argh! Das ist doch bewiesen, dass das nicht geht!
-
Also in dem Fall:
Mein Quicksort , der mit &(vec[0]) direkt auf dem Array arbeitet, ist nicht ganz so schnell, ich melde mich dann wieder, wenn ich Quicksort imperativ implementiert habe
-
wxSkip schrieb:
mann ey! schrieb:
Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?
Dann kann ich mir dort meine eigenen Funktionen machen oder friend-Funktionen deklarieren oder so...
Ja und? Was bringt Dir das? Klingt nach einer scheiß Idee. Null Ahnung von nix und dann auch noch beratungsresistent. Haben wir gerne.
wxSkip schrieb:
Enttäuscht schrieb:
Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren
Argh! Das ist doch bewiesen, dass das nicht geht!
Lass Deinen Sarkasmus-Detektor reparieren! Ist ja peinlich!
-
mann ey! schrieb:
wxSkip schrieb:
mann ey! schrieb:
Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?
Dann kann ich mir dort meine eigenen Funktionen machen oder friend-Funktionen deklarieren oder so...
Ja und? Was bringt Dir das? Klingt nach einer scheiß Idee. Null Ahnung von nix und dann auch noch beratungsresistent. Haben wir gerne.
Ich hab ja nicht gesagt, dass ich mich nicht beraten lasse, sondern nur, wie ich auf die Idee komme...
-
mann ey! schrieb:
wxSkip schrieb:
mann ey! schrieb:
Wie kommt man denn auf die Idee, von std::vector zu erben? Wozu soll das gut sein? Was hilft Dir das denn, wenn Du etwas sortieren willst?
Dann kann ich mir dort meine eigenen Funktionen machen oder friend-Funktionen deklarieren oder so...
Ja und? Was bringt Dir das? Klingt nach einer scheiß Idee. Null Ahnung von nix und dann auch noch beratungsresistent. Haben wir gerne.
Ich meinte eigentlich nicht Funktionen, sondern vor allem Operatoren überladen, denn das geht außerhalb ja nicht.
-
mann ey! schrieb:
Klingt nach einer scheiß Idee.
Weil die STL schon für jeden Anwendungszweck perfekt angepasst ist?