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

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

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

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

wxSkip

Sebastian Pizer schrieb:

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?

Das soll heißen, dass ich sowieso schon aus anderen Gründen von std::vecor abgeleitet habe.

Sebastian Pizer schrieb:

Warum soll das so sein? Statt zu raten, solltest Du das vielleicht mal überprüfen!
Gruß,
SP

Ich wollte es ja gerade überpüfen

wxSkip

Sebastian Pizer schrieb:

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

Sorry, aber habe ich das wirklich ignoriert? Ich leite für die Sortierfunktion doch gar nicht mehr von std::vector ab, sondern benutze entweder &(vec[0]) oder die .at()-Funktion. mann ey! hat halt einen älteren Beitrag kommentiert...

Nexus

wxSkip schrieb:

Sorry, aber habe ich das wirklich ignoriert?

Du hast einige Ratschläge, die dir in diesem Thread gegeben wurden, ignoriert. Es macht immer einen etwas zweifelhaften Eindruck, im Forum nachzufragen und es dann selbst doch besser zu wissen...

Was du betreibst, ist reinste Premature Optimization. Gerade der massive Einsatz von register und inline deuten darauf hin, dass du den Compilerfähigkeiten misstraust und versuchst, es selber besser hinzukriegen. Diese Schlüsselwörter einfach mal präventiv einzusetzen bringt nichts. Der Compiler versteht sie nur als Hinweis und kann in sehr vielen Fällen besser entscheiden, ob solche Optimierungen angebracht sind. Mit unüberlegtem Einsatz riskierst du sogar, dass das Programm langsamer wird, weil der Compiler seine eigenen Optimierungen zugunsten eines Programmierers, der die Kontrolle haben will, reduziert.

Vor allem, da du scheinbar Mühe mit grundlegenden Dingen wie Indexzugriff hast, bringt es dir viel mehr, Iteratoren einzusetzen als auf rohem Speicher zu operieren. Ich habe im Übrigen auch schon auf Seite 2 erwähnt, dass du dir ansonsten die Sicherheitsabfragen im Debug-Modus verspielst. Unterschätze diese nicht! Ich selbst habe mir durch eine Assertion am richtigen Ort schon einige Male stundenlanges Debuggen sparen können.

Das Wichtigste ist aber, dass du nicht versuchst, aufgrund von Vermutungen und aufs Geratewohl zu optimieren. Nochmals: Schreib zuerst korrekten Code! Es bringt dir absolut nichts, wenn dein Algorithmus zwar schnell ist, aber in gewissen Fällen Bugs enthält. Dazu kommt – besonders bei Sortieralgorithmen – dass schlussendlich die Logik des Algorithmus darüber bestimmt, ob eine Sequenz schnell sortiert werden kann. Mikrooptimierungen fallen dann meistens nicht mehr ins Gewicht.

wxSkip

Ich wusste ja, dass register und inline nur Hinweise sind, aber ich dachte, wenn der Compiler nicht darauf hingewiesen wird, zieht er es erst gar nicht in Erwägung... Ich hab jedenfalls mal einen Unterschied zwischen inline und nicht inline festgestellt. Nun gut, dann werde ich den Gebrauch in Zukunft einschränken, vor allem von register.

wxSkip

Weiß jemand, warum der gcc hier einen Fehler ausgibt:

template<class Type> void itquicksort(typename vector<Type>::iterator in, int size)
{
    //blah
}

int main(){    //deklaration usw.
    itquicksort(v1.begin(), (int)v1.size());
}

Er sagt:
error: no matching function for call to `itquicksort(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >, int)'

Nexus

Scheint so, als könnte er den Typ nicht herleiten. Aber warum machst du es nicht so? Diese Signatur ist auch viel verbreiteter und beschränkt dich nicht auf std::vector , sondern unterstützt alle Container mit Random-Access-Iteratoren (insbesondere auch C-Arrays).

#include <vector>
#include <iterator>

template <typename RandomAccessIterator>
void itquicksort(RandomAccessIterator begin, RandomAccessIterator end)
{
    // das wäre dann dein Typ (hier double)
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type type;

    // das wäre deine Grösse
    size_t size = end - begin;

}

int main()
{
    std::vector<double> v1 = /*...*/;
    itquicksort(v1.begin(), v1.end());
}

wxSkip

Vielen Dank, das funktioniert perfekt
Obwohl es mich wundert, weil in meinem anderen Projektordner hats ohne das typedef-Zeugs funktioniert.
Ich hab das jetzt getestet(mal mit 20 Mio. Pseudo-Zufalls-Doubles):
Direkt auf dem Array: 2.7 s
Mit Iteratoren: 3.2 s
Mit Zugriff über die .at() Funktion: 3.5 s

Nexus

Wenn du Microsoft Visual C++ verwendest, definiere das folgende Makro, um Checked-Iteratoren im Release-Modus auszuschalten. Diese sind Teil der erwähnten Laufzeitprüfungen. Im Release-Modus brauchst du sie eigentlich nicht.

#ifdef NDEBUG
 #define _SECURE_SCL 0
#endif

at() wird nie schneller als der Zugriff mit operator[] (ob nun auf dem std::vector oder direkt auf dem dynamischen Array) sein, weil der Index garantiert geprüft wird.

wxSkip

Nexus schrieb:

Wenn du Microsoft Visual C++ verwendest, definiere das folgende Makro, um Checked-Iteratoren im Release-Modus auszuschalten. Diese sind Teil der erwähnten Laufzeitprüfungen. Im Release-Modus brauchst du sie eigentlich nicht.
#ifdef NDEBUG
 #define _SECURE_SCL 0
#endif
at() wird nie schneller als der Zugriff mit operator[] (ob nun auf dem std::vector oder direkt auf dem dynamischen Array) sein, weil der Index garantiert geprüft wird.

Danke, aber ich verwende Code::Blocks mit MinGW.