011
11.04.2009, 18:29 Uhr
~pizer
Gast
|
Hier ist eine alternative C++ Version, die bei mir etwa 60% schneller läuft.
| C++: |
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <cassert>
using std::string;
using std::set;
using std::map;
using std::make_pair;
using std::pair;
using std::vector;
using std::cout;
using std::endl;
struct my_str_comp_t
{
// Die genaue Reihenfolge ist ja nicht so wichtig
// Diese Sortierung ist ein kleines bischen schneller
bool operator()(string const& a, string const& b)
{
const string::size_type al = a.length();
const string::size_type bl = b.length();
if (al==bl)
return a<b;
else
return al<bl;
}
};
int main()
{
using std::srand;
using std::rand;
using std::time;
typedef pair<const string*,const string*> str_ptr_pair_t;
typedef vector<const string*> str_ptr_vector_t;
// Speichere jedes Wort nur einmal ab im "Wort Cache".
// Dann werden nur noch zeiger auf const strings benutzt.
set<string, my_str_comp_t> words;
map<str_ptr_pair_t,str_ptr_vector_t> triples;
srand(time(NULL));
const string* pw1 = 0;
const string* pw2 = 0;
string temp;
while (std::cin >> temp) {
const string* pi = & * words.insert(temp).first;
// pi zeigt auf string object im cache
triples[make_pair(pw1,pw2)].push_back(pi);
pw1 = pw2;
pw2 = pi;
}
triples[make_pair(pw1, pw2)].push_back(
& * words.insert(".").first
);
pw1 = pw2 = 0;
for (int n=0; n<1000; ++n) {
str_ptr_vector_t const& third = triples[make_pair(pw1,pw2)];
assert(!third.empty());
const string* pi = third[rand() % third.size()];
// pi zeigt auf string object im cache
if (*pi == ".") break;
cout << *pi << ' ';
pw1 = pw2;
pw2 = pi;
}
cout << endl;
return 0;
}
|
Bzgl string-Zuweigung: Ich würde eigentlich vermuten, dass
langsamer ist (zumindest wenn die c++stdlib Implementierung kein "copy-on-write" benutzt, was ja wieder aus der Mode zu kommen scheint) als
| C++: |
w1.swap(w2);
w2.swap(i);
// i == altes w1, ist aber egal in diesen Fall
|
Vielleicht probiert mal jemand noch "unordered_set" bzw "unordered_map" von Boost/TR1 aus...
Gruß,
pizer |
