Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » STL Performance, die 2.

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
07.04.2009, 15:30 Uhr
Bruder Leif
dances with systems
(Operator)


Moin!

Ich sitz hier gerade mit einem kleinen Testprogramm (wer sich fuer den Algorithmus interessiert, google nach "Markov"), das in C++ deutlich langsamer laeuft als Perl. Als Testeingabe diente dabei die Lutherbibel, weil schoen gross

Liegt das an meinem Rechner, oder ist das bei Euch auch so? Hab ich Best Practices zur STL verletzt? Buh?


C++:
#include <iostream>
#include <string>
#include <map>
#include <utility>
#include <vector>
#include <cmath>
#include <ctime>

typedef std::vector<std::string> stringvector;
typedef std::pair<std::string, std::string> stringpair;

int main()
{
    std::map<stringpair, stringvector> triples;
    srand(time(NULL));

    std::string w1, w2, i;
    while (std::cin >> i) {
        triples[stringpair(w1, w2)].push_back(i);
        w1 = w2;
        w2 = i;
    }
    triples[stringpair(w1, w2)].push_back(".");

    w1 = w2 = "";
    for (int n=0; n<1000; ++n) {
        stringvector& third = triples[stringpair(w1, w2)];
        i = third[rand() % third.size()];
        if (i == ".") break;
        std::cout << i << " ";
        w1 = w2;
        w2 = i;
    }

    return 0;
}




Code:
#test.pl
while(<>) {
    for(split) {
        push @{$triples{$w1}{$w2}}, $_;
        ($w1, $w2) = ($w2, $_);
    }
}
push @{$triples{$w1}{$w2}}, '.';

($w1, $w2) = ('', '');

