alphabetisches Sortieren von Wörtern

[kaenzign]

Unglaublich wie ich das übersehen konnte.
Jetzt funktioniert es natürlich, danke dir.

[bist_du_sone?]

kaenzign schrieb:

Jetzt funktioniert es natürlich

Toll, jetzt kann man nach Alternativen suchen:
1)

int main()
{
  std::ifstream in("data.txt");
  std::vector<std::string> lines;
  for (std::string s; getline(in, s);)
    lines.push_back(s);
  std::sort(lines.begin(), lines.end());
  std::copy(lines.begin(), lines.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

struct line : std::string {};
std::istream& operator>>(std::istream& in, line& l) { return getline(in, l); }

int main()
{
  std::ifstream in("data.txt");
  std::vector<std::string> lines(std::istream_iterator<line>(in),
                                 std::istream_iterator<line>{});
  std::sort(lines.begin(), lines.end());
  std::copy(lines.begin(), lines.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

[Nathan]

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

[bist_du_sone?]

Nathan schrieb:

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

Würde mich echt wundern, ob das schneller ist. Misst du das mal?

[volkard]

Nathan schrieb:

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

??

Die Kosten des Wachsens beim push_back werden immer total überschätzt.
Nehmen wir an, daß der vector die Größe des internen Arrays immer verdoppelt, wenn das neue Element nicht reinpaßt. Und nehmen wir an, es werden 1Mio Werte eingetragen.
Startgröße mal 16 nehmen, ist aber recht egal.
Beim 17-te push_back müssen 16 Zahlen geschrieben werden.
Beim 33-ten push_back müssen 32 Zahlen geschrieben werden.
...
Beim 524289-ten push_back müssen 524288 Zahlen geschrieben werden.
Macht zusammen 1048576 Schreibungen. Also bloß eine Schreibungen pro push_back!
Und wenn man Pech hat, bis zu zwei. Aber mehr dann auch nicht. Natürlich macht man reserve, wenn es spürbar was bringt. Aber für so Kinkerlitzchen mache ich es regelmäßig nicht. Erst, wenn der Hauch einen Schimmers einen Verdachts darauf besteht, daß es am Ende spürbar sein könnte. Vorher schmiere ich mir damit meinen Code nicht voll. Und schon gar nicht zwanghaft.

Sobald mit den Daten irgendwas gerechnet wird, überwiegen andere Kosten.

Beim resize hätte man eine nutzlose Schreibung pro push_back, was durchaus vergleichbar mit 1-2 Schreibungen durch push_back ohne reserve ist.

[Nathan]

Habe ich mal gemacht (einfach nur mit einer steady_clock und mit hoher Prozessorauslastung (Browser, Skype, CB...), also vielleicht nicht ganz ausschlaggebend.
10.000.000 int-Werte mit rand() eingefügt:
1. resize() + operator[]: 0.234
2. reserve() + push_back(): 0.702
Das Ergebnis überrascht mich schon irgendwie...

[volkard]

Nathan schrieb:

Habe ich mal gemacht (einfach nur mit einer steady_clock und mit hoher Prozessorauslastung (Browser, Skype, CB...), also vielleicht nicht ganz ausschlaggebend.
10.000.000 int-Werte mit rand() eingefügt:
1. resize() + operator[]: 0.234
2. reserve() + push_back(): 0.702
Das Ergebnis überrascht mich schon irgendwie...

Absolut unglaubwürdig.

Mach einen release-Build.
Man die Optimierungen an, falls nicht schon geschehen.
Mach die Bereichsüberprüfungen aus.
definiere NDEBUG.
Lass die Messung je 100-mal laufen und nimm die schnellste Zeit, das ist die, wo Windows am wenigsten stören reinpfuscht.

[Nathan]

Nach 100-Testläufen hätten wir:
0,2028 für resize() und 0,2496 für reserve().

[volkard]

Nathan schrieb:

Nach 100-Testläufen hätten wir:
0,2028 für resize() und 0,2496 für reserve().

Zeig mal das Meßprogramm.
Die Zeiten könnten stimmen.

[Nathan]

#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>
#include <algorithm>

const std::size_t COUNT = 10000000;

int main()
{
    using namespace std::chrono;

    std::ofstream file("resize.txt", std::ios::out | std::ios::app);
    std::vector<int> vector;
    vector.resize(COUNT);

    steady_clock::time_point t1 = steady_clock::now();

    for (std::size_t i = 0; i < COUNT; ++i)
        vector[i] = std::rand();

    steady_clock::time_point t2 = steady_clock::now();

    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
    file << time_span.count() << std::endl;

    return 0;
}

Für reserve() dementsprechend.

[bist_du_sone?]

So geht das aber nicht, das resize musst du mitmessen.

steady_clock::time_point t1 = steady_clock::now();

#ifdef RESIZE 

  vector.resize(COUNT);

  for (std::size_t i = 0; i < COUNT; ++i)
    vector[i] = std::rand();

#else

  vector.reserve(COUNT);
  for (std::size_t i = 0; i < COUNT; ++i)
    vector.push_back(std::rand());

#endif

  steady_clock::time_point t2 = steady_clock::now();

resize: 0.30115
reserve: 0.292639

Ich würde aber immer push_back verwenden, weil resize ist nicht exception-neutral.

[Nathan]

OK, das mitgemessen habe ich bei beiden: 0.2495 ^^

Edit: und push_back() ist nur exception-neutral, solange kein neuer Speicher angefordert werden muss.
Ein Vorschlag: Wir einigen uns auf deque für stark-wachsende Arrays.

[Resizer]

... Und Du kisst die ganze Zeit den Aufruf für rand() mit. Das musst Die azeit musst Du mch separät messen und davon subtrahieren.

[kaenzign]

bist_du_sone? schrieb:

kaenzign schrieb:

Jetzt funktioniert es natürlich

Toll, jetzt kann man nach Alternativen suchen:

struct line : std::string {};
std::istream& operator>>(std::istream& in, line& l) { return getline(in, l); }

int main()
{
  std::ifstream in("data.txt");
  std::vector<std::string> lines(std::istream_iterator<line>(in),
                                 std::istream_iterator<line>{});
  std::sort(lines.begin(), lines.end());
  std::copy(lines.begin(), lines.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

Hätte da ein paar Fragen dazu
1. Was bedeutet der ':' in der ersten Zeile?
2. Warum überladest du zuerst den '>>'-Operator und verwendest ihn dann nicht in der Main funktion?
3. Das 3te Argument der copy()-Fkt. (letzte Zeile) ist ein Konstruktor der Klasse "ostream_iterator" oder? Muss man für den Auruf eines Konstruktors nicht zuerst ein Objekt der Klasse erstellen, auf das er ausgeführt werden soll?
Also z.B.

std::ostream_iterator<std::string> it(std::cout, "\n"));

oder die lange Version:

std::ostream_iterator<std::string> it = ostream_iterator(std::cout, "\n")

[Nathan]

1. Das : bedeutet, dass line von std::string erbt. Lies einfach weiter in deinem Buch/Tutorial mit dem du C++ lernst.
2. Der ostream_iterator braucht den << Operator um das auszugeben.
3. Nein, man kann auch einen temporären Wert übergeben.

[dd++ 0]

von mir noch der Hinweis:

http://www.google.de/#hl=de&tbo=d&sclient=psy-ab&q=never+derive+from+std:%3Astring

[volkard]

...

[kaenzign]

Mit der Theorie der Vererbung bin ich eigentlich schon einigermassen vertraut, mit der praktischen Anwendung jedoch überhaupt nicht.
Was bezweckst du denn hier mit dem Erben von String?

PS: Gibt es irgendeine Seite, wo man nachschauen kann, wie alle Klassen, Funktionen, etc. von den vorgegebenen C++ Libraries implementiert sind?

[Nathan]

Die Implementierung ist zum Teil compiler-abhängig.
Eine Übersicht über das, was du als Anwender brauchst, findest du z.B. hier:
http://www.cplusplus.com/reference/

[*Rewind*]

Siehe bitte http://www.c-plusplus.net/forum/310212 unter Referenzen. Falls du dich wirklich für die technische Umsetzung der Funktionen interessierst, kannst du jederzeit die Header öffnen oder anzeigen lassen. In Buchempfehlungen gibt's bestimmt auch Einiges, das man als Referenz nehmen kann. Mein Tipp: "The C++ Standard Library" von Josuttis