[C] Quicksort Zeitmessung -> Dumping stack trace

Page 1 of 2 1 2
12/10/2013 10:25 Belur#1
Hey,

hatte die Aufgabe verschiedene Arrays zu erzeugen. Mit den Größen
10
100
1000
10000
100000
1000000

Dazu sollte ich prüfen wie lange jeweils der Quicksort braucht um die Arrays zu sortieren.
Habe mir das also folgendermaßen vorgestellt:

PHP Code:
void zeit(){

    long int i;
    printf("\t Quicksort\n");
    for(i=10; i<=1000000; i*=10){
    xl=i;
    generieren();
    time_t vorher=time(NULL);
    quick_sort(daten);
    time_t nachher=time(NULL);
    printf("%d \t %d \n", i, (int)(nachher-vorher));


        }

} 
Wie man die Zeit angeblich misst, wurde uns vom Professor in einem Bsp. gezeigt.

xl ist die Länge des Arrays.

Hab erst gedacht es liegt daran, das der Datentyp int zu klein ist, da die Zahlen ja bis 1Million gehen.
Also alle relevanten Ints mal auf long int geändert.
Aber folgender Fehler bleibt nach wie vor:

Code:
0 [main] Praktikum4 4564 open_stackdumpfile: Dumping stack trace to Praktikum4.exe.stackdump
Vllt kann mir da jmd helfen.

Grüße
12/10/2013 12:22 Dr. Coxxy#2
zeig mal kompletten src und was fürn compiler du benutzt.

außerdem ist time nicht für solche zeitmessungen geeignet, da sie nur im sekundenbereich arbeitet, selbst mit 1mio elementen wird quicksort vermutlich unter 1 sekunde bleiben.

