🚀 go-pugleaf

Am 2. Apr. 1996 schrieb Dieter Lücking
(luecking@braunschweig.netsurf.de):

> //                However 'TYPE::opertor == (const T&)' is invoked twice and may reduce
> //                the performance.

Ein 'TYPE::operator==' wird überhaupt nicht aufgerufen, verglichen
werden ausschließlich Zeiger. Du meinst vermutlich 
'TYPE::operator= (const TYPE&)'. Dieser wird allerdings *dreimal* bei
jedem Schleifendurchlauf aufgerufen.

>       assert(start <= end && star <= mark && mark <= end);

Die Abfrage "start <= end" ist hier überflüssig, da sie schon aus den
anderen beiden Bedingungen folgt. (Den Tippfehler 'star' habe ich
implizit korrigiert.)

>          while(p < mark && s < end) {
>             t     = *s;
>             *p++  = *s;
>             *s++  =  t;
>          }

Das dürfte nicht viel bringen. Du überschreibst hier den Wert von *p
bevor Du ihn benutzt und schreibst nach *s genau den Wert, der da schon
steht. Du meinst vermutlich

	while (p < mark && s < end) {
	   t = *s;
	   *s++ = *p;
	   *p++ = t;
	}

M. a. W., Du willst *s und *p vertauschen und dann die Zeiger s und p
inkrementieren.

> Respose to luecking@braunschweig.netsurf.de

Diskussionen sollten hier im Brett stattfinden, damit alle was davon
haben.

So wie ich das verstehe, dient die Funktion dazu, in einem Feld zwei
Bereiche zu vertauschen, wobei nur eine einzelne Variable 't' als
Hilfsspeicher benutzt wird. Also mal etwas anders formuliert: Gegeben
sei ein n > 0, ein Feld a[0],...,a[n-1] mit n Elementen und ein k mit
0 < k < n. Das Feld soll jetzt so umsortiert werden, daß die ersten 
k Elemente hinten stehen und die letzten n-k El. vorne.

Der obige Algorithmus braucht dazu im ungünstigsten Falle n-1 Ver-
tauschungen (wen k = 1) und im günstigsten Fall n/2 Vertauschungen 
(falls k = n/2). Für jede Vertauschung werden drei Wertzuweisungen
benötigt. (Wertzuweisung meint hier Aufrufe von 'TYPE::operator=')
Die Anzahl der Wertzuweisungen ist also im günstigsten Fall n+n/2
und im ungünstigsten Fall 3n-3.

Der folgende Algotithmus benötigt nur  n + ggT(n,k)  Wertzuweisungen.
Im Falle  k = n/2  ist das genausoviel wie oben, in allen anderen Fällen
besser. (ggT meint "größter gemeinsamer Teiler") 

Ich benutze Indizes und keine Zeiger. Wer meint, daß das Arbeiten mit
Zeigern effizienter ist, der möge die Funktion umschreiben.


template<class TYPE>
void xtExchange (TYPE *a, int n, int k)
{
    int gg = ggT(n,k);

    for (int j=0; j < gg; j++) {

        TYPE t = a[j];

        for (int i=j;;) {
            int ii = i+k;
            if (ii >= n) ii -= n;
            if (ii == j) { a[i] = t; break; }
            a[i] = a[ii];
            i = ii;
        }
    }
}



Karl-Heinz Krause