alphabetisches Sortieren von Wörtern

Nathan schrieb:

Und seit wann werden die Werte bei ints ohne weiteres Argument auf 0 gesetzt?

Seit es vector gibt Ist übrigens ein weiterer Vorteil von vector gegenüber einem rohen Array.

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller, aber trotzdem sollte man resize() nicht empfehlen, wenn es doch auch reserve() gibt.

Nathan

Oh ja, stimmt ja.
Wusste ich gar nicht... Naja, habe es bisher noch nie wirklich gebraucht.^^

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller

Davon rede ich ja die ganze Zeit.

Nathan schrieb:

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller

Davon rede ich ja die ganze Zeit.

Ja, aber wayne?
Wenn man kurzen und schönen Code will, nimmt man push_back und wenn man schönen und schnellen Code will nimmt man reserve+push_back. resize hat da gar nichts zu suchen.

Nathan

OK, du hast Recht: TE, verwende reserve() und push_back(), sofern dein Backslash-Problem gelöst ist.
Zufrieden?
Und was hat Sone damit zu tun?

kaenzign

Nathan schrieb:

OK, du hast Recht: TE, verwende reserve() und push_back(), sofern dein Backslash-Problem gelöst ist.
Zufrieden?
Und was hat Sone damit zu tun?

Glaube du hast mich falsch verstanden
Genau dann wenn ich push_back() verwende, gibt mir die Funktion am schluss nur die Hälfte der Liste sortiert aus. Reserve() und Resize() ändern daran irgendwie nichts. Wie gesagt, meine vermutung ist, dass es ein Zusammenhang mit '\n' hat, mir ist jedoch nicht klar, wie ich das Problem umgehen kann.

Nathan

Der Fehler ist seltsam...
Übrigens geht das Bestimmen der Größe auch einfacher:

is.seekg (0, ios::end);
length = is.tellg();
is.seekg (0, ios::beg);

Mit seekg bestimmst du die Leseposition im File, abhängig von der Position, die im zweiten Parameter angegeben wird.

kaenzign

@Nathan

Aber wenn du tellg() auf den Schluss des Files anwendest, gibt er dir die Anzahl Zeichen und nicht die anzahl Zeilen zürich, oder?

Ich habe jetzt mal aus spass die Anzahl der einzulesenden Zahlen im .txt-file geändert. Komischerweise funktioniert die push_back() methode jetzt gar nicht mehr, obwohl ich nichts am Code veränderd habe.
Die Konsole gibt nun nach dem Start des Programms folgendes aus:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Process returned 3 (0x3)   execution time : 4.672 s
Press any key to continue.

Die >> Methode mit vorherigem resize() funktioniert aber nach wie vor...
Hier noch mal beides als Vergleich:

for(unsigned int i = 0; i!=lines; i++)
{
    int tmp;
    fin >> tmp;
    liste.push_back(tmp);
    i++;
}

liste.resize(lines);
for(unsigned int i = 0; i!=lines; i++) 
{
    fin >> liste[i];
}

Sollten doch eigentlich letztendlich genau dasselbe tun... Woran kann das liegen?

PS: Zur Erinnerung, der gesamte Code ist auf Seite 2 geposted.

for(unsigned int i = 0; i!=lines; i++)
{
    int tmp;
    fin >> tmp;
    liste.push_back(tmp);
    i++;
}

Schau dir mal ganz genau an, was da mit i passiert.

kaenzign

bist_du_sone? schrieb:

Schau dir mal ganz genau an, was da mit i passiert.

Hmm worauf willst du hinaus. So wie ich das sehe wird die Schleife "lines"-mal durchlaufen bzw. push_back() wird "lines"-mal ausgeführt, und es sollen "lines" Zahlen eingelesen werden, das ist doch in Ordnung?

Nathan

Nein, denn i wird zweimal inkrementiert.

kaenzign

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

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

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.