Array sortieren

Binggi

Ich brauche einen Ratschlag wie ich man effizientisten und am Sparsamsten einen Array Sortieren kann.

struct daten
{
  char   typ[16];
  float  wippenhoehe_ref;
  float  hoehe_nullpunkt;

Kleiner Ausschnitt aus der Struktur.
Ich muss das ganze nach typ sotieren.Wobei die ganze struktur wieder ein Array von ca 90-120 ist.40000 Byte pro strukturinstance
Das Programm muss unter MS/DOS laufen...
Bin bis jetzt immer an der Grösse der allozierten variablen gescheitert.
Ist qsort am Besten geeignet?
Gruss Binggi

icarus2

Wenn ich dich richtig verstehe, dann ist die Grösse der Datensätze das Problem, das heisst das Bewegen von Datensätzen ist sehr auwändig.

Wie viele daten-struct Instanzen hast du denn?
Wenn die Laufzeit nicht entscheidend ist, könnte Insertion Sort eine nette alternative zu Quicksort sein, da du im worst case nur linear viele Datensätze verschieben musst und es nur konstant zusätzlichen Speicher braucht.

Binggi

Ja das Problem ist die grösse. Es sind momentan 90 Datensätze, d.h 4MB Speicher.
Aber es kommt noch einiges von anderen Variablen hinzu die ich benötige um 2 weitere Datensätze synchron zu sortieren, welche aber wesendlich kleiner sind.
Der Compiler schluckt nicht 4MB+ lokaler Variablen...

Wutz

Was denn nun?
Hast du Probleme beim Sortieren oder beim "Halten" von Daten?
Nimm malloc/calloc, das gibts auch unter MSDOS.

Binggi schrieb:

Bin bis jetzt immer an der Grösse der allozierten variablen gescheitert.

Mach dir doch eine eigene, spezielle Ansicht deiner Daten.
Spendiere ein Zeigerarray auf dein Strukturarray und sortiere nur die Zeiger, anstatt die Strukturen umzukopieren. Das spart RAM und geht um einiges schneller.

Binggi

Ja schon, war auch mein erster ansatz aber das Problem ist, dass die Sortierten daten wieder in dem ursprünglich array kopiert werden müssen, da ich eine vorgegebe Funktion daten_schreiben(void) aufrufen muss. Und die schriebt den Array wider in ein Textfile. Ausserdem habe ich noch 6 integer strukturen, welche ich synchron Sortieren muss, da ich im nachhinein keinen Bezug mehr auf die Daten habe... Es ist auch nicht möglich das vordefinierte abzuändern. Verscuhe das ganze nochmals mit malloc.

SeppJ

Nenn mich jetzt naiv, aber spricht etwas dagegen, die Daten in-place zu sortieren?

Bei MS-DOS ärgerte die 64k Grenze doch ständig bei grösseren Programmen

Hast du die erfolgreich umschifft oder ist die für deinen Stress verantwortlich?

Wer kennt denn noch die Begrenzungen unter DOS?
a: 64k Blöcke -> kann man programmtechnisch umgehen
b: je nach Einträgen in den Startdateien und DOS-Version, pi * Daumen etwa 600kb freier Speicher auch, wenn in den Speicherbausteinen deutlich mehr vorhanden -> auch hier gab es Wege. Mit Nowel-DOS gab es da Lösungen. MS-Dos ohne Zusätze schaffte glaube ich nicht ganz soviel freien Speicher. Was PC-DOS konnte weiss ich nicht.
c: max. Festplattenpartitionengrössen abhängig von DOS-Version: 0MB, 32MB, 512MB
PC-DOS wurde zuletzt auch auf Rechnern mit grösseren Festplatten ausgeliefert. Ob die da mehr als die 512MB ansprechen konnten?

Das ist aber schon ein paar Tage her. Deshalb solltet ihr eingehender nachforschen

MfG f.-th.

Binggi

Ich benutze FreeDOS mit dem Emulator QEMU. Hab die Daten wie viel das FreeDOS schluckt nicht gefunden.

Bei MS-DOS ärgerte die 64k Grenze doch ständig bei grösseren Programmen

Hast du die erfolgreich umschifft oder ist die für deinen Stress verantwortlich?

Warscheinlich nicht. Ist hoffendlich das letzte Programm was ich für DOS schreiben muss...
Der malloc Versuch ging auch in die Hose: Error R6000: Stack Overflow war alles was er ausspucke. Ich benutze nmake zum kopilieren, gibt es auch einen Debuger dazu der mit weiterhelfen kann?

Wutz

Stack overflow hat nichts mit malloc zu tun, du hast wahrscheinlich immer noch zu große lokale Variablen, etwa

int bla(void *fasel)
{
  int a[1000000]; /* hier kann es leicht  einen Stacküberlauf geben */
  ...
}

oder noch schlimmer die Variablen sogar global.

nmake ist das make-tool. Zu welchem Compiler das gehört weiss ich gerade nicht.
Das wurde mindestens mit Digital Mars, Microsoft und Watcom ausgeliefert.

Also welchen Compiler hast du am Start und welchen Linker?

FreeDOS hab ich nicht so verfolgt - hat man da nicht versucht die Speichergrenzen zu erweitern?

MfG f.-th.

Binggi schrieb:

Ja schon, war auch mein erster ansatz aber das Problem ist, dass die Sortierten daten wieder in dem ursprünglich array kopiert werden müssen, da ich eine vorgegebe Funktion daten_schreiben(void) aufrufen muss. Und die schriebt den Array wider in ein Textfile. Ausserdem habe ich noch 6 integer strukturen, welche ich synchron Sortieren muss, da ich im nachhinein keinen Bezug mehr auf die Daten habe... Es ist auch nicht möglich das vordefinierte abzuändern. Verscuhe das ganze nochmals mit malloc.

ja, macht doch nichts. benutz doch das sortierte zeigerarray zum daten schreiben.
das mit den 6 int-strukturen kann ich jetzt nicht nachvollziehen.
warum kannst du das vordefinierte nicht ändern? kannst du es auch nicht um eine eigene schreibfunktion ergänzen?

Binggi

ja, macht doch nichts. benutz doch das sortierte zeigerarray zum daten schreiben.
das mit den 6 int-strukturen kann ich jetzt nicht nachvollziehen.
warum kannst du das vordefinierte nicht ändern? kannst du es auch nicht um eine eigene schreibfunktion ergänzen?

Nein leider nicht...
Ich habe eine Datei die ich in eine Strukur Array fülle, alles in allem 46kb gross. Nebenbei lese ich jedoch noch weitere 3 Dateien aus die in die jeweiligen int Array geschrieben werden. Wenn ich nun den struct array index 0 auf 2 verschiebe muss ich auch alle int array inex 0 auf 2 verschieben. Das ist recht schlecht gemacht aber nicht änderbar.
Wie gross dürfen denn alles globelen und lokalen Variablen gemeinsam gross sein?
Nicht mehr als 56kb?

Binggi schrieb:

Wie gross dürfen denn alles globelen und lokalen Variablen gemeinsam gross sein?
Nicht mehr als 56kb?

56kb ist ja eigentlich nicht so viel aber wieviel FreeDos hergibt weiß ich auch nicht. Vllt. haben die ja die Funktion alloca (nicht standard) implementiert.
http://www.mkssoftware.com/docs/man3/alloca.3.asp
oder vllt. lässt sich die stackgröße wie bei ms dos in der config.sys festlegen? keine ahnung.

vllt. liegt es auch an der qemu konfiguration?
guckst du:
http://lists.gnu.org/archive/html/qemu-devel/2009-10/msg02211.html

Binggi

Danke für eure Tipps, habe den Fehler gefunden.
Das Memorx Modell war auf Small eingestell. Bei Large habe ich die Probleme nicht mehr. Ausser malloc funktioniert nicht. '=' : defferent levels of indirection meint er. Aber der spinnt, ist alles korrekt.
Aber da des erste Problem behoben ist kann ich malloc wieder weglöschen.
Danke für eure Hilfe
Gruss Binggi

Wutz

Unsinn.
Der Compiler hat immer Recht.

Binggi

gcc sagt korrekt und der Compiler von FreeDOS (weiss den Namen nicht mehr) sagt Fehler. und gcc wurde mit pedantic compiliert. Die Frage ist wer hat mehr Recht?

Da er malloc ja nicht benötigt und die Fehlermeldung dort auftritt, wenn ich das richtig deute, kann es sein das er Glück hat.

Sollte der Quelltext für die Funktion des Programms unbedingt erforderlich sein und es funktioniert nicht wie erwartet, sollte man sich die Sache genauer ansehen.

Nach der Fehlermeldung haben ja schon einige gesucht

Ohne den Quelltext an der Stelle gesehen zu haben, vermute ich ein Zeigerproblem.

Das malloc nicht funktioniert kann an den genutzten Headern liegen. Abhängig vom Alter des Compilers oder dessen Lieferanten kann es sein das die Funktionen in verschieden benannten Headern sind. Manchmal ist auch der Dialekt ein wenig anders bei der Speicherreservierung.

MfG f.-th.

Binggi

Da ich die Funktion nicht mehr zwingend benötige, kann ich das weglassen.
Aber nach ANSI C ist die Funktion ,bzw. der malloc richtig verwenden.
Habe den quelltext nicht gerade zur Hand, aber es hat etwa so ausgesehen:

struct data *tmp_data[90];
for(iIndex=0;iIndex<90;iIndex++)
{
  tmp_data[iIndex]=malloc(sizeof(data));
}

Er kopiliert das ganze schon, es ist nur eine Warung. Aber sobal ich das Programm starte stürtzt des MSDOS ab,xD. Da macht Programmieren noch Freude.
Wenn mich nicht alles täuscht heisst der Compiler auf dem FreeDOS qcc.
Ich habe es auch mit casten versucht, da kommt dann irgend eine warnung mit "far pointer", habe den genauen wortlaut nicht mehr im Kopf.