Chars zusammenfügen und sortieren

campinge

Hallo und ein Frohes Neues!

Ich habe mal eine Frage:

Ich hab mir ein programm geschrieben, dass aus 2 verschiedenen Dateien zeilen einliest, splittet vergleicht und zusammenfügt.
Das klappt wunderbar. Allerdings habe ich festgestellt, dass die Anwendung, für die die fertige Datei ist, alle zeilen Alphabetisch und Numerisch sortiert haben will -.-

Die Zeilen (~200.000) sehen ungefähr so aus:

5340N;53.000000;40.000000;3
CAMRN;48.515145;-137.638273;5
MUN;34.5826752;123.692649;4

Sortiert werden muss nach dem ersten Kürzel.

Intern habe ich 4 chars erstellt, indem die Werte zwischen den ";" schleifenweise für jede Zeile eingelesen werden.
Am Ende der Schleife werden sie momentan direkt in eine Datei geschrieben.

Wie geh ich jetzt da am schlausten ran um die Zeilen zu sortieren?

Nexus

Wieso nimmst du nicht std::string ? Da werden dir auch gleich die Operatoren für lexikalische Vergleiche bereitgestellt, die für die Sortierung benutzt werden können.

Dann kannst du einen Container mit Elementen vom Typ std::string erstellen. Jede Zeile erhält nun so einen Eintrag. Dann machst du std::sort() darüber, speicherst wieder in die Datei und fertig.

Du musst die Trennung des ersten Kürzels nicht mehr beachten, da bei std::string zuerst nach dem ersten, dann nach dem zweiten Zeichen, etc. sortiert wird.

campinge

HI!

Danke für den Tipp schonmal!

Leider habe ich nicht wirklich viel erfahrung mit der Standardbibliothek.
Die Elemente befinden sich momentan in chars, damit ich sie einfach vergleichen kann.

Wie muss ich denn dann vorgehen um meine 4 chars inklusive trennzeichen in den string zu bekommen?
und wie erstelle ich dann einen großen string, den ich dann auch sortieren kann?

Ist es da nicht einfacher die chars in ein Array zu packen?

*EDIT*
Ich hab's mal manuell probiert:
`

strcpy(chDataString, chFix);

ctrcat(chDataString, ";");

strcat(chDataString, chLatitude);

strcat(chDataString, ";");

cout << chDataString << endl;

`

Nexus

Wie ist es genau mit den 4 Chars?

Ich hab es so verstanden, dass du in der Datei (den Dateien) die einzelnen Einträge hast:

5340N;53.000000;40.000000;3 
CAMRN;48.515145;-137.638273;5 
MUN;34.5826752;123.692649;4

Dann willst du sie in den Arbeitsspeicher einlesen und sortieren. Nach dem Sortieren willst du die Werte zwischen den ; auslesen. Hab ich das richtig verstanden?

Zum Sortieren:

std::deque<std::string> Entries;    // Container mit allen Einträgen(Zeilen), z.B. deque oder vector

std::string Line;                   // String anlegen, in dem eine Zeile gespeichert wird
std::ifstream File("filename.txt"); // Stream anlegen

while (std::getline(File, Line))    // Zeilen in einer Schleife einlesen und im String speichern
{
    Entries.push_back(Line);        // Zeile in den Container einfügen
}

std::sort(Entries.begin(), Entries.end());  // Container sortieren

Was das Zusammenfügen von Strings angeht, hast du es viel einfacher als mit char -Arrays:

std::string Str1 = "A5634C";
std::string Str2 = "XT522S";
std::string Text = Str1 + ";" + Str2;  // zusammenhängen

Du kannst auch operator+= oder append() benutzen. Schau vielleicht mal unter www.cplusplus.com nach, das ist eine gute Referenz zur Standardbibliothek.

campinge

Ok, also:

die Datei sieht in etwa so aus:

`ENTRE ENTRE-31.534170 130.949200

PEA83 PEA83-31.533961 115.952714

89W80 89W80-89.000000-180.000000

CUNNC CUNNC-31.532590 117.457100

PEA09 PEA09-31.531264 115.961353

NYNWH NYNWH-31.531130 147.241300

CBAEM CBAEM-31.531110 145.804600`

Hierbei handelt es sich um eine Navigationsdatenbank. Das geht so ungefähr 200.000 eintäge weiter. Daraus lese ich jede Zeile aus und zerschnipsel sie in 3 chars:

chFix[5] = "ENTRE"
chLatitude[10] = "-31.534170"
chLonglitude[11] = "130.949200"

und

chNumber[1] = "0"

chNumber kommt aus einer anderen Datei, dort wird abgeglichen, ob derselbe eintrag vorhanden ist, wie in dem char chFix. Wenn nicht, gibt's ne null.

dann wird alles in eine neue Datei geschrieben, die ein anderes Format vorraussetzt:

`ENTRE;-31.534170;130.949200;3

PEA83;-31.533961;115.952714;5

89W80;-89.000000;-180.000000;0

CUNNC;-31.532590;117.457100;0

PEA09;-31.531264;115.961353;3

NYNWH;-31.531130;147.241300;5

CBAEM;-31.531110;145.804600;5`

Allerdings muss die Ausgabe vorher alphabetisch sortiert werden, also:

`89W80;-89.000000;-180.000000;0

CBAEM;-31.531110;145.804600;5

CUNNC;-31.532590;117.457100;0

ENTRE;-31.534170;130.949200;3

PEA09;-31.531264;115.961353;3

PEA83;-31.533961;115.952714;5

NYNWH;-31.531130;147.241300;5`

und da haperts...

Hoffe das reicht ums verständlicher zu machen

Nexus

Okay. Das Zerschnipseln kannst du mit std::string einfach lösen, indem du die Memberfunktion substr() benutzt (siehe mein geposteter Link zur C++-Referenz). Oder du benutzt gleich std::replace() , um die Leerschläge durch Strichpunkte zu ersetzen.

Also würde ich zuerst zeilenweise von der ersten Datei einlesen, die Formatänderung und Vergleiche mit der anderen Datei vornehmen und dann die aktuelle Zeile jeweils in einem Container speichern. Wenn du diesen Container gefüllt hast, kannst du ihn mit std::sort() alphabetisch sortieren und wieder zeilenweise in die neue Datei schreiben.

Was mir allerdings etwas problematisch erscheint, sind die Prüfungen, ob der Eintrag in der anderen Datei vorhanden ist. Gehst du da für jeden Eintrag der ersten Datei alle Einträge der anderen Datei durch? Eventuell lohnt es sich, die Einträge der anderen Datei auch in einem Container zu speichern, vielleicht einem assoziativen wie std::set , damit du schneller suchen kannst.

Ich hoffe, das war jetzt einigermassen verständlich, ansonsten einfach nachfragen.

campinge

supi, das ging schnell.

An genau das hab ich auch gerade gedacht und habs mal drauf losprobiert:
error C2039 'deque' is not a member of 'std' ...

was das abgleichen angeht: ja, für jeden eintrag der ersten list muss ich die komplette 2. Liste durchlaufen, bis ich meine variable gefunden habe - oder eben nicht. Der Erste Testlauf hat gleub ich fast 4 Stunden gedauert...

also, nur um zu gucken ob ich's richtig verstanden habe:

Ich erstelle mir 2 container.
In den ersten kopiere ich die komplette 2. Liste
aus der ersten liste hole und verarbeite ich die variablen zeilenweise
(btw: leider hat er's hier nicht richtig angezeigt. in der ersten Liste habe ich zwischen dem ersten kürzel und dem wiederholten kürzel ca. 13 leerstellen, std_replace scheint hier schlecht zu sein...)
dann pushe ich alles in den 2. container.
nach durchlauf der schleife wird der sortiert und in die Datei geschrieben.

richtig?

--btw2: ist es möglich einen string in den container zu pushen?
den hätte ich nämlich schon parat...

*EDIT* Fehlermeldung schon begraben und die Strings scheine ich auch pushen zu können.

drakon

error C2039 'deque' is not a member of 'std' ...

#include <deque>
...

ist es möglich einen string in den container zu pushen?

std::vector<std::string> v;
v.push_back ("hmm");
std::string str = "ak";
v.push_back (str);
...

campinge

super, hat wunderbar geklappt. die chars kann ich alle pushen. morgen bau ich das dann nochmal komplett um.

allerdings hab ich noch 3 Fragen:

1. woher kommt std::sort. ist mal wieder "no member of 'std'"
2. wie speichere ich den container: nur std::ofstream FILE "filename.txt"); ?
3. wie vergleiche ich mein chFix mit dem containerinhalt der 2. Liste und hole mir die Variable?

Nexus

So, ich hatte gerade ein wenig Zeit...
Da du auch viel Eigeninitiative zeigst, hier mal ein ungefährer Ansatz. std::set ist ein assoziativer Container, bei dem man in logarithmischer Zeit suchen kann.

#include <fstream>	  // std::ifstream, std::ofstream
#include <string>       // std::string
#include <deque>		// std::deque
#include <set>		  // std::set
#include <algorithm>	// std::sort()

void Format(const std::string& Line, bool EntryFound)
{
	// hier formatierst du den String um. Abhängig davon,
	// ob der Eintrag in der zweiten Datei gefunden wurde.
}

int main()
{
	std::ifstream InFile1;      // Stream für erste Datei
	std::string Line;	          // String für jeweilige Zeile

	// Einträge der zweiten Datei in List2 speichern
	std::set<std::string> List2;
	while (std::getline(File1, Line))
	{
		List2.insert(Line);	// Zeile in List2 einfügen
	}

	// Einträge der ersten Datei in List1 speichern und
	// prüfen, ob Eintrag jeweils in List2 vorhanden ist
	std::deque<std::string> List1;	
	while (std::getline(File1, Line))
	{
		bool EntryFound = false
		if (List2.find(Line) != List2.end())	// wenn Eintrag in List2 vorhanden ist
		{
			EntryFound = true;	// kann man auch gleich mit ?: machen, aber hier übersichtlicher
		}

		Format(Line, EntryFound);      // String formatieren
		List1.push_back(Line);         // formatierten String in List1 einfügen
	}

	// Einträge aus List1 sortieren
	std::sort(List1.begin(), List1.end());

	// Stream für Ausgabedatei erstellen
	std::ofstream OutFile("OutFile.txt");

	// Alle Elemente aus List1 durchgehen
	for (std::deque<std::string>::iterator i = List1.begin(); i != List1.end(); ++i)
	{
		OutFile << (*i) << std::endl;	// Einträge wieder in Datei schreiben
	}
}

Vielleicht klären sich einige Fragen, wahrscheinlich entstehen aber wieder viele neue... Frag einfach.

Falls du dich mit der STL noch nicht so auskennst, kannst du dir ja mal diese Artikel anschauen (vor allem 1 und 2 sind hierbei wichtig):
1) Container
2) Iteratoren und Algorithmen
3) Hilfsklassen und Erweiterungen

campinge

wow, vielen dank!!!!!

dann studier ich das mal fleißig.
Vielen, vielen Dank nochmal für die Mühe!

campinge

ok, genial.
Ich habe es geschafft alles zu pushen, zu sortieren und zu schreiben.

Jetzt habe ich nurnoch eine Frage:

if (List2.find(Line) != List2.end())    // wenn Eintrag in List2 vorhanden ist

vergleicht doch die kompletten Zeilen miteinander, korrekt?
Da ich ja aus jeder Zeile nur das Erste Wort vergleichen kann (die sehen nämlich genau so aus wie das Endergebnis) muss ich die dann erst zerschneiden.
Wie schneide ich denn von einem String das erste Wort ab?

Nexus

campinge schrieb:

if (List2.find(Line) != List2.end())    // wenn Eintrag in List2 vorhanden ist
vergleicht doch die kompletten Zeilen miteinander, korrekt?

Ja.

campinge schrieb:

Da ich ja aus jeder Zeile nur das Erste Wort vergleichen kann (die sehen nämlich genau so aus wie das Endergebnis) muss ich die dann erst zerschneiden.
Wie schneide ich denn von einem String das erste Wort ab?

Mit der Memberfunktion std::string::substr() . Wenn das Wort immer gleich lang ist, kannst du substr() einen fixen Parameter übergeben. Ansonsten kannst du mit std::string::find() die Position des Trennzeichens (Abstand, Strichpunkt oder was auch immer) herausfinden und dann den Teilstring entsprechend lange machen.

campinge

So, vielen lieben Dank nochmal!

Ich habs doch tatsächlich noch gestern abend geschafft alles zum laufen zu bekommen. Die Idee mit den containern war wirklöich klasse, jetzt ist die Ablaufzeit von ~4 Stunden auf ca 2 Minuten verkürzt worden. Anscheinend war mein code doch etwas zu umständlich
Und mit der Kompatibilität klappst auch!

Nexus

campinge schrieb:

jetzt ist die Ablaufzeit von ~4 Stunden auf ca 2 Minuten verkürzt worden.

Wow, damit hätte ich jetzt nicht gerechnet.

Teuer sind hierbei vor allem die Zugriffe auf die Festplatte, also per Streams. Die STL-Container sind extrem praktisch und auch weitgehend auf Performance optimiert. Ich habe jetzt einmal std::deque empfohlen, da da die Speicherverwaltung günstig ist (Array von Arrays). Du könntest auch std::vector nehmen, allerdings könnte es sein, dass es dann länger dauert, weil jeweils die ganze Sequenz reallokiert werden muss, wenn die Kapazität erschöpft ist. Oder std::list , wobei das sehrwahrscheinlich noch langsamer ist, weil jedes Element einzeln allokiert wird. Achte darauf, dass du bei der Liste nicht die globale Funktion std::sort() , sondern die Memberfunktion std::list::sort() aufrufst. Du kannst ja ein wenig experimentieren, aber ich denke, mit std::deque bist du gut beraten.

drakon

campinge schrieb:

So, vielen lieben Dank nochmal!

Ich habs doch tatsächlich noch gestern abend geschafft alles zum laufen zu bekommen. Die Idee mit den containern war wirklöich klasse, jetzt ist die Ablaufzeit von ~4 Stunden auf ca 2 Minuten verkürzt worden. Anscheinend war mein code doch etwas zu umständlich
Und mit der Kompatibilität klappst auch!

Schalt mal noch auf Release. Das sollte dir auch noch sehr viel bringen. Dann bist du wahrscheinlich im Sekunden - Bereich.

Nexus

drakon schrieb:

Schalt mal noch auf Release. Das sollte dir auch noch sehr viel bringen. Dann bist du wahrscheinlich im Sekunden - Bereich.

Er sprach ja von 200'000 Einträgen und zwei Dateien. Allein das Streamen dürfte einige Zeit brauchen, und dann noch das Füllen zweier Container und Sortieren...

Aber genau weiss ich es auch nicht, da ich praktisch nie in dieser Grössenordnung arbeite. Von daher ist es schon möglich...

campinge

ok, danke für den Tipp!

Ich habe gerade festgestellt warum der durchlauf so schnell geht.

die Schleife für die 2. Datei läuft nur einmal durch, danach wird die einfach ignoriert. Somit wird halt nur für den 1. Navigationspunkt überprüft, ob dieser vorhanden ist. Der rest wird übersprungen.

gibt's so ne art fgetpos / fsetpos auch für die stl-container?

Nexus

campinge schrieb:

gibt's so ne art fgetpos / fsetpos auch für die stl-container?

Hm, die Funktionen kenne ich nicht gut, da die eher C sind. Meinst du etwas wie tellp() bzw. seekp() für Streams? Auf den Containern ( std::deque und std::vector ) kann man einfach per at() oder operator[] die einzelnen Elemente manipulieren.

Ich kann dir nur nochmals raten, www.cplusplus.com anzuschauen. Dort sind sowohl die Streams als auch die STL mit ihren Containern und Algorithmen sehr ausführlich erklärt.

drakon

Die generische Variante für für set wäre std::advance. Das abfragen müsstest du selbst mitzählen.

campinge

ok, danke Jungs!

Den Fehler habe ich gestern gefunden. Ich hatte die Definition + Deklaration global gealten. Dadurch gings ned.
Jetzt hab ich das kurz über die Schleife gehängt und siehe da, es klappt.
Allerdings wieder mit gewohnter langsamkeit. Habe gestern für 5881 Zeilen 5-10 Minuten gebraucht, da freue ich mich ja schon auf die 200000