pointer und arrays

[doomcalyptica]

hi all
alle sagen, pointer sind schnell, sicher einfach unersetzbar. ok, wenn es um dynamische verwaltung von listen geht stimm ich dem zu, aber schneller ???
man schaut sich das programm an:
2 x bubblesort algorythmus (1 x mit einem normalen array und 1 x mal mit einer kopie des arary, hmm eigentlich nicht ganz richtig, was ich sagen wollte ... ähh, ein pointer array, welches auf die elemente das orginals zeigt :)
was wollte ich damit bezwecken ??
naja eigentlich nur mal schauen, ob pointer wirklich so schnell sind wie alle sagen, das ergebnis hat mich aber etwas erschüttert ^^


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 16000

int main() {
int a[MAX], *pa[MAX];
int i,j;
int tmp, *ptmp;
long zeit;

srand(time(0));

for(i=0; i<MAX; i++) {
a[i]=rand()%9999;
pa[i]=&a[i];
}

zeit=time(0);
printf("sortierung durch pointer\n");

for(i=0; i<MAX; i++) {
for(j=(i+1); j<MAX; j++) {
if(*pa[i]<*pa[j]) {
ptmp=pa[i];
pa[i]=pa[j];
pa[j]=ptmp;
}
}
}

printf("der vorgang dauerte %ds(pointer)\n",(time(0)-zeit));
printf("sortierung durch variablen\n");

zeit=time(0);
for(i=0; i<100; i++)
printf("%d\n",a[i]);



for(i=0; i<MAX; i++) {
for(j=(i+1); j<MAX; j++) {
if(a[i]<a[j]) {
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}



printf("der vorgang dauerte %ds(variablen)\n",(time(0)-zeit));


return 0;
}

wenn man da sso ausfürt, stellt man fest, das bubblesort mit pointer um rund 40% langsamer ist als mit "normalen arrays" (jaja ich weis, an sich sind es auch pointer blabla).

wahrscheinlich ist der vorgang bei euch ratzifatz beendet und die zeiten sind gleich 0s ^^
dann stellt doch die anzahl bei MAX etwas höher ... ihr müsst halt mal guggN.
ich hab es getstet auf einem dualboard 2xPentium MMX mit jeweils 200MHz, wobei nur effektiv eine CPU am rechnen war. naja der RAM war auch nur mit 128MB bestückt.
ihr könnt ja, wenn ihr wollt (ich hoffe es zumindest, eure ergebnisse hir her posten aber bitte die zieten nenne, das MAX und eure hardware (CPU RAM))

so aber nun zu meiner frage:
wieso sind pointer in diesem fall so langsam ?
warum sollte ich eine kopie des array anlegen ode rbesser gesagtm, wieso sollte ich ein pointer array auf ein array zeigen lassen und erst dann sortieren (naja eigentlich adressen tauschen) ?

[peschmae]

Naja, soo überraschen sollte dich das auch nicht. Ich meine was macht der Sortieralgorithmus vor allem?
- vergleichen: Das ist etwas langsamer mit Pointern, da noch eine indirektion mehr drin ist d.h. er muss gucken wo der Pointer hinzeigt und dann dort hingehen
- rumkopieren: Das ist auch nicht schneller mit Pointern weil der Pointer (meist - ist Maschinen- und Compilerabhängig) gleich gross ist wie ein int.

d.h. von den Pointern profitierst du beim Rumkopieren - aber nur wenn es nicht um ints geht am Ende sondern um grössere Objekte, weil du dann vermeiden kannst die immer rumzukopieren und jede Menge temporäre Objekte anzulegen. Stattdessen tust du nur die 4 Byte (oder so) Pointer rumschieben.

MfG Peschmä

[Detrius]

Dein Vergleich hinkt. ;)

Mit Pointern hast du folgendes gemacht:
*pa[i]
Du gehst also beim Array pa an die Stelle i und lässt Dir den Inhalt der Speicheradresse anzeigen, die dort abgelegt ist. Das sind im Einzelnen dann folgende Schritte:
1)Zum Beginn des Arrays pa gehen
2) von dieser Adresse zum Speichelement gehen, dass i Einträge weiter ist
3) den Inhalt des Elements lesen
4) zu der Speicheradresse dieses Inhalts gehen
5) den Inhalt dort lesen

Bei Deinem Vorgehen mit Arrays entfallen Schritt 4 und 5, daher ist es schneller.

Der richtigere Vergleich würde wohl eher so aussehen für die Pointer:


for(i = 0 ; i < MAX ; i++) {
for(j = (i + 1) ; j < MAX ; j++) {
if(*(a + i) < *(a + j)) {
tmp = *(a + i);
*(a + i) = *(a + j);
*(a + j) = tmp;
}
}
}


Damit sollte beides genau gleich lange dauern (ich hab es nicht getestet).