struct nach elementen ordnen

SeppJ

Swordfish schrieb:

@SeppJ: Sollte die Vergleichsfunktion nicht einen negativen Wert bei lhs < rhs, 0 bei lhs == rhs und einen positiven Wert bei lhs > rhs liefern?

Ups, zuviel C++, wo die Vergleichsfunktion ein '<' sein soll und für C gar nicht nachgeschaut, was genau erwartet wird. Also:

int vergleiche_datum(const void *lhs, const void *rhs)
{
  struct datum *l = (struct datum*) lhs, 
    *r = (struct datum*) rhs;
  if (l->jahr < r->jahr) return -1;
  if (l->jahr > r->jahr) return 1;
  if (l->monat < r->monat) return -1;
  if (l->monat > r->monat) return 1;
  if (l->tag < r->tag) return -1;
  if (l->tag > r->tag) return 1;
  return 0;
}

Wutz

SeppJ schrieb:

Ups, zuviel C++,

Das stimmt.
Also:

int vergleiche_datum(const void *lhs, const void *rhs)
{
  const struct datum *l = lhs, *r = rhs;
  if (l->jahr < r->jahr) return -1;
  if (l->jahr > r->jahr) return 1;
  if (l->monat < r->monat) return -1;
  if (l->monat > r->monat) return 1;
  if (l->tag < r->tag) return -1;
  if (l->tag > r->tag) return 1;
  return 0;
}

woah ok, hab mir gedacht, dass ich das mir memcmp machen kann. Wenn aber die Elemente der struct integer sind, kann ich die Vergleichsfunktion nicht einfach für integer aufbauen?

SeppJ

cinder schrieb:

woah ok, hab mir gedacht, dass ich das mir memcmp machen kann. Wenn aber die Elemente der struct integer sind, kann ich die Vergleichsfunktion nicht einfach für integer aufbauen?

Zeig mal wie du das meinst.

da meine struct datum ja integer enthält hätt ich mir sowas als Vergleichsfunktion gedacht:

int comp(const int * a,const int * b)
{
  if (*a==*b)
    {
    return 0;
    }else
    if (*a < *b)
    {
        return -1;
    }else
      return 1;
}

SeppJ

Und Wasser brennt, weil es aus Wasserstoff und Sauerstoff besteht?

Swordfish

Wutz schrieb:

const struct datum *l = lhs, *r = rhs;

@cinder: Schau' Dir mal die Signatur des Funktionszeigers an, den qsort( ) für die Vergleichsfunktion verlangt...

alex2010

cinder schrieb:

hey
ich habe ein Programm geschrieben in welchen (unter anderem) daten(tag,monat,jahr) in eine struct gespeichert werden. Nun möchte ich diese nach dem Datum sortieren. Hab das ganze mit qsort versucht und komme einfach nicht weiter. hier mein Ansatz:
int int_cmp(const void *a, const void *b,list *liste)
{
elem *ia = (elem *)a; // casting pointer
elem *ib = (elem *)b;
return memcmp(ia,ib,liste->count);
}

qsort(tmp->year,tmp2->year,sizeof(elem),int_cmp);
bei liste->count handelt es sich um die Gesammtanzahl an Structelementen.

Ich hoffe jemand kann mir helfen
LG

Tja, beim Sortieren muß man auchmal beachten, daß wir nicht mehr 1980 schreiben, sondern 2012.

Und die Performance um den Faktor 10000 oder so zugenommen hat.

Mir wurde hier zwar schon unterstellt, daß ich keine Ahnung hätte aber was soll´s. Was kratzt es die deutsche Eiche, reibt sich an ihrem Stamm das Borstenvieh.

Die ganze Sortier-Algorithmen der 70er,80er Jahre sind entstanden aus dem Problem, daß man 640 KB Hauptspeicher zur Verfügung hatte, wovon das Programm das meiste belegte. Das kann man von der Performande her heute alles vergessen. Im Prinzip wurde früher so sortiert, daß man zwischen Rechen- und Massenspeicher switchen mußte, was den Algorithmus recht komplex macht.

MIt einem SPeicher von 4 GIgabyte kann man es sich leisten, ganz PRIMITIV zu sortieren, und die Performance liegt bei 10.000 Datensätzen im Bereich von Sekundenbruchteilen.

Ich traue mich, hier eine ganz primitive Sortierroutine vorzustellen:

1. Kopiere die ganze Datei in den Rechenspeicher als dynamische Liste.

2. Sieh eine zweite dynamische Liste vor, die dann die sortierten Element enthalten wird.

3. Lies alle Datensätze solange und immer wieder bis Abbruchbedingung erfüllt ist und finde bei jedem Durchgang das das kleinste/größte

4. Füge das gefundene kleinste/größte in die Kopie der Liste ein

5. Lösche das gefundene aus der 1. Liste oder überschreibe den Inhalt

6. Bis, Abbruchbedinung, alle Elemente gelöscht oder überschrieben sind.

7. Kopiere die sortierte Liste an den Speicherort der unsortierten Liste zurück.

Das ist kein Bubblesort und gar nix und dauert bei 10.000 Datensätzen Sekundenbruchteile.

LG Alex

SeppJ

Erklär mal bitte den Vorteil dieses gequirlten Unsinns gegen qsort.

alex2010

SeppJ schrieb:

Erklär mal bitte den Vorteil dieses gequirlten Unsinns gegen qsort.

Also erstmal:

Ich hab mich hier nicht im Forum angemeldet, um mir Beschimpfungen anzuhören.

KANN JA WOHL NICHT WAHR SEIN!

Man wird hier beschimpft mit gequirltem Unsinn.

Wenn das hier so weiter geht, bin ich ganz schnell wieder weg.

Außerdem hab ich genau erklärt, was da Sache ist: SEKUNDENBRUCHTEILE.

Ich setz solchen Leuten, die hier persönliche Beleidigungen ansetzen, einfach mal Quellcode entgegen. Kannst ja mal schauen, was an dem Code schlecht sein soll. Bzw. deine C-Kenntnisse etwas auffrischen obwohl das ist nicht mehr als ein Prototyp, der noch zu optimieren wäre. Im übrigen ist er historisch, kannst du, wenn du Ahnung hast, an dem cast-Operator erkennen. Aber hast du Ahnung?

Er sortiert 10000 Datensätze von ca. 150 Byte in Sekundenbruchteilen.

So what?

void sortiere_buchungsdatei_chronologisch()
{
 int anz_ds;    
 struct datei_ds
 {
     strc_bsatz data;
     datei_ds *next;              
 };    

 strc_bsatz buffer;
 datei_ds *listenkopf_1=NULL;    
 datei_ds *neues=NULL;
 datei_ds *laufzeiger=NULL;
 datei_ds *laufzeiger2=NULL;
 datei_ds *kleinstes=NULL;

 datei_ds *listenkopf_2=NULL;
 datei_ds *liste2_ende=NULL;
 FILE *bdp;

 bdp=fopen(dn_buchungen_bin,"rb");
 if (bdp==NULL)return;
// fseek(bdp,(long)-1*sizeof(strc_bsatz),SEEK_END);   
 fseek(bdp,(long)-1*sizeof(strc_bsatz),SEEK_END);   
 anz_ds=ftell(bdp)/sizeof(strc_bsatz);
 if (anz_ds<=1){fclose(bdp); return; } // leere Datei oder 1 DS

// Schritt 1: Datei komplett auslesen

 fseek(bdp,0,SEEK_SET);  // dateizeiger auf den Anfang zurücksetzen
 while (fread(&buffer,sizeof(strc_bsatz),1,bdp)==1) // datei in dynamische Liste kopieren
 {
   neues = (datei_ds*) malloc(sizeof( datei_ds));
   if (neues==NULL){fclose(bdp); meldung("Fehler dynamische Liste");return;}
   if (listenkopf_1==NULL) listenkopf_1=neues; // Kopf der Liste markieren
   else laufzeiger->next=neues; // an ndie Liste anhaengen

   neues->next=NULL;  
   laufzeiger=neues;
   laufzeiger->data=buffer;  // daten aus Datei uebernehmen

  } // while datei auslesen
  fclose(bdp);

// Schritt 2: daten durch umkopieren in 2. Liste sortieren:

   int ende=NEIN;
   do
   {
      kleinstes=listenkopf_1;             
      laufzeiger=listenkopf_1;
      while (laufzeiger->next!=0)
      {
         laufzeiger=laufzeiger->next;
          if (datindex(laufzeiger->data.datum)<datindex(kleinstes->data.datum))kleinstes=laufzeiger; 
      }  // kleinstes gefunden                
     if (strcmp(kleinstes->data.datum,"99.99.9999")==0) ende=JA; // ==0 sind identisch= JOB IS DONE
     else
     {
         neues = (datei_ds*) malloc(sizeof( datei_ds));
         if (neues==NULL){meldung("Fehler dynamische Liste 2");return;}
         if (listenkopf_2==NULL) listenkopf_2=neues;
         else liste2_ende->next=neues;
         neues->next=NULL;
         liste2_ende=neues;
         neues->data=kleinstes->data; // Daten kopieren
         sprintf(kleinstes->data.datum,"99.99.9999");
     }
  }  while (ende==NEIN);

  // Schritt 3: sortierte Liste in Datei zurückkopieren
  laufzeiger=listenkopf_2; // auf sortierte Liste setzen
  bdp=fopen(dn_buchungen_bin,"wb");
  if (bdp==NULL) {meldung("Kann Datei nicht oeffnen");return;}
  do
  {
      fwrite(&laufzeiger->data,sizeof(strc_bsatz),1,bdp);  
      if (laufzeiger->next!=NULL)laufzeiger=laufzeiger->next;
  }  while (laufzeiger->next!=NULL); // Listenende erreicht   

  fclose(bdp);

  // Schritt 4: Speicher für die beiden Listen wieder freigeben:

  do
  {
        laufzeiger=listenkopf_1;
        laufzeiger2=listenkopf_2;        
        if (listenkopf_1->next!=NULL) listenkopf_1=listenkopf_1->next;     
        if (listenkopf_2->next!=NULL) listenkopf_2=listenkopf_2->next;     
        free(laufzeiger);
        free(laufzeiger2);                        

   } while (listenkopf_1->next!=NULL||listenkopf_2->next!=NULL);         
    clrscr();        
    meldung("Datei wurde chronologisch sortiert");         

} // fu

Und File-I/O und malloc ist schneller als ein paar Zeiger zu verbiegen?
Ich möchte kein Programm von dir haben wollen.

Auch von mir:
Du schreibst Unsinn. Nicht nur in diesem Thread.

alex2010

DirkB schrieb:

Und File-I/O und malloc ist schneller als ein paar Zeiger zu verbiegen?
Ich möchte kein Programm von dir haben wollen.

Auch von mir:
Du schreibst Unsinn. Nicht nur in diesem Thread.

Mit so blöden Sprüchen ist nichts gesagt.

Was willst du denn sagen?

Daß man Sekundenbruchteile noch in Bruchteile von Sekundenbruchteilen umformen kann?

Und wenn ja wie oder was? (LACH)

Anstatt hier herumzuschwätzen, setz doch mal Code rein.

Code ist die Basis.

Das größte Problem ist, dass die Funktion im Fehlerfall Speicher verliert - so was verbietet sich einfach.

Direkt dahinter kommt, dass der Algorithmus quadratisch skaliert, im Gegensatz zu n * log(n) bei Quicksort. Man könnte diese Vorgehensweise höchstens dann verteidigen, wenn man vorher weiß, dass die Eingabedaten schon annähernd sortiert ankommen. Ferner entsteht ein riesiger Overhead dadurch, dass du dich für kleinste Speichermengen dauernd an den Heap wendest - zweimal pro Element, und wenn du da vernünftige Fehlerbehandlung reinpatchst, wird diese Fummelei den größten Aufwand bedeuten.

Nach Bugs hab ich jetzt noch nicht gekuckt. Kann ich vielleicht eine Beispieldatei kriegen, um das mal auszuprobieren?

SeppJ

SeppJ schrieb:

Erklär mal bitte den Vorteil dieses gequirlten Unsinns gegen qsort.

alex2010 schrieb:

...Schlechter Code...leeres Geschwätz...eingeschnapptes Verhalten...ein paar falsche Aussagen...

Zusammenfassend: Deine Funktion ist also langsamer, hat Fehler und ist nicht auf große Datenmengen anwendbar. Und du erklärst das sogar selber so. Wieso war der Vorschlag doch gleich kein Blödsinn?

Und wenn du eine Kritik an deinen Aussagen persönlich nimmst: Willkommen im Internet.

alex2010

seldon schrieb:

Das größte Problem ist, dass die Funktion im Fehlerfall Speicher verliert - so was verbietet sich einfach.

Direkt dahinter kommt, dass der Algorithmus quadratisch skaliert, im Gegensatz zu n * log(n) bei Quicksort. Man könnte diese Vorgehensweise höchstens dann verteidigen, wenn man vorher weiß, dass die Eingabedaten schon annähernd sortiert ankommen. Ferner entsteht ein riesiger Overhead dadurch, dass du dich für kleinste Speichermengen dauernd an den Heap wendest - zweimal pro Element, und wenn du da vernünftige Fehlerbehandlung reinpatchst, wird diese Fummelei den größten Aufwand bedeuten.

Nach Bugs hab ich jetzt noch nicht gekuckt. Kann ich vielleicht eine Beispieldatei kriegen, um das mal auszuprobieren?

Im Fehlerfall Speicher verlieren? 100 Jahre dauert es, bis ich 8 GB Speicher gefressen habe, mit diesem Programm, von 2000 Datensätzen, aber nur mal zur Orientierung, interessehalber: ERKLÄR MAL.

Zweitens ist es ja so, daß wir nicht die Anflugdaten eines Kampfflugzeuges in ECHTZEIT berechnen, und was an einem

SORTIERALGORITHMUS

auszusetzen ist, der seinen Job in

BRUCHTEILEN VON SEKUNDEN

erledigt, müßte anhand der REALEN ERLEBNISDATEN DER WELT DES JAHRES 2012 erstmal erklärt werden.

Performance und Optimierung immer und jederzeit, aber 0.x Sekunden erzwingen das nicht.

Vielleicht:

Wenn wir von Beschimpfungen mal übergehen zu sachlicher Aussage, hätten auch die Mitleser was davon,

REIN THEORETISCH,

nicht wie man 0.05 Sekunden in 0.04 Sekunden verwandelt (das eine reicht, das andree ist in 100 Jahren noch genug), sondern,

WORAN ICH AUCH IMMER INTERESSE HABE:

Wie man sauber programmiert.

That´s it.

LG Alex

alex2010

Und ja, sie ist quadratisch.

Bei 1000 Datensätzen ist der Zugriff 1000*1000 = 1 Mio.

So what? Was sind 1 Mio Datenzugriffe?

Sekundenbruchteile.

Worüber reden wir hier?

Daß der Ferrari, wenn man aus dem Kofferraum den Kasten Bier rausnimmt, noch schneller beschleunigt?

LG Alex

alex2010

DirkB schrieb:

Und File-I/O und malloc ist schneller als ein paar Zeiger zu verbiegen?
Ich möchte kein Programm von dir haben wollen.

Auch von mir:
Du schreibst Unsinn. Nicht nur in diesem Thread.

Du bist ja wirklich ganz schlau.

File i/o denken wir uns weg. Für uns ist das File sozusagen nicht vorhanden, die Daten hängen frei zugänglich in der Luft? Wir atmen sie ein wie Sauerstoff, oder was wolltest du sagen?

Und seit wann hat malloc() was mit der Rechenzeit zu tun?

Wirklich witzig.

So, da Code scheinbar König ist - ich habe das mal zusammengestrichen. Ich kann den Kram hier natürlich nicht testen, weil mir große Teile des Drumherums fehlen, also ist das mehr als Kladde zu verstehen. Ich bitte kleinere Fehler deshalb zu entschuldigen.

So etwa würde ich das anfangen:

#include <stdlib.h>

int compare_strc_bsatz(void const *lhs_p, void const *rhs_p) {
  strc_bsatz const *lhs = (strc_bsatz const *)lhs_p;
  strc_bsatz const *rhs = (strc_bsatz const *)rhs_p;

  return datindex(lhs->data.datum) - datindex(rhs->data.datum);
}

void sortiere_buchungsdatei_chronologisch()
{
  FILE *bdp;
  size_t anz_ds;
  size_t elem_read;
  strc_bsatz *data;

  bdp = fopen(dn_buchungen_bin,"rb");
  if(bdp == NULL) return;

  fseek(bdp, -1 * (long) sizeof(strc_bsatz), SEEK_END);
  anz_ds = ftell(bdp) / sizeof(strc_bsatz);

  if(anz_ds <= 1) {
    fclose(bdp);
    return;
  }

  fseek(bdp, 0, SEEK_SET);
  data = malloc(sizeof(strc_bsatz) * anz_ds);
  if(data == NULL) return;
  elem_read = fread(data, sizeof(str_bsatz), anz_ds, bdp);
  fclose(bdp);

  if(elem_read == anz_ds) {
    qsort(data, elem_read, sizeof(strc_bsatz), compare_strc_bsatz);
    bdp = fopen(dn_buchungen_bin, "wb");
    fwrite(data, sizeof(strc_bsatz), elem_read, bdp);
    fclose(bdp);
  }

  free(data);
}

Was den Rest angeht: Bitte beruhige dich zunächst wieder; ich lasse mich nicht gern anschreien.

Speicherlecks sind kein Kavaliersdelikt. Als Programmierer muss man darauf gefasst sein, mal in Situationen zu geraten, in denen die eigenen Programme nicht nur 150 Kilobyte Daten verarbeiten müssen, nicht nur zehn Sekunden am Stück laufen und nicht nur auf PCs. Zumal dieser Thread nicht mit der Diskussion deines Programms, das vielleicht wirklich mit begrenzten Parametern zurechtkommt, begonnen hat. Allerdings: auch wenn in einem konkreten Fall die Anforderungen begrenzt sind, läuft heute auf einer Maschine nicht mehr nur ein Programm zur selben Zeit, und ich gebe zu bedenken, dass dein Programm gerade dann Speicher wegwirft, wenn dieser eh schon knapp ist. Auch zeigt die Erfahrung, dass Anforderungen im Laufe der Zeit mal wachsen können, und - sei ehrlich, bist du der Ansicht, dass du dich durch dieses Listengewurstel in zwei Jahren noch durchfinden wirst?

Übrigens sprachst du anfangs noch von 10000 Datensätzen, da sind wir schon in der Größenordnung von 100 Millionen Vergleichen. Mit Stringauseinanderklamüserei und Sprüngen in die Wallachei (das gibt cache-misses ohne Ende, soviel ist mal klar). Das ist ja das Problem bei quadratischer Skalierung - der Aufwand steigt schnell stark an.

Mit deiner Hardware bist du im Jahr 2012 angekommen.
Nur mit deinem Datenvolumen bist du in den 1980ern hängengeblieben.

alex2010 schrieb:

Und seit wann hat malloc() was mit der Rechenzeit zu tun?

Okay, jetzt bin ich überzeugt, dass wir es hier mit einem Troll zu tun haben.