[C] Quicksort Zeitmessung -> Dumping stack trace

Belur · 12/10/2013, 10:25

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

Dr. Coxxy · 12/10/2013, 12:22

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?

ilovenoodles · 12/10/2013, 15:54

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.

Belur · 12/10/2013, 17:52

Mit dem long int war ich mir nicht sicher

Hatte es erst auch als normales int und bin dann hierauf gestoßen.

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

Dr. Coxxy · 12/10/2013, 18:26

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.

Dr. Coxxy · 12/10/2013, 18:44

Quote:

Originally Posted by ilovenoodles

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.

ilovenoodles · 12/10/2013, 18:55

Und wie ich recht habe:

Ist global...

MrSm!th · 12/10/2013, 19:00

Quote:

Originally Posted by ilovenoodles

Und wie ich recht habe:

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

@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.

ilovenoodles · 12/10/2013, 19:35

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

Ü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

Dr. Coxxy · 12/10/2013, 19:36

Quote:

Originally Posted by ilovenoodles

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

was hältst du davon deine klappe zu halten und mal weniger blödsinn von dir abzusondern?

Belur · 12/10/2013, 20:24

Bevor das hier noch weiter ausartet poste ich mal meinen Quellcode, der allerdings ziemlich unübrsichtlich ist.
Erstsemester und so

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;

}

Schlüsselbein · 12/10/2013, 20:44

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.

Tasiro · 12/10/2013, 20:54

Quote:

Originally Posted by MrSm!th

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

Ü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

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.

Dr. Coxxy · 12/10/2013, 21:11

Quote:

Originally Posted by Tasiro

Ich dachte, in C gäbe es VLAs?

erst mit C99.

Tasiro · 12/10/2013, 21:32

Quote:

Originally Posted by Dr. Coxxy

erst mit C99.

Wurde das mit C11 nicht wieder optional?