malloc 2d array

Hallo zusammen

Ich möchte eine Textdatei sortieren und alle Einträge die redundat sind entfernen. Mein Problem ist die Grösse der Datei. Sie hat etwa 4 Millionen Zeilen und in jeder zeile Steht ein Wort.
Da mein PC die grösse des statischen Speichers nicht schluckt, und 4 millionen Pointer auch nicht gehen wollte ich einen dynamischen machen.

char **caBuffer=malloc(10*50*sizeof(char));
strcpy(caBuffer[0],"Zorro");

Kann mir jemand sagen wo sich der Fehler versteckt?
Wie kann ich am evektivsten sortieren? Mit qsort?
Wie kann ich am evektivsten nach doppelten einträgen Suchen?

Gruss

SeppJ

dasolo schrieb:

Hallo zusammen

Ich möchte eine Textdatei sortieren und alle Einträge die redundat sind entfernen. Mein Problem ist die Grösse der Datei. Sie hat etwa 4 Millionen Zeilen und in jeder zeile Steht ein Wort.
Da mein PC die grösse des statischen Speichers nicht schluckt, und 4 millionen Pointer auch nicht gehen wollte ich einen dynamischen machen.
char **caBuffer=malloc(10*50*sizeof(char));
strcpy(caBuffer[0],"Zorro");
Kann mir jemand sagen wo sich der Fehler versteckt?

Die Idee bei 2D-Arrays ist eigentlich eher, dass du erst eine Reihe von Pointern auf Pointer reservierst und dann für jeden dieser Pointer nochmals ein malloc machst.

Wie kann ich am evektivsten sortieren? Mit qsort?

qsort ist in der Regel sehr effektiv implementiert, aber ich sehe nicht, wieso du hier sortieren müsstest.

Wie kann ich am evektivsten nach doppelten einträgen Suchen?

Ich weiß nicht ob dies das effektivste ist, aber es ist sicherlich ganz gut: Schreib dir einen Container wie das C++ set, d.h. ein binärer Suchbaum (gerne auch mit Ausgleichsalgorithmen falls der Baum zu unbalanciert wird). Dann sortierst du die Wörter eins nach dem anderen in den Baum und guckst ob ein entsprechender Eintrag eventuell schon vorhanden ist. Dies sollte, wenn mich nicht alles täuscht, in N*log(N) der Wörterzahl laufen.

supertux

dasolo schrieb:

Kann mir jemand sagen wo sich der Fehler versteckt?

du hast Platz reserviert, um 500 Bytes zu speichern, die Anfangsadresse zu diesem Block liegt auf caBuffer.

Der Inhalt des reservierten Blockes ist aber nicht definiert und kann alles möglich sein, caBuffer[0] ist keine gültige Adresse. Du kannst strcpy darauf nicht anwenden, weil caBuffer[0] ins Nirvana zeigt. Du musst wiederrum Speicher für "Zorro" reservieren, caBuffer[0] zuweisen und dann strcpy verwenden.

dasolo schrieb:

Wie kann ich am evektivsten nach doppelten einträgen Suchen?

Mit Hashes. Ich hätte dein Problem so gelöst.
Jeder string bekommt eine mehr oder weniger eindeutige Zahl zugewiesen (du speicherst das in einer struct line_hash { unsigned hash; unsigned linenr; }; in einem Array. Das muss dann zum Glück nicht ganz so gross wie die Datei sein.
Dann sortierst du das Array nach dem Hash und merkst dir alle gleichen Hashes.
Das sind nicht mehr ganz so viele, die kannst du in einem Array vollständig einlesen und aussortieren.

Rein theoretisch ist die Laufzeit gleich wie die von SeppJ (N·log(N)), aber in der Praxis müsste sie deutlich schneller ablaufen.

Danke, hatte ich föllig vergessen den Pointer noch Platz erinzuräumen... Das mit dem Baum scheint mir ein bisschen übertrieben... Wenn ich zuerst sortiere muss ich nur noch die Nachbarn vergleichen und eintsprechend löschen... Andernseits als Übung einen Baum zu erstellen schein mir sinnvoll

qsort ist in der Regel sehr effektiv implementiert, aber ich sehe nicht, wieso du hier sortieren müsstest.

qsort ist in der Regel sehr effektiv im
plementiert, aber ich sehe nicht, wieso du hier sortieren müsstest.[quote]
Das Zeil sein soll die Wörter in alphabetischer Reihenfolge in einer Textdatei zu schreiben und alle Doppelten zu löschen...
Und es sollte in einer akzeptablen Zeit geschehen, darum nehme ich ja nicht Bubblesort.

[quote="dasolo"]Danke, hatte ich föllig vergessen den Pointer noch Platz erinzuräumen... Das mit dem Baum scheint mir ein bisschen übertrieben... Wenn ich zuerst sortiere muss ich nur noch die Nachbarn vergleichen und eintsprechend löschen... Andernseits als Übung einen Baum zu erstellen schein mir sinnvoll
[quote]qsort ist in der Regel sehr effektiv implementiert, aber ich sehe nicht, wieso du hier sortieren müsstest.

Das Zeil sein soll die Wörter in alphabetischer Reihenfolge in einer Textdatei zu schreiben und alle Doppelten zu löschen...
Und es sollte in einer akzeptablen Zeit geschehen, darum nehme ich ja nicht Bubblesort.

Edit: Es handelt sich um 5.5millionen Wörter...

Wutz

Nimm qsort für diese Aufgabe, das ist einfach und gut.

Binggi

Sorry für den doppelpost...

Ich habe nun ein neues Problem... Nach ca 1.5 Millionen Wörter meldet der

Compiler make: *** [run] Segmentation fault (core dumped)

Hier der Code:

char **ppcBuffer=malloc(6000000);
		char caBuffer[100+1];
		int i=0;
		FILE *fp=fopen("db.txt","r");

		while(fgets(caBuffer,100,fp)>0)
		{
			ppcBuffer[i]=malloc(strlen(caBuffer)+1);
			strcpy(ppcBuffer[i],caBuffer);
			i++;
		}

Hat jemand eine Idee wie ich das problem umgehen kann?
Danke für eure Hilfe...

Edit: Zur Aufklärung, hatte im Geschäft mein Passwort nicht zur Hand,xD Ich bin dasolo...

SeppJ

6000000, 100+1, 100 wo kommen all diese magischen Zahlen her? Wieso benutzt du nicht so viel Speicher wie du wirklich brauchst? Beispielsweise ist 6000000/4 = 1.5 Millionen. Fällt dir was auf? Ich wette sizeof(char**) ist bei dir 4.

Binggi

Die Datei ist 5.8Millionen Wörter schwer... Daher kommt 6.000.000.
Du hast recht, habe ich vergessen das sizeof(char**) dazuzurechen.
100 hat keinen Tieferen Sinn, ich habe angenommen, dass die Wörter nich länger als 100 sind. 100+1 da terminierung.
DAnke für deine Hilfe.

Wutz

Ich nehme mal an, mit Wörter meinst du Zeilen.
Durchlaufe erstmal die Datei komplett um die Anzahl der Zeilen zu bestimmen und die Gesamtzeichenzahl addiert von jeder Zeile ohne '\n' und mit '\0', dann machst du genau 2x malloc für Zeilenzahl*sizeof(char*) und Gesamtzeichenzahl; dann rewind und nochmal zeilenweisen Durchlauf mit entsprechender Befüllung der 2 o.g. Speicherbereiche.
Falls malloc fehlschlägt, musst du auf das zweite malloc verzichten und mittels ftell/fseek nur mit den Offsets der Zeilen arbeiten, dafür brauchst du dann nur insgesamt Zeilenzahl*sizeof(long) Hauptspeicher.

Binggi

Ich habes mitlerweile geschfft... der Rest war kein Problem mehr.

void sort_cstrings_example() 
{ 
    char **ppcBuffer=malloc(6000000*sizeof(char**));
    char **ppcBuffer1=malloc(6000000*sizeof(char**));
		char caBuffer[100+1];
		int i=0,j=1,k=1;
		FILE *fp=fopen("db.txt","r");

		while(fgets(caBuffer,100,fp)>0)
		{
			ppcBuffer[i]=malloc(100+1);
			strcpy(ppcBuffer[i],caBuffer);
			i++;

		}
		ppcBuffer[i+1]=malloc(strlen(caBuffer)+1);
		ppcBuffer[i+1]=0;

		ppcBuffer1[0]=malloc(sizeof(ppcBuffer[0])+1);
		strcpy(ppcBuffer1[0],ppcBuffer[0]);

		while(ppcBuffer[j])
		{
			//printf("%s %s\n\n",ppcBuffer1[k-1],ppcBuffer[j]);
			if(stricmp(ppcBuffer1[k-1],ppcBuffer[j]))
			{
				ppcBuffer1[k]=malloc(100+1);
				strcpy(ppcBuffer1[k],ppcBuffer[j]);
				k++;				
			}
			j++;
			//printf("%d\n",j);
		}

Die Datei ist mittlerweile sortiert.
nicht sehr schön aber es Funktioniert,

SeppJ

Wutz schrieb:

Ich nehme mal an, mit Wörter meinst du Zeilen.
Durchlaufe erstmal die Datei komplett um die Anzahl der Zeilen zu bestimmen und die Gesamtzeichenzahl addiert von jeder Zeile ohne '\n' und mit '\0', dann machst du genau 2x malloc für Zeilenzahl*sizeof(char*) und Gesamtzeichenzahl; dann rewind und nochmal zeilenweisen Durchlauf mit entsprechender Befüllung der 2 o.g. Speicherbereiche.
Falls malloc fehlschlägt, musst du auf das zweite malloc verzichten und mittels ftell/fseek nur mit den Offsets der Zeilen arbeiten, dafür brauchst du dann nur insgesamt Zeilenzahl*sizeof(long) Hauptspeicher.

Das sind sehr viele Dateizugriffe. Bei großen Dateien kann dies sehr lange dauern. Darf ich eine alternative Strategie vorschlagen?

Lies einmal ein. Wenn du an deine Kapazitätsgrenze stößt, dann machst du ein realloc mit doppelter Größe. Da hast du zwar ein bisschen Herumkopiererrei im Speicher aber dies sind selbst im schlimmsten Fall nur so viele Kopieraktionen wie deine Datei lang ist. Und Rumkopieren im Speicher geht sehr schnell. Diese Allokationsstrategie hat sich schon oft bewährt wenn man nicht genau weiß, was auf einen zukommt. Und da man hier die gesamte Datei analysieren müsste um die Zeilen zu zählen, zähle ich das mal zu den Situationen wo man nicht genau weiß was kommt.

Noch besser wäre natürlich, wenn du den Vorschlag mit dem binären Suchbaum umsetzt, da verbrauchst du nur so viel Speicher wie du auch wirklich brauchst und die Herumkopiererei entfällt auch zugunsten von ein paar if-Abfragen. Das ist noch einmal eine ganze Ecke effizienter. Vor allem da du hinterher nicht mehr sortieren brauchst, kommst du damit in eine ganz andere Komplexitätsklasse.