Code:
    for(i=10; i<=1000000; i*=10){
    xl=i;
was soll die schleife überhaupt?
12/10/2013 15:54 ilovenoodles#3
Wozu long int? int auf x86 architekturen hat 32bit. 2^32 = 4294967296 abs values (unsigned). signed entsprechend ~ hälfe (positiv), was locker ausreicht.

Fehler ist ein Stack Overflow, sprich du initialisierst wahrscheinlich ein Array mit size i auf dem Stack. Der Stack ist begrenzt. Sowas macht man auf dem Heap:

int *iArray = new int[1000000];

PS.: An welcher Wald und Wiesen Hochschule.... Mathematische Komplexität? Argh.
12/10/2013 17:52 Belur#4
Mit dem long int war ich mir nicht sicher :D
Hatte es erst auch als normales int und bin dann hierauf gestoßen.
[Only registered and activated users can see links. Click Here To Register...]

Deswegen hab ich das zur Vorsicht mal geändert weil ich dachte das wäre evtl zu klein.

Problem ist allerdings, dass wir keine Heaps hatten :<
Warscheinlich weil ich grad im ersten Semester bin...




Und zum 1. Beitrag.

Das Array sollte ja immer um den Faktor 10 vergrößert werden und dann sortiert werden.
Und generieren() generiert das Array mit der Größe xl.

Vllt ist noch wichtig zu erwähnen, dass es sich um ein 2d Array handelt also:

PHP Code:
long int daten[][yl]; 
Wobei in unserem Fall yl erstmal fest auf 2 begrenzt ist.

Grüße
12/10/2013 18:26 Dr. Coxxy#5
wie gesagt, zeig mal den kompletten source, wir haben leider keine glaskugel mit der wir deine fehler aufspüren können.

EDIT:
hier schenk ich dir:
Code:
#define DATEN_SIZE 10000000

int daten[DATEN_SIZE];

void Fill()
{
	for (int i = 0; i < DATEN_SIZE; i++)
	{
		daten[i] = rand() | (rand() << 15);
	}
}

void Print()
{
	for (int i = 0; i < DATEN_SIZE; i++)
	{
		printf("%d:\t%d\n", i, daten[i]);
	}
}

int __cdecl cmp(const void* a, const void* b)
{
	return (*(int*) a) - (*(int*) b);
}

void Sort()
{
	qsort(daten, DATEN_SIZE, sizeof(int), cmp);
}

// main
	srand((unsigned int)time(NULL));

	Fill();
	//Print();
	getc(stdin);
	DWORD Begin = GetTickCount();
	Sort();
	printf("\nGebrauchte Zeit: %d ms\n\n", GetTickCount()-Begin);
	getc(stdin);
	//Print();
GetTickCount ist allerdings windows spezifisch, müsstest du dann gucken.
12/10/2013 18:44 Dr. Coxxy#6
Quote:
Originally Posted by ilovenoodles View Post
blabla
bin mir zu 99% sicher, dass das nicht sein problem ist, da er in der funktion anscheinend auf das array als globale zugreift und man ein array nicht dynamisch in einer funktion auf dem stack allokieren kann (zmdst mit C sprachmitteln), deswegen wie ich jetzt zum 3. mal schreibe soll er mal den gesamten source rausrücken und sagen welchen compiler/ide/os er benutzt.
12/10/2013 18:55 ilovenoodles#7
Und wie ich recht habe: [Only registered and activated users can see links. Click Here To Register...]

Ist global...
12/10/2013 19:00 MrSm!th#8
Quote:
Originally Posted by ilovenoodles View Post
Und wie ich recht habe: [Only registered and activated users can see links. Click Here To Register...]

Ist global...
Und damit nicht auf dem Stack, sondern im Data-Segment.
Ein Array muss eine Compile-Zeit-Konstante als Größe haben, ergo kann er i ohnehin in keinem Fall nutzen, um das Array zu erzeugen.
Das ginge, wie du schon erkannt hast,nur auf dem Heap.
Und btw. ist new kein C.
Quote:
Originally Posted by ilovenoodles View Post
@Dr. Coxxy: Das wird so nicht laufen. Legst auch 10^7 integer aufn Stack...
Nein. Klugscheißen will gelernt sein.

Übrigens ist es nicht korrekt, dass int notwendigerweise 32bit hat, da liegt der TE schon richtig.
Wenn er Werte bis zu 4 mrd speichern will, braucht er plattformunabhängig mindestens einen long. Int wird es auf den meisten Plattformen allerdings auch tun.
12/10/2013 19:35 ilovenoodles#9
Hab nie behauptet das new zu C gehört. Und Compile-Zeit-Konstante hasse resch, würde nur mit nem define laufen.



Quote:
Originally Posted by MrSm!th View Post
Übrigens ist es nicht korrekt, dass int notwendigerweise 32bit hat, da liegt der TE schon richtig.
Wenn er Werte bis zu 4 mrd speichern will, braucht er plattformunabhängig mindestens einen long. Int wird es auf den meisten Plattformen allerdings auch tun.
Blödsinn. Fragt sich wer hier Klugscheißt :p
12/10/2013 19:36 Dr. Coxxy#10
Quote:
Originally Posted by ilovenoodles View Post
Hab nie behauptet das new zu C gehört. Und Compile-Zeit-Konstante hasse resch, würde nur mit nem define laufen.





Blödsinn. Fragt sich wer hier Klugscheißt :p
was hältst du davon deine klappe zu halten und mal weniger blödsinn von dir abzusondern?
12/10/2013 20:24 Belur#11
Bevor das hier noch weiter ausartet poste ich mal meinen Quellcode, der allerdings ziemlich unübrsichtlich ist.
Erstsemester und so :D :D

Geschrieben unter Eclipse mit Cygwin auf Windows.



PHP Code:

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


#define yl 2

long int daten[][yl];
long int xl=20;



void qs(int daten[][yl], int links, int rechts) {
  int i,j;
  int x,y,z;

  i=links; j=rechts;
  x = daten[(links+rechts)/2][1]; // mittleres Element

  do {
    while (daten[i][1]<x && i<rechts) i++; // such Element für "große Klasse"
    while (x<daten[j][1] && j>links) j--;     // such Element für "kleine Klasse"

    if (i<=j) {                                     // vertausche Elemente
      y = daten[i][1]; //zahl zwischenspeichern
      z = daten[i][0]; //index zwischenspeichern
      daten[i][1] = daten[j][1];
      daten[i][0] = daten[j][0];
      daten[j][1] = y;
      daten[j][0] = z;
      i++; j--;
    }
  } while (i<=j);

  if (links<j) qs(daten, links,j);                   // Aufruf für "kleine Klasse"
  if (i<rechts) qs(daten, i, rechts);          // Aufruf für "große Klasse"


}

/**
 * Diese Funktion bereitet den Aufruf der Rekursiven "qs"
 * Funktion vor.
 *
 * Der Parameter "daten" enthält die Daten, die sortiert
 * werden sollen.
 */
void quick_sort(int daten[][yl]) { // Quicksort vorbereiten
  int zaehler;

  zaehler = xl;
  qs(daten, 0, zaehler-1);
}

void ausgabe(){


    int i;
    int j;

    printf("Index \t Zufallszahl \n");
        for(i=0; i<xl; i++){

            for(j=1; j<yl; j++){
                printf("%d \t %d \n", daten[i][0]+1, daten[i][j]);
            }

        }
        printf("\n");

}

void generieren(){


    int i;
    int j;
    for(i=0; i<xl; i++){

        daten[i][0]=i;
        for(j=1; j<yl; j++){

            daten[i][j]=random()%500;
        }


    }


}

void zeit(){

    long int i;
    printf("\t Quicksort\n");
    for(i=10; i<=1000000; i*=10){
    xl=i;
    generieren();
    time_t vorher=time(NULL);
    quick_sort(daten);
    time_t nachher=time(NULL);
    printf("%d \t %d \n", i, (int)(nachher-vorher));


        }

}


int main(int argc, char **argv) {

    zeit();


      return 0;

} 
12/10/2013 20:44 Schlüsselbein#12
Um nochmal bisschen weiter zu klugscheißen: Die Wörter Heap und Stack sind nicht passend. Der Standard gibt nicht vor, wo die Variablen und Objekte letzendlich landen, sondern nur wie diese sich zu verhalten haben bezüglich ihrer Gültigkeit.
12/10/2013 20:54 Tasiro#13
Quote:
Originally Posted by MrSm!th View Post
Ein Array muss eine Compile-Zeit-Konstante als Größe haben, ergo kann er i ohnehin in keinem Fall nutzen, um das Array zu erzeugen.
Das ginge, wie du schon erkannt hast,nur auf dem Heap.
Ich dachte, in C gäbe es VLAs?

Quote:
Originally Posted by MrSm!th View Post
Übrigens ist es nicht korrekt, dass int notwendigerweise 32bit hat, da liegt der TE schon richtig.
Wenn er Werte bis zu 4 mrd speichern will, braucht er plattformunabhängig mindestens einen long. Int wird es auf den meisten Plattformen allerdings auch tun.
Vorzeichen beachten. Oder einfach stdint.h einbinden und uint_least32_t oder uint_fast32_t verwenden.

Quote:
Originally Posted by Schlüsselbein View Post
Um nochmal bisschen weiter zu klugscheißen: Die Wörter Heap und Stack sind nicht passend. Der Standard gibt nicht vor, wo die Variablen und Objekte letzendlich landen, sondern nur wie diese sich zu verhalten haben bezüglich ihrer Gültigkeit.
Und laut Standard heißen sie:
Quote:
Originally Posted by §6.2.4
There are four storage durations: static, thread, automatic, and allocated.
12/10/2013 21:11 Dr. Coxxy#14
Quote:
Originally Posted by Tasiro View Post
Ich dachte, in C gäbe es VLAs?
erst mit C99.
12/10/2013 21:32 Tasiro#15
Quote:
Originally Posted by Dr. Coxxy View Post
erst mit C99.
Wurde das mit C11 nicht wieder optional?
Page 1 of 2 1 2