2D Array sortieren

[simsa]

Hallo SeppJ,

danke für Deine Antwort.

Naja, mit sort in der Shell kann ich nicht arbeiten, weil

1. das Programm in C, was ich geschrieben habe, ließt binäre Dateien (die binäre
Datei ist das Ergebnis einer Simulation) ein. Aus meiner Einleseroutine erhalte
ich dann die 2D-Array-Datei.

2. diese Datei muss ich dann weiter 'verarbeiten', sortieren, interpolieren und
etc..

Das 2D-Array beinhaltet nur 'double'-Zahlenwerte.

Ich hatte die Datei einfach mal rausgeschrieben und geguckt, wie schnell es
mit sort() geht. Ich vergleiche meine Programme immer mit 'Standard'-Sachen
um zu gucken, ob meins besser ist oder nicht

Wäre sehr Dankbar, wenn jemand mir qsort etwas näher bringen würden.

Besten Dank,
simsa

[simsa]

Hallo knivil,

hier ist der 'sortier'-Teil meines Programms.

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

#include "sort.h"
#include "tools.h"

int sort (char *order) {

	int length;

  double **xy = readXY("data/pull_fx.xvg", &length);

	if (strcmp(order, "asc") == 0)					///< ascending order
		qsort(xy, length, sizeof(double), cmp);
	else if (strcmp(order, "desc") == 0)		///< descending order
		qsort(xy, length, sizeof(double), cmp);
	else {
		printf("ERROR: sort() -> unknown sorting order '%s'\n", order);
		printf("Program terminated.\n");
		exit(EXIT_FAILURE);
	}

	return 0;

}

double compare (const void * a, const void * b)
{
  return ( *(double*)a - *(double*)b );
}

Die cmp-funktion ist nicht fertig bzw. weiß ich nicht wie, ich es 'schreiben'
soll.

Ich will die Shell umgehen, es wäre für meine Auswertungen unpraktisch.

Viele Grüße,
simsa

[broffi]

SeppJ schrieb:

Kein Wunder: Das sort der Shell ist schließlich auch in C geschrieben und die wussten auch was sie taten.

Wer weiss, was er tut, schreibt in C. Die Schlussfolgerung gefällt mir

SeppJ schrieb:

Die haben bestimmt kein Selection-Sort genommen. Möglicherweise benutzen sie sogar einfach qsort aus der Standardbibliothek.

Das waren wirklich echte Profis. Die nutzen ein optimiertes Merge-Sort (immer 16 Listen auf einmal).
Das ermöglicht (1.) Swap-Dateien (effizientes Sortieren von Mengen, die nicht mehr in den Speicher passen), (2.) paralleles Sortieren auf mehreren Threads und (3.) stabiles Sortieren.

SeppJ schrieb:

qsort ist übrigens auch nicht die allerletzte Offenbarung, was Geschwindigkeit angeht, wenn die einzelnen Elemente klein sind und die Vergleichsfunktion einfach aufgebaut ist.

qsort ist nie die allerletzte Offenbarung was Geschwindigkeit angeht. Aber fast immer ausreichend.

SeppJ schrieb:

In dem Fall bietet sich das sort aus der Standardbibliothek von C++ an, weil das mit dem Fall viel besser zurecht kommt. Was für Daten sind das denn? Datenelemente bis zu ungefähr 16 Byte würde ich eher mit C++ machen, bei größeren Sachen wird es dann irgendwann egal, da der Prozess von den Vergleichen und Vertauschungen selbst dominiert wird und die Sprache keine Rolle mehr spielt.

Wenn Geschwindigkeit eine Rolle spielt und die Datenelementy kleiner als 16 Byte gross sind, bietet sich prinzipiell radix-sort an.
Wenn die Daten nicht in den Speicher passen, bietet sich Merge-Sort an.
Wenn die Elemente gross sind, aber die Daten nicht allzu gross, bietet sich eine Indexliste an.
...
std::sort kann das nicht alles abbilden (aber zugegenenermassen eine Übermenge von qsort).

[knivil]

double **xy = ...

Du kannst dir auch ueber geeignete Datenstrukturen Gedanken machen. Btw. wer gibt dein Array von Array von double wieder frei?

double compare (const void * a, const void * b) 
{ 
return ( *(double*)a - *(double*)b ); 
}

Falsch, die von qsort erwartete Signatur der Vergleichsfunktion ist anders. Auch sonst beruecksichtigst du nur den ersten Wert in deinem Array von doubles.

Bemerkenswert ist aber, dass wenn ich solche riesen Dateien in der Linux
Shell mit dem sort Befehl sortiere es viel schneller geht.

Wieviel Gigabyte hat denn die Datei?

Ansosnten:

struct entry
{
    double v[2];
};

int sgn(double val) {
    return (0 < val) - (val < 0);
}

int entry_less(void const* a, void const* b)
{
    struct entry const* first = (struct entry*)a;
    struct entry const* second = (struct entry*)b;

    int r = (first->v[0] - second->v[0] == 0) ? sgn(first->v[1] - second->v[1]) : sgn(first->v[0] - second->v[0]);
    return r;
}

int _tmain(int argc, _TCHAR* argv[])
{
    struct entry es[] = { {1,0}, {2,1}, {1,2}, {5,2}, {5,1}, {5,3} }; // ich spare mir das einlesen mal

    qsort(es, 6, sizeof(es[0]), entry_less);

    for (int i = 0; i < 6; ++i)
        printf("%f %f'\n", es[i].v[0], es[i].v[1]);

	return 0;
}

[SeppJ]

simsa schrieb:

double **xy;

Das ist schon einmal sofort falsch für eine Liste von zwei doubles. Das ist eine Liste von Listen von doubles.

double (*xy)[2] ist eine Liste von zwei doubles. Und viel schneller.

[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

[DirkB]

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