Ascii sortieren mit c++



  • Liebe Forengemeinde,

    da ihr mir schon die letzten beiden Male so gut helfen konntet, habe ich mal wieder eine Frage.
    Ich schreibe momentan riesige ascii-files (Im Grunde 4 Einträge mit double Zahlen) die z.T. 3.5 GB groß sind. Leider muss ich das file nach dem schreiben sortieren (habe es bis jetzt immer unter linux mit sort -n gemacht, leider sind es jetzt dezimalzahlen, und der befehl geht nicht mehr). Könnte man das ggf. mit c++ machen ohne viel Aufwand?
    Ich weiß nur wie ich Vektoren sortieren, aber ein so großen vektor wird mein PC wohl leider nicht schaffen.

    Danke für die Hilfe



  • Hast du das schon probiert? 3.5 GB passen noch knapp in den Programmspeicher, wenn du einen PAE-Kernel verwendest. Sonst wird das knapp, aber du musst ja nicht alle 3.5 GB im Speicher haben, doubles sind in der Regel etwas kompakter als ihre ASCII-Formatierung. Ausserdem kann der Kernel ja noch Swappen.

    Kannst ja mal schauen, ob das hier funktioniert:

    struct line { double a, b, c, d; };
    bool operator<(line const& lhs, line const& rhs) { return lhs.a < rhs.a; }
    std::istream& operator>>(std::istream& in, line& l) { return in >> l.a >> l.b >> l.c >> l.d; }
    std::ostream& operator<<(std::ostream& os, line const& l) { return os << l.a << ' ' << l.b << ' ' << l.c << ' ' << l.d; }
    
    int main() {
      std::istream_iterator<line> i(std::cin), e;
      std::vector<line> v(i, e);
      std::sort(v.begin(), v.end());
      std::copy(v.begin(), v.end(), std::ostream_iterator<line>(std::cout, "\n"));
    }
    

  • Mod

    Drei Anmerkungen:
    1. Als double-Datentyp im Speicher sollten deine Zahlen deutlich kleiner sein als geschrieben in einer Datei. Im Zehnersystem geschreiben ist ein double ungefähr 16 Byte lang, im Arbeitsspeicher gespeichert aber nur 8.
    2. Brauchst du deine Zahlen tatsächlich sortiert oder kann es sein, dass du bloß glaubst, dass du sie sortieren müsstest, um etwas ganz anderes zu erreichen (was eventuell viel einfacher geht)?
    3. Falls du wirklich sortieren musst und konventionelle Verfahren an der Datenmenge scheitern, dann wirst du wohl zu sogenannten "externen" Sortierverfahren greifen müssen. Die Grundmethodik ist wie beim Mergesort: Du sortierst kleinere Blöcke, speicherst die Zwischenergebnisse irgendwo ab und fügst aus den sortierten Blöcken das Endresultat zusammen.



  • Hallo!

    @sarten Danke werde es morgen mal ausprobieren.

    Also ich glaube ich muss es sortieren. Da die erste variable die Zeit ist und anschließend die sortierte Version ausgelesen wird und events festlegen (immer wenn der Zeitunterschied zwischen 2 zeilen zu gering wird ist es ein event, ansonsten ein neues). Natürlich könnte ich auch alle 110.000.000 Millionen Zeilen einlesen und schauen ob eine Zahl die Bedingung erfüllt, glaube aber leider, dass es länger dauert.

    Gute Nacht!



  • Evtl ist es besser, wenn du die Zahlen vor dem auf die Platte schreiben sortierst (so sparst du dir das erneute auslesen & schreiben), oder bei dieser Datenmenge evtl. es in eine Datenbank schiebst.



  • Ich verstehe Dein Datenformet noch nicht. Du schreibst jeweils,vier doubles auf einmal und der erste wert ist die Zeit und dass machst Du n-mal. Und dann musst Du alle ersten Werte sortieren. Oder ist es was anderes?


Log in to reply