Dateiverarbeitung in C |
15.05.2015, 00:21 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | Dateiverarbeitung in C hallo, eigentlich soll es bei dieser Aufgabe um Threads und Speedup gehören, also das Programm mittels #pragma Anweisungen beschleunigen. Konkret soll hierzu eine Textdatei eingelesen und alle Wörter, die mindestens einmal vorkommen abgespeichert werden. Wir haben hierzu ein Codegerüst erhalten. Hier ist auch schon mein erstes Problem: Ich verstehe nicht, wofür die Variablen "target" oder "hash" gut sind. Im Prinzip kann ich mit dem vorgegeben Code, bis auf das öffnen der Datei, nicht nachvollziehen. Mit hilfe des buffer und der strtok() Funktion habe ich einen Versuch gemacht, die Wörter der Datei einzulesen. Hier mal der Code dazu:
Ich denke, wenn ich den vorgegeben Code, bzw. die vorgegeben Arrays bzw. Variablen richtig verstehe wofür genau ich die brauche, würde mir das enorm weiterhelfen. Im Moment bin ich ziemlich ratlos. Auch habe ich nicht wirklich eine Ahnung, wie man die Wörter des Textes überhaupt einlesen kann. So wie ich den Rest des vorgegeben Codes verstehe, ist im Prinzip der 3. und 4. Teil der Aufgabe schon vorgegeben, sodass es im Prinzip nur darum geht, die Wörter der Datei zu speichern. Ich hoffe mir kann jemand weiterhelfen und schon mal vielen Dank im voraus. Im folgenden noch der Code für den MD5 hash, damit das Programm compiliert werden kann.
hier die md5.h Datei
|
||||||||||||||||||||
|
|||||||||||||||||||||
15.05.2015, 07:42 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
eulerscheZahl | Hashfunktion: eine beliebig lange Bytefolge soll auf eine bestimmte Länge reduziert werden und gleichzeitig ein identischer Hashwert für ähnliche Bytefolgen möglichst ausgeschlossen werden. Wenn du z.B. eine große Datei aus dem Internet lädtst, kannst du so sicherstellen, dass sie auch fehlerfrei bei dir angekommen ist. Daher wird der Hash der Datei manchmal angegeben (siehe eclipse). Du sollst letztlich die Hashfunktion umkehren, also einen string finden, dessen hash target entspricht. Man kann aus Hashwerten aber nicht direkt das Original errechnen: zum einen gibt es mehr als eine Möglichkeit, auf einen bestimmten Hashwert zu kommen (der ja eine begrenzte Größe hat, während das Original größer sein kann), zum anderen wird oft großer Aufwand betrieben, die Funktion derart zu gestalten, dass sie sich nicht invertieren lässt (wichtig für Kryptographie, in deinem Fall eher uninteressant). Deshalb sollst du sämtliche Kombinationen mit dem vorgegebenen Hash vergleichen. Ich verstehe ehrlich gesagt nicht, wie du so Wörter einlesen willst, hier mal mein Vorschlag:
|
||||||||||||||||||||
15.05.2015, 13:50 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
as_string | Also, irgendetwas passt da bei der Aufgabenstellung nicht zusammen... Einerseits schreibst Du, dass die Aufgabe wohl sei, eine eindeutige Liste von vorkommenden Wörtern zu generieren. Dazu muss man wohl auch eine Hashtabelle aufbauen, so dass der Lookup relativ schnell ist. Warum man dafür MD5 verwenden sollte, der ja eigentlich eher kryptographische Zwecke erfüllt als besonders schnell zu sein um ihn bei Hash-Tabellen zu verwenden, ist mir nicht klar. Des weitern hat eulerscheZahl natürlich Recht, dass wohl auch ein String gefunden werden soll, der dem vorgegebenen target-Hash entspricht. Nur was soll das wiederum mit der Liste eindeutiger Wörter zu tun haben? Die erste Teilaufgabe, die im Quelltext genannt ist, ist die eindeutige Wortliste... ok. Dann ist aber die Rede von "two-string combinations". Hä? Welche zwei Strings? Die von zwei Wörtern? Sprich, man soll die eindeutige Liste nehmen und jedes Wort mit allen anderen kombinieren und mit der Kombination einen Hash bilden? Für was soll das denn gut sein? Soll man dann die Kombination finden, die dem Target-Hash entspricht oder wie? Keine Ahnung... Also eine etwas genauere Aufgabenstellung braucht man da mE schon. Gibt es da einen noch einen Aufgabentext dazu, den Du uns im Original geben könntest? So wie ich die Aufgabe verstehe: Ersteinmal eine eindeutige Liste der vorkommenden Wörter bilden. Das macht man normalerweise mit einer Hash-Tabelle und mit einer für Strings passenden Hash-Funktion. Ich würde da nicht MD5 dafür nehmen. Um das Leben einfach zu gestalten, würde ich noch eine verkettete Liste führen, damit man die Hashtabelle am Ende auch vernünftig ausgelesen bekommt. Ob man diesen Teil parallelisieren kann ist mE fraglich und würde auch nicht viel bringen, weil dabei ja auch noch die Datei gelesen wird, so dass das Eintragen in die Hash-Tabelle wohl die geringste Zeit kosten wird. Wenn das mit Hash-Tabelle zu kompliziert ist: Man kann erst eine Liste machen, in der man sich alle Wörter merkt, wie sie vorkommen und diese dann anschließend sortieren. Dann läuft man über die Liste und nutzt aus, dass nach der Sortierung ja logischerweise alle gleichen Wörter hintereinander kommen, so dass man recht leicht eine eindeutige Liste bekommt. Das ist auch sehr ungeschickt, weil man dann wirklich den ganzen Text im Speicher halten muss und dazu noch im Anschluss sortieren muss. Der Ansatz mit der Hashtabelle ist da viel effizienter, aber auch etwas aufwändiger umzusetzen, denke ich. Wenn man diese Liste hat, muss man offenbar Wortpaare bilden, für jedes Paar einen Hash berechnen und den mit dem target vergleichen. Das ist der Teil, den man gut parallelisieren kann, denke ich. Vielleicht machst Du eine Funktion, die die beiden Indizes der beiden zu kombinierenden Wörter in der eindeutigen Liste als Parameter bekommt und einen Hashwert zurück gibt. Dann vergleichst Du diesen Wert mit dem target. Das kannst Du natürlich für alle Paare parallel machen, also das Ausrechnen des Hash und das Vergleichen. Außerdem: Du musst bei MD5 die beiden Teilstrings nicht erst Concatinieren, man kann auch einfach zweimal MD5_Update() aufrufen, also einmal den Init, zweimal das Update und dann das Finalize, um den fertigen MD5 zu bekommen. Noch was wegen der HASH_LENGTH-Konstante: Die Länge eines MD5-Hashwertes ist immer 16 Byte. Gruß Marco |
||||||||||||||||||||
18.05.2015, 23:43 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | hallo, erst mal danke für die Antworten. So, wie ich das jetzt verstanden habe, muss ich den Hash der eingelesen Wörter mit den Hashwerten von target vergleichen. Der Hash eines eingelesen Wortes wird ja mit MD5_Final übergeben, sodass dieser im Array "hash" stehen müsste (da dies ja an MD5_Final übergeben wird), somit habe ich versucht einfach den jeweils eingelesenen Hash-Wert von hash nach jedem eingelesen Wort mit target zu vergleichen und anschließend das jeweilige Wort auszugeben. Komischerweise kommt bei Ausführung immer SIGSEV oder so ähnlich und das Programm bricht ab, kompilieren tut es aber. Nach Aufgabenstellung ist es glaube ich nicht schlimm, wenn gleiche Wörter mehrfach eingelesen werden, da steht ja nur "Alle Wörter die mindestens einmal im Text vorkommen abspeichern". Nach dem Hinweis von "as_string" rufe ich die Funktion MD5_Update 2 mal auf. Die Arraygröße von "words" habe ich auf 1 Million erhöht, da der Text "Les Miserables" ungefähr so viele Wörter enthält und sonst nicht eingelesen werden könnte. Ist meine Gedankenweise so erst mal richtig oder ist die komplett daneben? Vielen Dank schon mal im voraus. Im folgenden noch der Code:
|
||||||||||||||||||||
Anzeige | |||||||||||||||||||||
|
|||||||||||||||||||||
19.05.2015, 11:51 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
as_string | Hallo! Ich habe gerade keine Zeit, aber was mir auf den aller ersten Blick auffällt:
Das ist ja in mehrfacher Hinsicht falsch: Du willst, dass Byte i von hash gleich Byte i von target ist, nicht dass jedes Byte von hash mit jedem in target übereinstimmt. Du brauchst keine verschachtelten for-Schleifen sondern nur einmal über die Hash-Länge laufen dafür! Außerdem setzt Du match bei jedem einzelnen Treffer auf 1 und gibst den Text aus. Du willst aber nur dann, wenn alle Bytes mit dem selben Index in den beiden Arrays übereinstimmen einmal sagen, dass alles "match"t. Ich würde deshalb zuerst match auf 1 und i auf 0 setzen. Dann eine while-Schleife machen, die so lange weiter geht, wie (match && i < HASH_LENGTH) ist. Dann die beiden Elemente der beiden Arrays an der Stelle i vergleichen. Wenn verschieden match auf 0 setzen, danach i hoch zählen und die Schleife ist fertig. Den Rest muss ich mir andersmal anschauen. Dein Fehler ist übrigens ein SEGFAULT (SIGSEGV) und tritt auf, wenn Du versuchst auf Speicher zuzugreifen, den Du noch nicht oder nicht mehr reserviert hast. Häufig, wenn z. B. ein Zeiger noch nicht initialisiert ist oder wenn Du auf ein Array außerhalb der reservierten Arraygröße versuchst zuzugreifen (out-of-bounds), oder auch, wenn eine Speicherreservierung nicht geklappt hat man trotzdem munter drauf zuzugreifen versucht, oder irgendwo einen null-pointer her hat, den man versucht zu dereferenzieren, oder oder oder... Da muss ich andersmal danach suchen dann. Gruß Marco |
||||||||||||||||||||
19.05.2015, 11:55 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
as_string | Ich glaube, dass auch das mit dem strstr und dem needle die Probleme machen könnte. Muss needle nicht ein zero-terminated string sein? Dann sollte man
scheiben, oder nicht? Gruß Marco |
||||||||||||||||||||
19.05.2015, 16:51 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
eulerscheZahl |
Da werden dann eben aus 50.000 Wörtern plötzlich 500.000. Da du immer Paare aus zwei Wörtern bilden sollst, hast du eine quadratische Laufzeit, also brauchst du 100 mal so lange. Da es bei mir auch so schon eine halbe Stunde dauert, solltest du die Auswahl so weit wie möglich einschränken. Die Lösung ist übrigens "threads help". |
||||||||||||||||||||
19.05.2015, 21:07 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | ich habe den Code entsprechend der Beschreibung von Marco nun folgendermaßen abgeändert.
Irgendwie passt das ganze aber überhaupt noch nicht. Das Programm läuft nahezu ohne Verzögerung, auch mit der großen Textdatei und die Werte von hash[i], wie auch von target[i] sind alle NULL. Also ich denke, da fehlt noch eine ganze Menge |
||||||||||||||||||||
19.05.2015, 21:14 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
eulerscheZahl | Ich sehe nicht, dass du irgendetwas sinnvolles (also 2 Wörter) an MD5_Update übergibst. Dafür brauchst du 2 verschachtelte Schleifen. Ach ja: char needle[2] = {c} Füllt alles außer das erste Arrayelement mit 0 auf, was ja '\0' entspricht. Ich habe das mal mit C# durchprobiert (damit bin ich einfach schneller):
|
||||||||||||||||||||
19.05.2015, 22:40 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
as_string | Hallo! Oh, stimmt... Das war mir nicht bewusst, dass C den Rest dann mit Nullen auffüllt. Schon wieder was dazu gelernt! Gruß Marco |
||||||||||||||||||||
19.05.2015, 23:31 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | also folgendes ist nun doch das beste was mir eingefallen ist: Der Code beginnt erst nach der while Schleife, die die Wörter aus der Datei einliest:
basierend darauf, dass ich 2 verschachtelte Schleifen für MD5_Update brauche und da ich mich etwas nach dem C# Code orientiert habe. Wäre das mit dem testen aller möglichen 2er Kombinationen per MD5 so erstmal korrekt? Ich bin mir jetzt nicht sicher, ob auch Steuerzeichen mit abgespeichert werden, das darf nach Punkt 2 der Aufgabenstellung ja nicht passieren und man soll anhand eines vorgegeben Hashwertes noch die beiden dazugehörigen Wörter finden. Vielen Dank schon mal. |
||||||||||||||||||||
19.05.2015, 23:40 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | Es darf doch nur jedes Wort, das mindestens einmal im Text vorkommt nur je einmal abgespeichert werden. In der Aufgabenstellung vom vorgegeben Code steht: "find all unique words from the book". Somit ist das doch eindeutig und wie ich gerade sehe, ist die Laufzeit sonst viel zu lang. Kann ich das mit der Funktion "strtok()" und dem gegebenen delimiter erreichen? Dies wird in Punkt 2 der Aufgabe ja auch als Hinweis angegeben. |
||||||||||||||||||||
20.05.2015, 06:47 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | so nachdem ich die ganze Nacht daran gesessen habe, habe ich nun folgendes:
die Stellen die ich noch optimieren will, habe ich kommentiert. Aber was immer mir noch nicht klar ist, wie ich nach Aufgabenstellung, Wörter zu einem Hash finden soll. Der Hash zu dem man die zwei Wörter finden soll ist 32 Zeichen lang, bei der Ausgabe, ist der dazugehörige Hash aber nur höchstens 2 Zeichen lang. Hab ich da was falsch, oder passt die Aufgabenstellung nun nicht? Mehr was ich da noch probieren könnte, fällt mir wirklich nicht mehr ein. Dass die Wörter nur einmal eingelesen werden sollen, hab ich hinbekommen, wenn auch vielleicht etwas ungeschickt. Somit hat sich der Post zuvor erst mal erledigt. |
||||||||||||||||||||
20.05.2015, 10:20 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
as_string | Das hier ergibt keinen Sinn:
Was Du willst ist doch: Vergleiche jedes Element von target mit dem entsprechenden Element von hash. Wenn es (mindestens) eines gibt, das unterschiedlichen Wert hat, dann ist es kein Treffer, wenn alle übereinstimmen ist es ein Treffer. Um diese Aussage treffen zu können musst Du doch dann aber logischerweise zuerst über die Arrays gelaufen sein und erst, wenn Du komplett ohne Unterschied durch gekommen bist, kannst Du etwas ausgeben. Dann die Bedingung: Wenn etwas in C gleich 0 ist, entspricht es false. Dein if((...) == 0) wird also immer genau dann true, wenn das in der der Klammer false ist. Es wirkt also wie ein "not". Da Du in der Klammer auf Ungleichheit prüfst, aber das Ergebnis negierst, hast Du das selbe, wie wenn Du
geschrieben hättest. Das ist aber hier so wie so Quatsch. Übrigens, als Du die while-Schleife hattest, hast Du nicht die Variablen vorher initialisiert gehabt, so wie ich Dir das sogar geschrieben hatte: Natürlich musst Du die Zählvariable bei einer while()-Schleife vor der Schleife immer wieder auf 0 setzen. Außerdem musst Du die boolsche Variable auf 1 setzen. Wenn Du aber keine while()-Schleife verwenden willst, geht das äquivalent auch mit einer for()-Schleife, etwa so:
Hab das Fragment zwar jetzt nicht ausprobiert, sollte aber tun, was es soll. Ein MD5-Hash ist immer 16 Byte lang. Wenn man die einzelnen Byte hexadezimal schreibt, bekommt man zwei Zeichen von 0-9 oder a-f für jedes Byte, also insgesamt 32. Ich weiß jetzt nicht, was Du mit 32 Zeichen meintest, allerdings. So wie Du es geschrieben hattest, gibst Du aber immer nur übereinstimmende Bytes von hash aus, was, sorry..., Quatsch ist! Der ganze Hash muss übereinstimmen, oder er stimmt eben nicht überein. Ob einzelne Byte übereinstimmen wenn nicht all, ist irrelevant. Um diesen Vergleich zu machen, brauchst Du aber eigentlich diese Schleife gar nicht selbst zu programmieren. Die C-Standardbibliothek hat schon fertige (und stark optimierte) Funktionen für solche Dinge. Z. B. :
Das sollte auch funktionieren (auch völlig ungetestet von mir!). bei memcmp, strcmp und so ist wichtig: Die Funktionen geben -1, 0 oder 1 zurück. Bei Gleichheit eine 0. Gruß Marco |
||||||||||||||||||||
20.05.2015, 19:02 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | hallo, das funktioniert irgendwie nicht. Also jetzt wird überhaupt nichts mehr gefunden.
bist du sicher, dass man das so machen muss? |
||||||||||||||||||||
20.05.2015, 19:16 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | ich denke der Hash, der gefunden werden soll, wird nicht richtig richtig generiert |
||||||||||||||||||||
20.05.2015, 21:33 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
eulerscheZahl | Das init musst du innerhalb der Schleife machen, sonst hast du noch den alten Wert drin. |
||||||||||||||||||||
20.05.2015, 21:40 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | ich versuch das mal eben. Ich dachte erst, ich müsste die Wörter so in words einlesen, dass ich in words schon alle zweier String-Kombinationen habe. Ist aber immer ein SIGSEGV Signal gekommen. Versucht hatte ich das mit der Funktion strcat(). Nach Aufgabenblatt versteh ich das aber so, dass in words erstmal nur jedes Wort einzelnd gespeichert werden soll und das mit den 2er Strings dann über MD5 läuft. Welche Variante wäre denn nun die richtige? |
||||||||||||||||||||
20.05.2015, 22:44 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | es scheint soweit jetzt zu klappen. Aber bei der Ausgabe des Hashwertes werden die Nullen nicht mit ausgegeben.
woran liegt das? |
||||||||||||||||||||
21.05.2015, 03:19 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
deppensido | ich habe die Aufgabe soweit fertig. Könnt ihr bitte nochmal schauen, ob ich die #pragma Anweisungen richtig gesetzt habe, damit das Programm schneller ausgeführt wird? Die Ausführung der großen Textdatei "Les Miserables.txt" dauert immer noch ca. 15 Minuten bis das Programm terminiert, das kann doch nicht richtig sein oder? Hier noch der komplette Code, vielen Dank im voraus und schon mal danke für die bisherigen Hilfen.
|
||||||||||||||||||||
21.05.2015, 23:51 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Karlito | Hi, Sorry für die späte Meldung. Du solltest einen Teil des Hashes (Präfix, Suffix oder Modul) als index für das Array verwenden, in dem Du die Wörter speicherst. Somit musst Du nicht jedes mal alle Wörter in der bestehenden Liste vergleichen, sondern musst nur in dem entsprechenden Eintrag schauen, ob der Hash nur zufällig gleich ist. Um dann nach gleichen Hashes zu schauen, müsstest Du nur das gesamte Array durchgehen und in Einträgen mit zwei oder mehr Wörtern schauen, ob der Hash wirklich gleich ist. Somit müsstest Du auch im Nachhinein nicht alle Wörter mit allen vergleichen, da Du die potentiellen Gleichen Hashes ja schon ermittelt hast. Der Aufwand würde sich so stark minimieren (gegenüber der aktuellen Implementierung). Gruß, Karlito |
||||||||||||||||||||
22.05.2015, 00:33 | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Karlito | Hier der Quelltext (etwas chaoitisch) von einem XML-Parser, den ich mal geschrieben habe um eine Liste aller in Wikipedia vorkommenden Wörter zu erstellen. Der Dump ist ca 12 GB groß und die Indizierung läuft in unter 10 Min. Der Hash (FNV) ist nicht 100%ig optimal. Man kann den Hash auf eine bestimmte Bit-Länge optimieren, was ich hier nicht gemacht hatte. Es ist quasi eine Hash-Tabelle, welche keine flexible Größe hat. Dabei wird das Modul des FNV-Hashes verwendet, um ein Bucket zu adressieren. In einem Bucket befinden sich dann Einträge (LinkedList von Entries) mit dem selben Hashmodul. Um einen Hash oder Wort zu Suchen muss man nur noch das Modul des Hashes als Adresse für das Bucket verwenden und bekommt die entsprechenden Einträge. Ich habe hier außerdem den Stringvergleich selbst implementiert, weil strncmp eine Edit-Distanz liefert. Dazu muss mehr Arbeit getan werden, als einfach nur nach dem ersten Unterschied zu suchen und sollte damit schneller sein. Alternativen habe ich mir noch nicht angeschaut... Gruß, Karlito
|
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |