Sortieren schneller als std::sort

Servus,

Es gibt ja verschiedene Arten zu sortieren. Nach welcher arbeitet std::sort. Und gibt es eine Schnellere ?
Ich habe folgende Funktion:

double CMdxFiles::Interpolate(vector<double> x,vector<double> y,double xist)
{
		int i;
		double yist = 0;

		XY_Datensatz XY,temp;
		temp.X = xist;
		temp.Y = xist;
		temp.n = 0;

		Cmp cmp(temp);
		cmp.XY_arbeitspunkt = temp;

// Achtung zweitaufwendig
		vector<XY_Datensatz> vXY;
		vXY.clear();

		for(i=0;i<x.size();i++)
		{
			XY.n = i;
			XY.X = x.at(i);
			XY.Y = y.at(i);
			vXY.resize(vXY.size() + 1, XY);
		};

		sort(vXY.begin(),vXY.end(),cmp);

		if(vXY.size() >= 2)
		{
			yist = ( ( vXY[0].Y - vXY[1].Y ) / ( vXY[0].X - vXY[1].X ) * ( xist - vXY[0].X) ) + vXY[0].Y;
		}
		else
			yist = 0;

		return yist;
}

7H3 N4C3R

Die meisten Implementierungen benutzen AFAIK QuickSort, was auf einer unsortierten und "zufällig geordneten" Menge oft ein O(n*log n) bringt. Im Falle von ein paar "Killersequences" fällt es aber auf O(n*n) zurück.

Es gibt meines Wissens ein paar Modifizierungen von QuickSort, die mir namentlich gerade nicht einfallen, die u.U. effizienter sein können. Wenn du es schneller brauchst mit garantierter Mindestlaufzeit, könntest du auf Heapsort gehen, der hat eine garantierte Laufzeit von O(n*log n), kann aber meistens trotzdem nicht mit Quicksort mithalten.

berniebutt

Für kleine Datenmengen sind die Standard-Sorts wie Quicksort voll aureichend. Erst bei grossen Datenmengen können alternative Sort-Algorithmen Vorteile in der Laufzeit bringen. Mehr dazu findet sich sicher in der speziellen Literatur für Mathematiker weltweit.

Hallo,

es gibt auch noch std::stable_sort() ist oft mit einem mergesort implementiert.

Werner Salomon

Diplomand schrieb:

Es gibt ja verschiedene Arten zu sortieren. Nach welcher arbeitet std::sort. Und gibt es eine Schnellere ?

woher weißt Du denn, dass in Deinem Code der sort-Aufruf 'zeitaufwändig' ist?

Tausche doch mal die Zeile 23 von

Diplomand schrieb:

vXY.resize(vXY.size() + 1, XY);

nach

vXY.push_back( XY );

Ach - und lass Zeile 16 mit 'vXY.clear()' einfach weg. Das ist an dieser Stelle mehr als überflüssig.
Und kann es sein, dass in Zeile 8 ein copy-und-paste-Fehler vorliegt?

Gruß
Werner

Jester

std::sort nutzt meist Introsort, ein modifiziertes Quicksort. Das heißt es wird Quicksort benutzt, bis zu einer gewissen Mindestgröße, ab dann wird mit Insertionsort weitergemacht, weil das auf kleinen Eingaben schneller läuft.

Wenn man Quicksort randomisiert bekommt man eine erwartete Laufzeit von O(n log n), einige std::sort Implementierungen enthalten afair sogar eine Kontrolle, die abbricht, wenn der Aufwand zu groß wird und dann auf eine alternative Implementierung wechselt. Allerdings sind die std::sort-Implementierungen wohl meist nicht randomisiert, sondern benutzen eine einfache "Median of Three"-Strategie zur Auswahl des Pivots.

Für allgemeines Sortieren von Mengen, die in den Speicher passen gibt es nur eine handvoll Algorithmen, die schneller sind als Quicksort. Für große Datenmengen, die nicht mehr in den Speicher passen, sondern von der Platte gelesen werden müssen, ist Quicksort dagegen ungeeignet. Hier ist dann Merge-Sort die deutlich bessere Wahl.

Allerdings scheint mir bei Dir eher ein anderes Problem vorzuliegen.

for(i=0;i<x.size();i++)
{
  XY.n = i;
  XY.X = x.at(i);
  XY.Y = y.at(i);
  vXY.resize(vXY.size() + 1, XY);
};

Das gefällt mir nicht. Warum nicht lieber in der letzten Zeile: vXY.push_back(XY); wenn du Pech hast verbrätst Du nämlich hier die ganze Laufzeit, weil je nach Implementierung die Kapazität wirklich nur auch size+1 erhöht wird und du damit jedesmal alle Element rumkopierst. Wenn das der Fall ist verbrätst Du Deine Laufzeit hier.

