.dat Datei auslesen

Werner Salomon

Es heißt in der Aufgabenstellung: ".. in C or your favorite language .."
d.h. C++ wäre ok, zumal ja noch gefordert ist, dass die Zahlen ".. in increasing order .." (std::sort) und ".. each number at most once .." (std::unique) ausgegeben werden sollen. Das ist natürlich mühselig in C alles 'per Hand' zu kodieren.

Die eigentliche Herausforderung sehe ich aber in der Größe der Datei - bzw. in der Anzahl der Zahlen. Das sind immerhin 2GByte, die auch noch zu einer Zeit im Speicher liegen müssen, wegen sortieren! Ich wüsste jedenfalls nicht ad hoc wie man so was 'partiell' sortieren soll.

Auf meinem etwas schwachen Haus-PC habe ich es nicht geschafft einen std::vector oder std::deque mit 500000000 Elementen a 4Byte (32Bit) anzulegen.

Gruß
Werner

hustbaer

Sortiert werden muss da gar nix - ich würde das einfach mit nem Bitmap Index machen. Braucht 512 MB RAM + IO Puffer + Kleinvieh => unter 600 MB.
Und ist in C vermutlich genau so einfach umzusetzen wie in C++.

hustbaer

MfG schrieb:

- wenn du dafür 100€ willst... wie viel willst du dann bei wirklichen problemen?

Wenn du Preisdumping betreiben willst, OK, deine Sache.
Ich hab' nicht vor jemals Auftragsarbeiten anzunehmen wo mir netto weniger als €30~40 pro Stunde übrigbleiben. Und da ist ein Hunderter *nix*. Reicht ja nichtmal für 1,5 Stunden.
Und wenn du den ganzen Overhead einrechnest (Datenfile runterladen, testen, Kommunikation + Preisverhandlung mit dem Auftraggeber, Rechnung schreiben, Programm verschicken, Abwicklung der Bezahlung etcpp.), dann sind 1,5 Stunden mMn. nicht zu hoch gegriffen.

volkard

MfG schrieb:

- wenn du dafür 100€ willst... wie viel willst du dann bei wirklichen problemen?

nix.

volkard

Werner Salomon schrieb:

Es heißt in der Aufgabenstellung: ".. in C or your favorite language .."

Ups, sorry. Dann passt es hier.

Werner Salomon schrieb:

d.h. C++ wäre ok, zumal ja noch gefordert ist, dass die Zahlen ".. in increasing order .." (std::sort) und ".. each number at most once .." (std::unique) ausgegeben werden sollen. Das ist natürlich mühselig in C alles 'per Hand' zu kodieren.

Naja, nicht wirklich.
Mit fopen, fseek und fread(&i,4) kann man fein einzelne Zahlen rauspicken.
Dann muss man ja abgeben

while(!sorted())
   swap(file[rand()%max],file[rand()%max]);

Ich bin nicht direkt dafür zuständig, daß Herr Miltenberger einen zu lahmen Rechner hat, oder? Das gibt ne 1 oder ne 5. Ne 4, wenn man nachweist, daß mit echtem Zufall statt rand() der Erwartungswert der Laufzeit endlich ist. ⁽¹⁾

Werner Salomon schrieb:

Die eigentliche Herausforderung sehe ich aber in der Größe der Datei - bzw. in der Anzahl der Zahlen. Das sind immerhin 2GByte, die auch noch zu einer Zeit im Speicher liegen müssen, wegen sortieren! Ich wüsste jedenfalls nicht ad hoc wie man so was 'partiell' sortieren soll.

Da fallen mir Lösungen ein wie anderen Schuppen von den Haaren. Direkt mal memorymapping und sort/unique. Falls der Rechner nicht genug virtuellen Speicher für die Datei hat, einfach selber nachbauen, das geht in C++ lecker, habs auf nem 386-er schon gemacht. Quicksort/Mergesort sollten mit wenigen Views auskommen und der Nachbau sollte fast keine Performance fressen bei sagen wie mal 64k View-Größe und davon nicht mehr als 5. Die Sprungvorhersagen haben fast immer recht.