for $len (1..1000) {
    @words = @{$triples{$w1}{$w2}};
    $i = $words[int(rand($#words+1))];
    last if $i eq '.';
    print "$i ";
    ($w1, $w2) = ($w2, $i);
}



Und nicht nur Perl:


Code:
Laufzeiten.txt

C#:     3.040
Python: 3.219
Java:   3.891
LUA:    3.937
Perl:   4.671
AWK:    4.812
C++:    7.235
Tcl:    8.422



Wenn ich die Zeit dazu hab, mach ich noch eine C-Version. Aber DAS ist doch mal... glumpf...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Dieser Post wurde am 07.04.2009 um 15:38 Uhr von Bruder Leif editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
07.04.2009, 16:12 Uhr
0xdeadbeef
Gott
(Operator)


In der Perl-Version benutzt du eher eine std::map<std::string, std::map<std::string, std::vector<std::string> > >, oder? Ich müsste das Laufzeitverhalten jetzt ausrechnen, aber dass dabei unterschiedliche Ergebnisse rauskommen, erstaunt mich wenig.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
07.04.2009, 22:57 Uhr
Bruder Leif
dances with systems
(Operator)


Klar, dass es nicht genau das selbe ist; aber ich hatte nicht erwartet, dass die Performance dermassen stark darunter leidet, dass Perl C++ so davonrennt. Ich probiers morgen mal mit der gleichen Struktur, mal sehen, was dann draus wird...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
07.04.2009, 23:19 Uhr
0xdeadbeef
Gott
(Operator)


Ich bin nicht sicher, ob das direkt die Laufzeit stark beeinflusst. Ich hege ein bisschen die Vermutung, dass das Hantieren mit den ganzen std::pairs und das daraus resultierende Hin- und Herkopiere mehr damit zu tun haben.

Wenn du es aber genau wissen willst, lass einen Profiler drüber laufen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
08.04.2009, 12:59 Uhr
Bruder Leif
dances with systems
(Operator)


OK, jetzt wird die Sache interessant. Alter Rechner mit OpenBSD:


Code:
C:       13
C#:      31
AWK:     41
Python:  49
Perl:    54
Java:    60
C++:     67
LUA:     67
Tcl:    254



C++ enttaeuscht, ansonsten hatte ich das Ergebnis so erwartet. Schon eher was als unter Windoof. Lustig, der Profiler meint, 37% der Laufzeit haengen in std::string::compare, dicht gefolgt vom RB-Tree der std::map. Tolle Implementierung... ich bastel mir mal eine HashMap und probiers damit...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
09.04.2009, 17:50 Uhr
0xdeadbeef
Gott
(Operator)


Magste den fertigen Code mal herzeigen, und haste vielleicht nen Link zu den Eingabedaten? Ich besitze keine Lutherbibel, und ich hätte auch wenig Lust, sie abzutippen.

Ich würde gern mal ein bisschen damit rumspielen und sehen, ob ich da noch was rausgeholt kriege.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
10.04.2009, 00:15 Uhr
Bruder Leif
dances with systems
(Operator)


Moin! Dann kopier ich mal ein bisschen Code hierher...

C++ steht oben, habs mit word1 + " " + word2 probiert (statt std::pair) -- noch schlimmer...

In C hab ich "geschummelt", wenn man davon sprechen kann, weil halt noch keine fertige Datenstruktur da war; und ich hab boese ausgenutzt, dass die gesamte Datei am Stueck im Speicher steht, also kein Rumkopieren von Strings. Ausserdem ein Hash statt RB-Tree; ein paar der Skriptsprachen machen das auch so:


C++:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

/******************************************************************************/

enum { BUCKETS = 16384 };

/******************************************************************************/

unsigned int hash(char* word1, char* word2)
{
        unsigned int ret = 17;
        while (*word1) ret = ret * 31 + (unsigned char) *word1++;
        while (*word2) ret = ret * 31 + (unsigned char) *word2++;
        return ret % BUCKETS;

}

/******************************************************************************/

typedef struct tagSuffix {
        char* suf;
        struct tagSuffix *next;
} suffix;

/******************************************************************************/

typedef struct tagEntry {
        char* word1;
        char* word2;
        int suffixCount;
        suffix* suffixes;
        struct tagEntry* next;
} entry;

/******************************************************************************/

void putHash(entry* words[], char* word1, char* word2, char* suf)
{
        suffix* newSuffix = malloc(sizeof(suffix));
        unsigned int hashVal = hash(word1, word2);
        entry* tmp = words[hashVal];

        while (tmp) {
                if ((tmp->word1 == word1) && (tmp->word2 == word2)) break;
                if (!strcmp(tmp->word1, word1) && !strcmp(tmp->word2, word2)) break;
                tmp = tmp->next;
        }

        if (!tmp) {
                tmp = malloc(sizeof(entry));
                tmp->word1 = word1;
                tmp->word2 = word2;
                tmp->suffixCount = 0;
                tmp->suffixes = NULL;
                tmp->next = words[hashVal];
                words[hashVal] = tmp;
        }
        newSuffix->suf = suf;
        newSuffix->next = tmp->suffixes;
        tmp->suffixCount++;
        tmp->suffixes = newSuffix;
}

/******************************************************************************/

entry* getHash(entry* words[], char* word1, char* word2)
{
        entry* tmp = words[hash(word1, word2)];

        while (tmp) {
                if ((tmp->word1 == word1) && (tmp->word2 == word2)) break;
                if (!strcmp(tmp->word1, word1) && !strcmp(tmp->word2, word2)) break;
                tmp = tmp->next;
        }
        return tmp;
}

/******************************************************************************/

void freeHash(entry* words[])
{
        unsigned int i;
        entry* e;
        entry* en;
        suffix* s;
        suffix* sn;

        for (i=0; i<BUCKETS; ++i) {
                for (e=words[i]; e; e=en) {
                        for (s=e->suffixes; s; s=sn) {
                                sn = s->next;
                                free(s);
                        }
                        en = e->next;
                        free(e);
                }
        }
}

/******************************************************************************/

char* readFile(char* fileName)
{
        FILE* in;
        long fileSize;
        char* ret;

        in = fopen(fileName, "rt");
        if (!in) return NULL;
        fseek(in, 0, SEEK_END);
        fileSize = ftell(in);
        fseek(in, 0, SEEK_SET);
        ret = malloc(fileSize+1);
        fread(ret, fileSize, 1, in);
        fclose(in);

        return ret;
}

/******************************************************************************/

int main()
{
        entry* words[BUCKETS] = {0};
        char* file = readFile("test.txt");
        char* delim = " \n\r\t";
        char* i;
        char* w1="";
        char* w2="";
        int num;
        entry* e;
        suffix* suffixes;
        int sufNum;

        srand(time(NULL));

        if (!file) {
                printf("Unable to open test.txt\n");
                return 1;
        }

        for (i = strtok(file, delim); i; i=strtok(NULL, delim)) {
                if (*i == 0x00) continue;
                putHash(words, w1, w2, i);
                w1 = w2;
                w2 = i;
        }
        putHash(words, w1, w2, ".");

        w1 = w2 = "";
        for (num=0; num<1000; ++num) {
                e = getHash(words, w1, w2);
                sufNum = rand() % e->suffixCount;
                suffixes = e->suffixes;
                while (sufNum--) suffixes = suffixes->next;
                i = suffixes->suf;
                if (i[0] == '.' && i[1] == 0x00) break;
                printf("%s ", i);
                w1 = w2;
                w2 = i;
        }

        free(file);
        freeHash(words);
        return 0;
}

/******************************************************************************/



Man beachte das hingeschluderte Fehlen von Kommentaren
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Dieser Post wurde am 10.04.2009 um 00:16 Uhr von Bruder Leif editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
10.04.2009, 00:18 Uhr
Bruder Leif
dances with systems
(Operator)


Die Skriptsprachen sind schnell mal eben runtergehauen. Zuerst AWK:


Code:
BEGIN {
        w1=w2="";
}

{
        for (i=1; i<=NF; i++) {
                triples[w1,w2,cnt[w1,w2]++] = $i;
                w1=w2;
                w2=$i;
        }
}

END {
        triples[w1,w2] = ".";
        w1=w2="";
        for (len=0; len<1000; len++) {
                i=triples[w1,w2,int(rand()*cnt[w1,w2])];
                w1=w2;
                w2=i;
                if (i == ".") break;
                printf("%s ", i);
        }
}



Dann Lua:

Code:
triples = {}
math.randomseed(os.time())

function add(w1, w2, w3)
        if not triples[w1..","..w2] then
                triples[w1..","..w2] = {w3}
        else
                table.insert(triples[w1..","..w2], w3)
        end
end

w1, w2 = "", ""

for i in io.lines("test.txt") do
        string.gsub(i, "([^%s]*)%s*", function(c) add(w1, w2, c); w1, w2 = w2, c end)
end
add(w1, w2, ".")

w1, w2, out = "", "", ""

for len=1, 1000 do
        i = triples[w1..","..w2]
        i = i[math.random(#i)]
        out, w1, w2 = out .. w1 .. " ", w2, i
        if i == "." then
                out = out .. w1
                break
        end
end

print((string.gsub(out, "^%s*", "")))



Perl:

Code:
while(<>) {
        for(split) {
                push @{$triples{$w1}{$w2}}, $_;
                ($w1, $w2) = ($w2, $_);
        }
}
push @{$triples{$w1}{$w2}}, '.';

($w1, $w2) = ('', '');

for $len (1..1000) {
        @words = @{$triples{$w1}{$w2}};
        $i = $words[int(rand($#words+1))];
        ($w1, $w2) = ($w2, $i);
        last if $i eq '.';
        print "$i ";
}
print "\n";


--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
10.04.2009, 00:19 Uhr
Bruder Leif
dances with systems
(Operator)


Python:


Code:
import random

w1 = ""
w2 = ""
triples = {}
for line in open("test.txt").readlines():
        for word in line.split():
                key = w1 + " " + w2
                if not triples.has_key(key):
                        triples[key] = [word]
                else:
                        triples[key].append(word)
                w1 = w2
                w2 = word

key = w1 + " " + w2
if not triples.has_key(key):
        triples[key] = ["."]
else:
        triples[key].append(".")

random.seed()
w1 = ""
w2 = ""
for i in range(1000):
        list = triples[w1 + " " + w2]
        word = list[int(random.random() * len(list))]
        if word == ".":
                break

        print word,
        w1 = w2
        w2 = word

print



Und Tcl:


Code:
expr {srand([clock clicks])}

proc add {w1 w2 w3} {
        set list {}
        if [info exist ::triples($w1,$w2)] { set list $::triples($w1,$w2) }
        lappend list $w3
        set ::triples($w1,$w2) $list
}

set w1 {}
set w2 {}

foreach i [read [open "test.txt"]] {
        add $w1 $w2 $i
        set w1 $w2
        set w2 $i
}
add $w1 $w2 .

set w1 {}
set w2 {}
set out {}
for {set len 0} {$len < 1000} {incr len} {
        set i $triples($w1,$w2)
        set i [lindex $i [expr "int(rand() * [llength $i])"]]
        set out "$out $w1"
        set w1 $w2
        set w2 $i
        if { [string match $i . ] } {
                set out "$out $w1"
                break
        }
}

puts [string trim $out]


--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
10.04.2009, 00:20 Uhr
Bruder Leif
dances with systems
(Operator)


In Java wie beim C++-Versuch Strings aneinandergehaengt:


Code:
import java.util.*;
import java.io.*;

public class t
{
        public static void main(String args[]) throws IOException
        {
                HashMap<String, ArrayList<String>> triples = new HashMap<String, ArrayList<String>>();
                Random rnd = new Random();
                BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                String w1="", w2="", line;
                while ((line = in.readLine()) != null) {
                        for (String i: line.split("\\s+")) {
                                ArrayList<String> list = triples.get(w1 + " " + w2);
                                if(list == null) triples.put(w1 + " " + w2, list = new ArrayList<String>());
                                list.add(i);
                                w1 = w2;
                                w2 = i;
                        }
                }
                ArrayList<String> list = triples.get(w1 + " " + w2);
                if(list == null) triples.put(w1 + " " + w2, list = new ArrayList<String>());
                list.add(".");

                w1 = w2 = "";
                for (int n=0; n<1000; ++n) {
                        ArrayList<String> third = triples.get(w1 + " " + w2);
                        String i = third.get(rnd.nextInt(third.size()));
                        if (i == ".") break;
                        System.out.print(i + " ");
                        w1 = w2;
                        w2 = i;
                }
        }
}



Und in C# aehnlich:


Code:
using System;
using System.Collections.Generic;

public class Test
{
        public static void Main(String[] args)
        {
                Dictionary<string, List<string>> triples = new Dictionary<string, List<string>>();
                Random rnd = new Random();

                string w1="", w2="", line;
                while ((line = Console.ReadLine()) != null) {
                        foreach (string i in line.Split()) {
                                if(!triples.ContainsKey(w1 + " " + w2)) triples[w1 + " " + w2] = new List<string>();
                                triples[w1 + " " + w2].Add(i);
                                w1 = w2;
                                w2 = i;
                        }
                }
                if(!triples.ContainsKey(w1 + " " + w2)) triples[w1 + " " + w2] = new List<string>();
                triples[w1 + " " + w2].Add(".");

                w1 = w2 = "";
                for (int n=0; n<1000; ++n) {
                        List<string> third = triples[w1 + " " + w2];
                        string i = third[rnd.Next(third.Count)];
                        if (i == ".") break;
                        Console.Write(i + " ");
                        w1 = w2;
                        w2 = i;
                }
        }
}


--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: