Wie heißt das private Array mit dem Inhalt des std::vector?

[wxSkip]

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...

[wxSkip]

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.

[Blue-Tiger]

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?

[wxSkip]

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

[Blue-Tiger]

Du hast das Testprogramm vergessen

[wxSkip]

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

[Blue-Tiger]

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

[Blue-Tiger]

Ach ja: "register" hat heutzutage keine Funktion mehr, der Compiler weiss selbst, welche Werte er im Register haelt 'inline' ist vermutlich genauso ueberfluessig.

[wxSkip]

Nein, das ist nicht sortiert... da muss ich noch den Fehler suchen...

[wxSkip]

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

[wxSkip]

Und jetzt ists auch deutlich langsamer

[Enttäuscht]

Und ich dachte jetzt hätte es endlich jemand geschafft in O(log n) zu sortieren

[wxSkip]

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!

[wxSkip]

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

[mann ey!]

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!

[wxSkip]

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...

[wxSkip]

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.

[wxSkip]

mann ey! schrieb:

Klingt nach einer scheiß Idee.

Weil die STL schon für jeden Anwendungszweck perfekt angepasst ist?

[wxSkip]

mann ey! schrieb:

Was bringt Dir das?

1. Ich hab sowieso noch andere Sachen damit vor, außer ihn zu sortieren.
2. Ich wusste damals ja noch nicht, dass man auf andere Weise an die Adresse des Arrays rankommt, um den Vektor effizienter zu sortieren.

[Sebastian Pizer]

wxSkip schrieb:

mann ey! schrieb:

Was bringt Dir das?

1. Ich hab sowieso noch andere Sachen damit vor, außer ihn zu sortieren.
2. Ich wusste damals ja noch nicht, dass man auf andere Weise an die Adresse des Arrays rankommt, um den Vektor effizienter zu sortieren.

Wenn der Ton auch zu wünschen übrig lässt, die Anmerkung von "mann ey!" ist berechtigt. Zu Deinem ersten Punkt: Soll das ein Argument sein, um von std::vector abzuleiten? Wenn ja: Versuch's nochmal. Vielleicht fällt Dir ein besserer Grund ein. Tipp: Es gibt keinen. Zum zweiten Punkt: Du glaubst scheinbar, dass der Zugriff auf die Daten eines vectors über einen vector-iterator langsamer ist als der Zugriff über ein Zeiger. Warum soll das so sein? Statt zu raten, solltest Du das vielleicht mal überprüfen! Mit dem Vevtor-eigenen Iterator schlägst Du -- bei einer guten STL-Implementierung -- zwei Fliegen mit einer Klappe: Im "Release-Modus" sind die Dinger sauschnell und im "Debug-Modus" erhältst Du zusätzliche Überprüfungen, um Fehler abzufangen.

Ich habe jetzt nicht mehr jeden Beitrag aus diesem Thread im Kopf. Mein Eindruck ist aber, dass die Punkte, die ich angesprochen habe, mehrfach erwähnt worden und von Dir ignoriert worden sind. Starke Leistung für einen 4-seiten-Thread!

Gruß,
SP