op[](size_t index){
   size_t page=index/65536;
   if(loaded[page])
      return pages[page][index%65536];
   else{
      unloadRandomPage();
      loadPage(page);
      return (*this){index];
   }
}

Gerne auch das damals auf Bändern übliche Mergesort, ob Bänder oder Dateien ist fast egal.

Werner Salomon schrieb:

Auf meinem etwas schwachen Haus-PC habe ich es nicht geschafft einen std::vector oder std::deque mit 500000000 Elementen a 4Byte (32Bit) anzulegen.

Muss ja nicht im RAM sein. Sagen wir mal selbe AUfgabenstellung aber mit 200G Daten voller 64-bittiger unsigneds. Ok, der 64-Bit-Prozzi packt mmap damit und einfach sort/unique. Nehmen wir einen 32-Bit-Professor. Mergesort und Radixsort(sagen wie mal 256, also 8 Läufe) schreien doch danach genommen zu werden. Ist beides stante pede fürchterlich schnell, dann noch ein wenig an die zu erwartende Hardware anpassen.

⁽¹⁾ Ich hab mal in der Vorlesung "Expertensysteme" fast so viel geschlafen wie der Prof, den die Vorlesung noch viel weniger interessiert hatte. Es kam einfach NULL Inhalt rüber. Unser Job: Die angegebenen Bücher lesen und ein Expertensystem bauen…
Volki hat sich keins der Bücher gekauft. Die waren auch zu 99% supi abstrakt. Uha, ein Inferenzsystem kommuniziert mit einer Benutzerschnittstelle. Nette Bildchen im Buch. Volki hat auch lieber 500000000 Elementen a 4Byte gestreichelt, das hat ja sonst keiner gemacht. Drei Wochen vor Abgabe fängt die Panik an. Zwei Wochen vor Abgabe baute ich schnell mal was und es ward Scheiße. Eine Woche vor Abgabe baute ich schnell was und es war zwar lauffähig und schlauer und lernfähiger als ein Knäckebrot, aber sie war

"weder "
for(;;) 
  "$${setze beliebige positive Eigenschat von Software ein} noch "

Hab dann http://condor.depaul.edu/elliott/250/animal.lsp abgegeben!!! Ein Lisp-Programm zur Demo, daß Rechner lernen können. Hab alle Kommentare, Zeilenunbrüche und Einrückungen weggemacht und alle Bezeichner von vorn nach hinten durch a, b, c, d, e… ersetzt, hab die Überschrift der Vorlesung angepaßt, und die Kacke abgegeben. Das Prog hieß "Expertor II" und hatte schonmal den besten Namen von allen.
Nu war der Prof auch noch ein geborener Lisp-Hasser! Das wußte ich vorher nicht. Er wußte, aus anderen Vorlesungen, daß ich mir eigentlich keine 2 gönne, nichtmal in Grundlagenvorlesungen, die nicht in die Diplomnote eigehen. Während andere auf dem Digitalschaltbrett Mühe hatten, eine Schaltung zu bauen, die ihre Initialen in ASCII erkennt, hab ich ihm gezeigt, wie man mit wenigen Gattern und dem 4-Bit-Schieberegister einen ansehnlichen Pseudozufallszahlengenerator baut. Er war vorher vollkommen sicher, mit diesem Müll könne man nicht zaubern. Funktion des Expertors II wurde vorgeführt: Das Prog konnte nur ganz schlichte Tatsachen lernen. Aber naja, es konnte. Prof fragte nach lauter Details, inwiefern was wie von den Büchern umgesetzt wurde und Volki schaute auf seine Schuhspitzen und wackelte mit den Schultern und sagte "aber es lernt doch". Nach einer Minute war das Terrain abgesteckt: Ich hatte keine Ahnung was er will und er hatte keine Ahnung, was ich kann. Patt.
Dann Vorstellung des Codes. *lol*
Er hat schallend gelacht. Dieses Lachen von ihm ist auf jeden Fall eine meiner schönsten Erinnerungen an die Studienzeit.

SeppJ

