Thread View: de.comp.lang.c++
2 messages
2 total messages
Started by Dieter Lücking
Tue, 02 Apr 1996 05:47
algorithm
Author: Dieter Lücking
Date: Tue, 02 Apr 1996 05:47
Date: Tue, 02 Apr 1996 05:47
71 lines
3239 bytes
3239 bytes
An algorithm:
// ============================================================================================
// Contents:
// ============================================================================================
//
// xtExchange
//
// ============================================================================================
// (Created) Dieter Luecking
// ============================================================================================
#include <assert.h>
// ============================================================================================
// xtEchange
// ============================================================================================
//
// Arguments: 'TYPE* start' is the stating position.
// 'const TYPE* mark' is the marked position (condition: 'start' <= 'mark').
// 'const TYPE* end' is the ending positin (condition: 'mark' <= 'end').
// Description: This function exchanges all values in front of 'mark' with all values
// at and after 'mark' upto 'end'.
// Return: A pointer to the new position of of 'start'.
// Example: Array: "start XXX mark YYY end ZZZ"
// Exchanged: "mark YYY start XXX end ZZZ"
// Remarks: The execution time is (in the worst case) linear to 'end' - 'start'.
// However 'TYPE::opertor == (const T&)' is invoked twice and may reduce
// the performance.
//
// ============================================================================================
template <class TYPE>
TYPE* xtExchange(TYPE* start, const TYPE* mark, const TYPE* end) {
assert(start <= end && star <= mark && mark <= end);
TYPE* p = start;
TYPE* newpos = p + (end - mark);
TYPE* s = (TYPE*)mark;
TYPE t;
while(mark < end) {
while(p < mark && s < end) {
t = *s;
*p++ = *s;
*s++ = t;
}
if(p == mark) mark = s;
else s = (TYPE*)mark;
}
return newpos;
}
template <class T>
inline TYPE* xtExchange(TYPE* start, const TYPE* mark, size_t size) {
return xtExchange(start, mark, start + size; }
template <class T>
inline TYPE* xtExchange(TYPE* start, size_t mark, size_t size) {
return xtExchange(start, start + mark, start + size); }
// ============================================================================================
// EOF
// ============================================================================================
I hope that more discussions refer to programming.
Have a nice work
Dieter Luecking
P.S.:
Respose to luecking@braunschweig.netsurf.de
Re: algorithm
Author: Karl-Heinz Krause
Date: Wed, 03 Apr 1996 16:47
Date: Wed, 03 Apr 1996 16:47
85 lines
3296 bytes
3296 bytes
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
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads