2D Array sortieren

simsa

Hallo,

danke für Eure Unterstützungen; da es wohl mit double **xy ein Problem gibts,
wollte ich hier mal meine Einleseroutine für das Einlesen zeigen:

//
// read x- and y-values
//
double **readXY (char *fname, int *data_length) {

	int
		i = 0,
		pos = 0L,
		lines = 0;

	double
		*x, *y;

	FILE
		*FileIn = fopen(fname, "r");

	if (FileIn == NULL) { 
		printf("ERROR: readXY() -> FileIn.\n");
		exit(EXIT_FAILURE);
	} else {
		while (pos != EOF) {
			pos = fgetc(FileIn);
			if (pos == '\n') 
				lines++;
		}

		x = (double *) malloc(lines * sizeof(double));
		if (x == NULL) {
			printf("ERROR: readXY() -> malloc of x.\n");
			exit(EXIT_FAILURE);
		}

		y = (double *) malloc(lines * sizeof(double));
		if (y == NULL) {
			printf("ERROR: readXY() -> malloc of y.\n");
			exit(EXIT_FAILURE);
		}

		fseek(FileIn, 0L, SEEK_SET);

		while (i < lines && fscanf(FileIn, "%lf %lf", &x[i], &y[i]) == 2)
			i++;

		fclose(FileIn);
	}

	*data_length = lines;

	double **xy;

	xy = malloc(2 * sizeof(double));
	if (xy == NULL) {
		printf("ERROR: readXY() -> malloc of xy.\n");
		exit(EXIT_FAILURE);
	}

	xy[0] = x;
	xy[1] = y;

	return xy;

}

Vielleicht könnt ihr mir da einen besseren Weg zeigen (ich hatte es damals
auf die schnelle mit double **xy gemacht und seit dem verwende ich es).

Viele Grüße,
simsa

SeppJ

Werden wir doch mal objektorientiert. Die Quelle für die Daten ist eine Datei, kein Dateiname. Der Aufrufer sollte also die Datei übergeben, nicht ihren Namen. So steht ihm frei, wie die Datei geöffnet wird oder ob es überhaupt eine richtige Datei ist oder irgendein anderes Ding, dass sich wie eine Datei verhält. Ebenso dein Datenfeld. Das Einlesen ist eine Aktion auf einem Datenfeld, keine Aktion, die ein Datenfeld erzeugt. Oder falls sie doch ein neues Datenfeld erzeugt (durchaus legitim), dann behält sie die Kontrolle darüber und gibt sie nicht an die Anwendungsebene. So können die Datenfeldfunktionen frei entscheiden, was richtig und gut ist, ohne dass sich der Benutzer darum kümmern muss. So kann man solche Details dann auch einfach mal ändern (zum Beispiel ein anderes Sortierverfahren einbauen, ohne dass es jemand mitbekommt ).

Hier ist ein (noch) primitives, aber ausbaufähiges, Grundgerüst nach diesem Konzept:

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

typedef struct
{
  double pair[2];
} double_pair;

typedef struct
{
  double_pair *begin;
  double_pair *end;
  double_pair *end_reserved;
} dynamic_pair_array;

void insert_dpa(dynamic_pair_array *this, double v0, double v1)
{
  if (this->end_reserved - this->end == 0) // reallocation required
    {
      size_t old_size = this->end - this->begin;
      size_t new_size = (old_size + 1) * 1.5;
      this->begin = realloc(this->begin, new_size * sizeof(*this->begin));
      this->end = this->begin + old_size;
      this->end_reserved = this->begin + new_size;
    }

  this->end->pair[0] = v0;
  this->end->pair[1] = v1;
  ++this->end;
};

dynamic_pair_array construct_dpa_from_file(FILE *file)
{
  dynamic_pair_array this;
  this.begin = this.end = this.end_reserved = NULL;
  double val1, val2;
  while(fscanf(file, "%lf %lf", &val1, &val2) == 2)
    {
      insert_dpa(&this, val1, val2);
    }
  return this;
}

void destroy_dpa(dynamic_pair_array* this)
{
  free(this->begin);
}

void print_dpa(const dynamic_pair_array* this, FILE* file)
{
  double_pair *current;
  for (current = this->begin; current != this->end; ++ current)
    {
      fprintf(file, "%f %f\n", current->pair[0], current->pair[1]);
    }
}

int main()
{
  FILE *file = fopen("test.dat", "r");
  dynamic_pair_array data = construct_dpa_from_file(file);
  fclose(file);
  print_dpa(&data, stdout);
  destroy_dpa(&data);
  return 0;
}

Sieht doch gleich viel sauberer aus. Sortieren habe ich jetzt bewusst noch nicht reingepackt, ich will schließlich nicht alles vormachen.

Die Speicherallokationen sind noch ein bisschen wild, da ich die Rückgabewerte nicht prüfe. Ist nicht die feine Art, aber ich wollte es für das Beispiel nicht übertreiben.

Was man beobachten sollte:
1. Wie die Datenstruktur intern funktioniert, bekommt der Anwender (main) gar nicht mit. Er muss bloß den Konstruktor aufrufen und am Ende den Destruktor. Dazwischen kann er die Zugriffsfunktionen nutzen wie er möchte und braucht sich um nichts weiter zu kümmern.
2. Jede Funktion hat eine klar abgegrenzte Aufgabe (ok, der Konstruktor macht hier ein bisschen viel, aber das war einfach die Problemstellung :p ). Keinerlei Wiederholung. Der Konstruktor braucht nicht wissen, wie man Werte einfügt, das macht das insert (das übrigens auch gerne der Anwender selber aufrufen darf, wenn er möchte!). Dadurch bleibt jede Funktion übersichtlich. Man hätte noch den Elementzugriff kapseln können, aber da ich dies nicht wirklich viel genutzt habe, habe ich mir das für den Beispielcode gespart.

knivil

@simsa: Bitte benutze Codetags! Wenn du nicht weisst wie, dann druecke auf die Zitierentaste und schau dir die Beitrage im Editor an.

FILE *file = fopen("test.dat", "r");

Ein "rb" ist besser, weil binaer.

SeppJ

knivil schrieb:

FILE *file = fopen("test.dat", "r");
Ein "rb" ist besser, weil binaer.

Aber entweder sind die Einträge formatiert (Der TE benutzt scanf) und es ist egal, oder das Einlesen selber ist falsch (wenn die Daten binär vorliegen).

knivil

fscanf(FileIn, "%lf %lf", &x[i], &y[i])

Gut scheint wohl doch nicht binaer zu sein. Einlesen habe ich ignoriert.

da es wohl mit double **xy ein Problem gibts,
wollte ich hier mal meine Einleseroutine für das Einlesen zeigen

So rein prinzipiell nicht. Ist aber trotzdem schlecht.

simsa

Hallo SeppJ,

danke für Deine Mühe, aber so komploziert wollte ich die Einleseroutine doch
nicht machen/haben.

Ja, mich hätte lieber das sortiere mehr interessiert.

Beste Grüße,
simsa

simsa

Hi knivil,

die Dateien sind binär. Ich lese sie aus, lege sie in eine externe Datei ab, lese
sie wieder ein und dann arbeite ich mit Dezimalzahlen weiter. Das Auslesen wird
von einem anderen C-Programm gemacht.

Ich rufe die Programme in einer Shell-Datei hintereinander auf.

Mein Ziel ist, alle 'einzelne' Programme in ein einziges Programm zusammenzuführen.

Leider hatte ich die Programme vor 3 Jahren geschrieben...

Zwei Fragen noch:

Warum ist das mit dem Einlesen so 'kompliziert' gemacht?
Klar, [quote]das Einlesen ist eine Aktion auf einem Datenfeld[/quote]
Blöd wird es dann nur, wenn man eine bestimmte Zeile haben möchte.

Ich dachte diese Schreibweise [quote]this->end[/quote] sollte man nicht
mehr benutzen, stattdessen [quote]this.end[/quote].

Ich habe mein Code immer zwischen

und

geschrieben, aber
nichts ist passiert.

Grüße,
simsa

SeppJ

Betreffend Formatierungen deiner Beiträge: Du hast anscheinend BB-Code deaktivert. Ist ein klickbares Kästchen unter dem Editfenster.

SeppJ

simsa schrieb:

danke für Deine Mühe, aber so komploziert wollte ich die Einleseroutine doch
nicht machen/haben.

Findest du meine 26 Zeilen zum Einlesen wirklich kompliziert . Du brauchst dafür selber 60 Zeilen, in denen ich ein ganzes Programm mit Beispielausgabe habe. Wohlgemerkt: Ein funktionierendes Programm, ohne Speicherlöcher. Dein Programm wimmelt davon.

die Dateien sind binär. Ich lese sie aus, lege sie in eine externe Datei ab, lese
sie wieder ein

Dein Einlesen passt nicht dazu.

und dann arbeite ich mit Dezimalzahlen weiter.

Dezimalzahlen? Was meinst du damit?

Ich rufe die Programme in einer Shell-Datei hintereinander auf.

knivil hat Recht:

knivil schrieb:

Wahrscheinlich brauchst du kein C-Programm, sondern kannst einfach kleine Linuxprogramme mittels Pipes verknuepfen.

Warum ist das mit dem Einlesen so 'kompliziert' gemacht?

Was findest du daran kompliziert? Hast du die Technik noch nie gesehen?

Lesen ist wirklich nur dies:

while(fscanf(file, "%lf %lf", &val1, &val2) == 2)
    {
      insert_dpa(&this, val1, val2);
    }

Wert hinten dranhängen ist das insert, welches für sich auch nicht kompliziert ist. Dafür spare ich mir solche fehleranfällige und umständliche Sachen wie:

while (pos != EOF) {
pos = fgetc(FileIn);
if (pos == '\n')
lines++;
} 
x = (double *) malloc(lines * sizeof(double));
// ... 
y = (double *) malloc(lines * sizeof(double));
// ...
fseek(FileIn, 0L, SEEK_SET);

while (i < lines && fscanf(FileIn, "%lf %lf", &x[i], &y[i]) == 2)
i++;
// ...
*data_length = lines;
double **xy;
xy = malloc(2 * sizeof(double)); 
// ...
xy[0] = x;
xy[1] = y;

return xy;

Findest du das wirklich einfacher?

Das beste ist: Alles ist total unabhängig voneinander, man kann leicht an einer Stelle Features einbauen, ohne irgendwoanders etwas ändern zu müssen. Zum Beispiel:

Blöd wird es dann nur, wenn man eine bestimmte Zeile haben möchte.

Da wird gar nichts blöd. Was sollte da dran blöd werden?

Ich dachte diese Schreibweise

this->end

sollte man nicht
mehr benutzen, stattdessen

this.end

.

Ich weiß nicht, wo du das her hast, aber es ist Unsinn. Die beiden Schreibweisen bedeuten jeweils ganz was anderes und sind nicht austauschbar.

simsa

Hallo Sepp,

ich komme nochmal kurz zum Einlesen/Auslesen, was hier etwas zur Irritation
geführt hat (sorry dafür ;)):

Vorweg, die Namen, die ich jetzt nenne sind fiktional.

Aus meiner Simulation bekomme ich eine binäre Datei. Wir nennen diese Datei
mal binaer.xtc. Mit dem Programm readbin.c lese ich die binäre Datei aus und
schreibe die Zahlenwerte (Dezimalzahlen/Dezimalziffern) in eine für 'Menschen'
lesbare Datei, nennen wir diese einfach mal lesbar.xvg.

Mit dem Programm readXY.c lese ich nun lesbar.xvg 'wieder' ein und verarbeite
sie.

Nun zum Kommentar, warum ich dafür keine Shell Programme benutzten möchte:

In der Datei lesbar.xvg sind zwei Spalten, nennen wir die erste Spalte x-Spalte
und die zweite Spalte y-Spalte.

Es kommt vor, dass in der x-Spalte doppelte Einträge vorkommen, so dass ich
über die entsprechen y-Werte mitteln muss (je nachdem, entweder einfaches mitteln, median, oder runnig average; hängt mit der Steigung von zwei Punkten
zusammen ab; Ist eigentlich noch etwas komplizierter...).

Deshalb will ich nicht in die Shell ausweichen, weil ich auch so mögliche
Fehler minimieren möchte, die sich evtl. einschleichen würden.

Dann noch zu den höheren Datentypen Sache:

Also, wenn ich mir folgedes definiere:

typedef struct NEWTYPE {
 int A;
 double B;
 char *C;
} newtype;

dann kann ich doch ganz einfach mit

newtype test;

Werte für

test.A = 120;
test.B = 1.2;
test.C = "Aha";

zuweisen bzw. auch zugreifen.

Achso, dann noch eine kleine Bitte für zukünftige Einleseroutinen:

Ich bin kein wirklicher 'Fan' von objektorientierter Programmierung.
Dafür schreibe ich lieber Funktionen und versuche in der Funktion auch
weitgehendst Memory-Leaks zu vermeiden, sprich nicht mehr gebrauchten
Speicher wieder freigeben.
Leider kann ich in meiner 'Einleseroutine' readXY(char *fname, int length)
den Speicher für xy freigeben, da sonst ja ich nichts 'bekomme'.

Wie würdet Ihr das regeln?

@SeppJ: Danke nochmal für den Tipp mit dem Kästchen

Vielen Dank und viele Grüße,
simsa

SeppJ

simsa schrieb:

Dann noch zu den höheren Datentypen Sache:

Also, wenn ich mir folgedes definiere:
typedef struct NEWTYPE {
 int A;
 double B;
 char *C;
} newtype;
dann kann ich doch ganz einfach mit
newtype test;
Werte für
test.A = 120;
test.B = 1.2;
test.C = "Aha";
zuweisen bzw. auch zugreifen.

Ja. Aber änder bloß nicht test.C, auch wenn der Compiler es prinzipiell erlaubt(aus historischen Gründen). Du meinst wohl eher const char *C;

Ich bin kein wirklicher 'Fan' von objektorientierter Programmierung.
Dafür schreibe ich lieber Funktionen und versuche in der Funktion auch
weitgehendst Memory-Leaks zu vermeiden, sprich nicht mehr gebrauchten
Speicher wieder freigeben.
Leider kann ich in meiner 'Einleseroutine' readXY(char *fname, int length)
den Speicher für xy freigeben, da sonst ja ich nichts 'bekomme'.

Wie würdet Ihr das regeln?

Genau dafür hat man dieses Prinzip erfunden. Einzelne abgeschlossene Funktionen sind ja schön und gut, aber wenn man mal Daten mit logischem Anhängsel (Nötigkeit des free) aus einer Funktion raus oder reintragen muss, dann ist dieses verpacken in Objekte eine bewährte Technik. Praktisch alle Software ist heutzutage so programmiert. Auch in C.
Ohne kommt man sehr schnell durcheinander und endet mit Speicherlöchern und inkonsistentem Programmzustand.

Es gibt theoretisch auch andere Ansätze, aber das wäre für diese Aufgabe eher eine Kuriosität, um mal zu zeigen, dass es geht. Oder du kannst es natürlich auch ganz klassisch prozedural machen, so wie du es vor hattest. Bloß schreit das eben nach Fehlern, wie du hoffentlich bemerkt hast.

Du kannst den objektorientierten Ansatz natürlich auch gehörig abspecken. Ein

double (*d)[2];

als Objekt tut es gewiss auch, dann gibst du das an eine passende Leseroutine und eine passende Freigaberoutine. Aber du verlierst dabei so einige der Vorteile, zum Beispiel die Trennung der Funktionen und insgesamt wird alles viel unflexibler. Vor allem, da ich dir schon vorgemacht, wie es mit geringem (eher sogar weniger) Aufwand besser ginge.

simsa

Nunja, ich will doch an mein double **xy und readXY(...) festhalten, bis ich
mir die Zeit nehme und es sauberer umschreibe.

Daher wäre ich Euch sehr dankbar, wenn ihr mir zeigen könntet, wie das mit
dem qsort und dem double **xy am besten geht.

Beste Grüße und einen schönen Abend noch,
simsa

SeppJ

Kannst du denn irgendetwas mit qsort sortieren? Wenn ja: Wo ist das Problem hier? Wenn nein: Da liegt das Problem! Dann musst du erst einmal lernen, wie man Datentypen über void* abstrahiert. Hast du dir denn in den letzten 8 Stunden mal ein paar Beispiele zu qsort angesehen?

simsa

Hallo SeppJ,

Ja, ich habe schon mit qsort sortiert, aber nur 1D Arrays.

Mit 2D Arrays habe ich da Schwierigkeiten, weil ich nicht ganz genau weiß, wie die 'Vergleichsfunktion' aussehen soll,
dass wenn doppelte x-Einträge vorkommen, dann die doppelten x-Einträge nach der y-Spalte sortiert werden sollen
(entweder absteigend oder aufsteigend).

Ich hatte mir heute früh noch mal dein Code zum Einlesen angeguckt. Dazu habe ich noch zwei Fragen:

In deiner insert_dpa() Funktion hast du eine Zeile mit

size_t new_size = (old_size + 1) * 1.5;

stehen. Wieso multiplizierst du noch mit 1.5?

Dann noch eine Frage zum

typedef struct
{
  double_pair *begin;
  double_pair *end;
  double_pair *end_reserved;
} dynamic_pair_array;

Sollen *begin, *end und *end_reserved die Indizes des Array's sein?
Falls ja, warum verwendet man nicht lieber "int" dafür?

Vielen Dank schonmal für Deine Hilfe.

Grüße,
simsa

simsa schrieb:

Mit 2D Arrays habe ich da Schwierigkeiten, weil ich nicht ganz genau weiß, wie die 'Vergleichsfunktion' aussehen soll,
dass wenn doppelte x-Einträge vorkommen, dann die doppelten x-Einträge nach der y-Spalte sortiert werden sollen
(entweder absteigend oder aufsteigend).

Wie Vergleichst du denn Wörter? Wenn der erste Buchstabe unterschiedlich ist, kannst du schon entscheiden. Was machst du aber wenn die gleich sind?

Du musst doch eh eine eigene Vergleichsfunktion schreiben.

Wenn du weißt wie ein Array in C aufgebaut ist, ist es kein Problem mehr.
Der ganz rechte Index wechselt am häufigsten. Also stehen x- und y-Werte immer paarweise im Speicher.
Somit hast du eigentlich auch nur noch ein 1D-Array

simsa

Hallo,

ich habe vorhin wieder mit dem sortieren von einem 2D array gekämpft.

Diesmal habe ich nicht direkt eine Datei eingelesen, sondern mir ein kleines
Array mit 'sinnlosen' Zahlen erstellt.

Mein Code sieht so aus:

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

typedef struct {
	double x;
	double y;
} data2d;

int
comp (const void *p1, const void *p2)
{
	if (*(data2d*)p1.x <  *(data2d*)p2.x) return -1;
	if (*(data2d*)p1.x == *(data2d*)p2.x)
	{
		if (*(data2d*)p1.y <  *(data2d*)p2.y) return -1;
		if (*(data2d*)p1.y == *(data2d*)p2.y) return 0;
		if (*(data2d*)p1.y >  *(data2d*)p2.y) return 1;
	}
	if (*(data2d*)p1.x >  *(data2d*)p2.x) return 1;
}

int
main (int argn, char *argv[])
{

	int i = 0;
	data2d *xy = NULL;
	xy = (data2d *) calloc(10, sizeof(data2d));

	xy[0].x = 1.2;		xy[0].y = 1.019;
	xy[1].x = 2.02;		xy[1].y = 33.98;
	xy[2].x = 3.25;		xy[2].y = 321.2;
	xy[3].x = 6.8;		xy[3].y = 105.1;
	xy[4].x = 5.11;		xy[4].y = 78.77;
	xy[5].x = 3.42;		xy[5].y = 658.5;
	xy[6].x = 3.12;		xy[6].y = 688.8;
	xy[7].x = 21.2;		xy[7].y = 1.081;
	xy[8].x = 100.2;	xy[8].y = 132.4;
	xy[9].x = 19.2;		xy[9].y = 1.157;

	printf("before qsort()\n");
	printf("==============\n");
	for (i=0; i<10; i++)
		printf("xy[%d].x = %.3f   xy[%d].y = %.3f\n", i, xy[i].x, i, xy[i].y);

	qsort(xy, 10, sizeof(data2d), comp);

	printf("after qsort()\n");
	printf("==============\n");
	for (i=0; i<10; i++)
		printf("xy[%d].x = %.3f   xy[%d].y = %.3f\n", i, xy[i].x, i, xy[i].y);

	return 0;

}

Leider funktioniert da was nicht ganz. Wäre euch sehr dankbar, wenn ihr
drüber gucken könntet.

Beste Grüße,
simsa

Wutz

Niemals double-Werte mittels == auf Gleichheit prüfen, das bringt nur Unglück.

http://ideone.com/EGXyKE

SeppJ

Was heißt denn, "funktioniert nicht ganz"? Bitte präzise Fragen stellen und präzise Problembeschreibungen geben!

Compiliert das überhaupt? In Zeile 13 ff. hast du lauter Syntaxfehler, weil du den Zeiger nicht richtig dereferenzierst:
http://en.wikipedia.org/wiki/C_operator_precedence#Operator_precedence
Also entweder richtig klammern oder besser gleich den Operator -> benutzen.

Weiter habe ich jetzt nicht geguckt.

Noch ein alter Trick für die Vergleichsfunktion, um dir die tausend Casts zu sparen (die du übrigens auch nicht const-korrekt durchgeführt hast ):

int comp_mein_datentyp(const void* left, const void *right)
{
  const mein_datentyp *lhs = left, *rhs = right;

  // Hier ganz entspannt mit lhs und rhs arbeiten.
}

P.S.: Außerdem hast du eventuell undefiniertes Verhalten, da es keinen Rückgabewert deiner Funktion gibt, wenn keine der Bedingungen zutrifft. Dieser Fall kann bei dir eintreten! Beispiel: NaN.

simsa

@SeppJ: danke danke danke

@Wutz: danke danke danke danke

Beste Grüße,
simsa

simsa

Hallo Wutz,

eine kleine Frage noch zu deinem sehr hilfreichen Link:

Ich habe noch eine Frage bzgl. deiner Vergleichsfunktion:

int
comp (const void *p1, const void *p2)
{
    const data2d d1 = *(const data2d*)p1;
    const data2d d2 = *(const data2d*)p2;
    double x1 = d1.x,y1 = d1.y,x2 = d2.x, y2 = d2.y;

    if( x1 < x2 ) return -1;  // Bedingung 1
    if( x1 > x2 ) return 1;   // Bedingung 2
    if( y1 < y2 ) return -1;  // Bedingung 3
    if( y1 > y2 ) return 1;   // Bedingung 4
    return 0;                 // Bedingung 5
}

Kann man die Bedingungen 1 bis 5 auch so schreiben:

if( x1 < x2 ) return -1;       // Bedingung 1
    else if( x1 > x2 ) return 1;   // Bedingung 2
    else if( y1 < y2 ) return -1;  // Bedingung 3
    else if( y1 > y2 ) return 1;   // Bedingung 4
    else return 0;                 // Bedingung 5

Wäre für mich einfacher, wenn ich mein Code wieder nach drei Jahren angucke ;).

Beste Grüße,
simsa

P.S. ich bin gerade unterwegs und habe keinen Compiler zur Hand