Wenn Du das geändert hast, ist Dein Bottleneck tatsächlich das Sortieren. Die Frage ist, warum sortierst Du, Du benutzt doch am Schluß nur 2 Elemente? Vermutlich suchst du das nächstgrößere und das nächstkleinere Element, bzw. die beiden, die am nächsten an x_ist dran sind, oder? Das kannst Du mit einer einfachen Schleife auch in linearer Zeit machen: Ähnliches wie man ein minimales Element durch einmaliges drüberlaufen finden kann, kann man nämlich auch die beiden kleinsten bzw. die k kleinsten (für konstantes k) in linearer Zeit bestimmen. Damit kommst Du insgesamt auf lineare Laufzeit... danach kannst Du dann mit den low-level Optimierungen anfangen, falls es nicht sowieso reichen sollte.

hustbaer

Der Trick ist dass Introsort ab einer gewissen Tiefe (nicht Grösse!) auf Heapsort umschaltet, um die Fälle abzufangen wo Quicksort "entartet", also dann O(N^2) wäre. Damit hat man den Vorteil dass, wenn Quicksort nicht "entartet" alles so schnell wie bei Quicksort läuft, aber trotzdem immer O(N log N) garantiert ist.
Dass dann bei kleinen Sets (vielleicht 5 bis 10 Elemente) auf Insertion Sort umgeschaltet wird ist eine weitere Optimierung, die allerdings nicht massgeblich dafür ist ob sich ein Algorithmus Introsort nennt oder nicht.

Genaueres hier nachzulesen: http://en.wikipedia.org/wiki/Introsort

hustbaer

@Diplomand: ohne weitere Kenntnisse über das was sortiert werden soll, wie gross die Input-Sets sind, ob da schon was vorsortiert ist oder nicht etc., ist Introsort wohl im Moment das Optimum.

Wenn man natürlich bestimmte Annahmen treffen kann gibt es - je nachdem was für einen "Spezielfall" man gerade hat - bessere Alternativen. Es gibt z.B. Fälle wo ein einfacher Bubble-Sort viel schneller ist als Quicksort oder Introsort, nämlich wenn das Input-Set schon fast komplett vorsortiert ist.

Oder, wenn man weiss dass man nur wenige verschiedene Werte hat, diese dafür alle zig oder hundertfach vorkommen, und der Wertebereich sehr beschränkt ist, dann kann man schön Bucketsort verwenden.

uswusf.

Shade Of Mine

Der Code ist furchtbar ineffizient. Hier mal eine leicht korrigierte Version...

double CMdxFiles::Interpolate(vector<double> const& x,vector<double> const& y,double xist) 
//Kopien bei parametern vermeiden
{ 
assert(x.size() == y.size());
//damit wir uns x.at und y.at sparen.
        /*int i;
        double yist = 0;

        XY_Datensatz XY,temp; 
        temp.X = xist; 
        temp.Y = xist; 
        temp.n = 0; 

        Cmp cmp(temp); 
        cmp.XY_arbeitspunkt = temp; 
*/
// unnoetig??

        vector<XY_Datensatz> vXY; 
        vXY.reserve(x.size());
//verhindern von reallokationen

        for(int i=0;i<x.size();++i)
//standard for idiom
//uU noch x.size() aus der schleife raus 
        { 
/*            XY.n = i; 
            XY.X = x.at(i); 
            XY.Y = y.at(i); */
            vXY.push_back(XY_Datensatz(i, x[i], y[i])); 
//wir haben ja hoffentlich konstruktoren
        }; 

        sort(vXY.begin(),vXY.end(),Cmp()); 
//wozu braucht Cmp ein XY_Datensatz Element?
//wenn es das wirklich braucht, was _sehr_ komisch waere:
//sort(vXY.begin(),vXY.end(),Cmp(XY_Datenelement(0, xist, xist));
//sinnvoller waere sowieso den operator< von XY_Datensatz zu verwenden

        if(vXY.size() >= 2) 
        { 
            return ( ( vXY[0].Y - vXY[1].Y ) / ( vXY[0].X - vXY[1].X ) * ( xist - vXY[0].X) ) + vXY[0].Y; 
        } 
        else 
            return 0; 
//wir brauchen kein yist        
}

da wir aber sowieso keinen sortierten container brauchen, sondern nur die kleinsten (oder groessten) 2 Elemente, brauchen wir kein sort machen, sondern mit einer normalen suche koennen wir das in O(N) bestimmen.

was mich aber echt interessieren wuerde waere Cmp. das sieht einfach nur kaputt aus...

PS:
was Jester ueber Cmp sagt klingt vernuenftig... Ich ziehe meinen Cmp einwand damit zurueck.

Jester

Wenn viele Anfragen kommen, lohnt es sich evtl. doch in O(n log n) Zeit einmal sortieren. Anschließend kann man dann vermutlich in O(log n) Zeit die beiden interessanten Elemente finden.