Um mal beim Thema zu bleiben: Der Threadersteller hat doch eine klare Frage gestellt und nicht nach einer Komplettlösung verlangt:

Wie kann ich in C++ eine .dat auslesen, welche binär gespeichert ist bzw. die mir auf der Konsole die richtigen Zahlen anzeigt und nicht irgendein Kauderwelsch?

Auf so etwas geben wir doch normalerweise gerne Antwort? Ich jedenfalls gebe eine:
Zuerst einmal müssen wir wissen, wie genau die Zahlen abgespeichert sind, denn einfach nur "binär" sagt nicht viel. In der Aufgabenstellung steht, dass das signed, little-endian, 32-bit Integer sind. (Ich gehe im Folgenden davon aus, dass du weißt, was Endianess ist, ansonsten schlag es im Lexikon nach). signed 32-Bit Integer können wir in C++ ganz einfach bekommen. Wenn wir std:uint32_t aus cstdint nehmen, haben wir genau den Datentyp, den wir brauchen. Aber wie steht es mit der Endianess? Eher schlecht, denn C++ (und auch C) machen keinerlei Vorgaben, wie die Datentypen intern funktionieren. Das heißt, genau genommen können wir kein Annahmen zur Endianess machen. Wir können vielleicht irgendwelche tollen Präprozessormakros benutzen, um zur Compilezeit die Endianess der Zielplattform zu bestimmen. Oder zur Not einen Test zur Laufzeit machen. Wie auch immer: Was machen wir mit dem Ergebnis?

Wenn unsere Plattform little Endian benutzt (oder wir einfach frech annehmen, dass sie das benutzt, ohne zu testen, weil die meisten Desktopcomputer little endian benutzen), dann sind wir fertig, dann können wir einfach ifstream::read benutzen und bekommen passend unsere Werte.

Wenn unser Plattform big endian benutzt, dann müssen wir die Daten transformieren. Es gibt da sicher irgendwelche tollen Tricks oder vorgefertigte Funktionen (vielleicht Funktionen zur Netzwerkkommunikation, da dort dieses Problem auch auftaucht?), aber: Wir können mittels Mathematik auch eine ganz allgemeine Lösung schreiben, die funktioniert, ganz egal welche Endianess unsere Maschine verwendet. Funktioniert auch für Little Endian, ist bloß nicht ganz so optimal wie das im vorherigen Absatz beschriebene read, dafür muss man sich keinerlei Sorgen machen. Wie macht man das mit Mathematik? Wir wissen ja, was Endianess bedeutet, das ist einfach nur eine Zahlendarstellung, aus dieser können wir den Zahlenwert ausrechnen, ohne uns kümmern zu müssen, wie es intern dargestellt wird. Wir haben in den Daten 4 Byte, die unsere Zahl darstellen, das erste Byte zählt am wenigsten, das vierte am meisten. Jede Stelle hat 256 Möglichkeiten (oder 1 << 8, da ein Byte (hier) 8 Bit hat). Daher ist der Zahlenwert:

uint32_t value =   byte[0] * (1 << 0*8)
                 + byte[1] * (1 << 1*8)
                 + byte[2] * (1 << 2*8)
                 + byte[3] * (1 << 3*8)

Und so hätten wir unseren Zahlenwert vollkommen plattformunabhängig gelesen bekommen.

edit: Nein, haben wir nicht. Ich habe das signed vergessen. Hier haben wir ein Problem, wenn wir plattformunabhängig sein wollen: Wir wissen nicht, wie das Vorzeichen der Zahl in der Datei dargestellt ist und es gibt auch keine Angabe in der Aufgabenstellung. Wahrscheinlich ist es Zweierkomplement. wir könnten es in der Datei nachgucken, da wir die ersten paar Zahlen kennen. Wahrscheinlich kommen gar keine negativen Zahlen vor, da die Aufgabenstllung sagt, man solle bei 0 anfangen (vielleicht will der Aufgabensteller einen auch extra rein reiten). Insgesamt müssten wir dies aber bei der Rechnung berücksichtigen. Ich komme aber zu dem Schluss, dass dies wahrscheinlich nicht Kernbestandteil der Aufgabenstellung ist und wir höchstwahrscheinlich einfach davon ausgehen sollen, dass unser lokaler Rechner das gleiche Zahlenformat hat, wie der Rechner auf dem die Datendatei erstellt wurde. Das heißt, das vorgeschlagene read ist vermutlich die gesuchte Lösung. Aber nun hast du sehr viel Text um zu begründen, warum read genommen werden sollte und was die Alternativen wären .

@volkard: Hier muss man doch wirklich gar nicht sortieren und auch nicht unique'en. hustbaer ist da glaube ich schon auf dem richtigen Pfad. Einen index zu erstellen klingt viel cleverer und effizienter.

hustbaer

Ja, nix sortieren.
Wie effizient das ist trau ich mich nicht abschätzen. Könnte sogar mieser laufen als mit sortieren -- vorausgesetzt man bringt beim Sortieren alles ins RAM (ohne Paging). Wegen mieser Cache-Ausnutzung beim Index Erstellen (ausgenommen die Zahlen im File bliden schöne "Klumpen" - was aber ein Sonderfall wäre).
Dafür braucht es wenig Speicher und ist watscheneinfach zu implementieren.

Und abgesehen davon haben wir doch gerade erst vor ein paar Wochen ne ähnliche Aufgabenstellung durchgenommen.
Die "Lösung" die dabei "erarbeitet" wurde war:
* In Blöcke die ins RAM passen aufteilen
* Jeden Block quicksorten und in ein Temp-File schreiben
* Finaler streaming merge Pass über alle Blöcke gleichzeitig

Wobei der finale Pass natürlich kein N-Way merge sort ist, sondern ein binärer Baum aus lauter 2-way Mergern die ihren Input von jeweils zwei weiteren 2-way Mergern holen bzw. in der letzten Ebene von File-Readern holen.

@volkard
Ich wette nen zu fressenden Besenstiel dass dein "virtual memory merge sort" um einiges langsamer ist als mein "streaming merge".

Werner Salomon

Hallo hustbär,

man lernt doch nie aus.

hustbaer schrieb:

Sortiert werden muss da gar nix - ich würde das einfach mit nem Bitmap Index machen. Braucht 512 MB RAM + IO Puffer + Kleinvieh => unter 600 MB.

Da ich kein Informatiker bin, sagt mir 'Bitmap Index' gar nix. Ich habe mir zwar die Wiki-Seite angeschaut, aber wie man das einsetzt um die Zahlen in aufsteigender Reihenfolge auszugeben, ist mir ein Rätsel.

Kanst Du da mal einen Hinweis geben, wie das funktioniert.

Gruß
Werner

volkard

SeppJ schrieb:

@volkard: Hier muss man doch wirklich gar nicht sortieren und auch nicht unique'en. hustbaer ist da glaube ich schon auf dem richtigen Pfad. Einen index zu erstellen klingt viel cleverer und effizienter.

Ähm. Logo. Dachte, die totale Dominanz des Ausstreichens (sowohl in Sachen Laufzeit als auch in Sachen Programmierzeit) ist so sonnenklar, daß ich da nicht mehr näher drauf eingehen muss.
Hab mich wohl getäuscht, da Du UND hustbaer mich drauf hinweisen.

volkard

Werner Salomon schrieb:

Kanst Du da mal einen Hinweis geben, wie das funktioniert.

vector<bool> v(500000001);//Nach über 10 Jahren der erste Einsatz dieses komischen Containers!
while(in>>i)
   v[i]=true;
for(each possible i)
   if v[i]
      writeln(v[i]);

Werner Salomon schrieb:

man lernt doch nie aus.

Wenn Dir sowas Spaß machst, lies Programmimng Pearls von Bentley.

hustbaer

@volkard
Bin schon zu oft davon überrascht worden dass jmd. etwas nicht verstanden hat oder nicht auf eine bestimmte Idee gekommen ist, dass ich da kaum mehr Annahmen treffe.
Zumindest nicht wenn so wie bei deinem Beitrag so überhaupt kein Hinweis darauf da ist.