3. Zeit für Histogrammberechnung

Zeit für Histogrammberechnung

  • ?

    hallo!

    Ich beschäftige mich derzeit mit Zufallswerten und Histogrammen. Zur Auswertung meiner Ideen benutze ich Python.
    Es werden recht hohe Datenmengen berechnet.

    Es interessiert mich, wieviel schneller mein Programm in C als in Python wäre.
    Wenn es einen großen Zeitvorteil gäbe, würde ich mich mal mit C beschäftigen und vielleicht einige meiner Sachen dann in C schreiben.

    Vielleicht könnt ihr kurz ein Programm in C schreiben, das ein Histogramm von 10 Millionen ASCII-Werten erstellt und dann die Laufzeit mit der meines Pythonprogramms vergleichen.

    Entweder benutzt ihr Python zum Ausführen meines Codes oder, wenn ihr kein Python installiert habt, könnt ihr euch die hochgeladene zip-Datei runterladen.
    Darin befindet sich das Programm als exe; zum Ausführen muss man Python nicht installiert haben.

    Der Python-Code sieht so aus:

    # -*- coding: cp1252 -*-
from time import time
from collections import defaultdict
print "Programm gestartet"
daten=[]
datei=open("t.txt")
daten=datei.read()
datei.close()
t1=time()
histogramm = defaultdict(int)
for value in daten:
    histogramm[value] += 1
t2=time()
print "Zur Berechnung des Histogramms wurden"
print t2-t1,"Sekunden benötigt."
print "__________________________"
c=raw_input("Ende mit beliebiger Taste")

    Dazu braucht ihr dann noch die Daten.
    Entweder erstellt ihr euch selber eine Datei mit dem Namen "t.txt", die 10.000.000 ASCII-Werten enthält; jeder ASCII-Wert kann zwischen 50 und 100 liegen
    Oder ihr ladet euch meine t.txt runter:
    http://rapidshare.com/files/456627294/t.txt

    hier der Link zum Archiv mit der Version, die ohne Python läuft:
    http://rapidshare.com/files/456626798/dist.zip
    Das Archiv enthält schon die t.txt, die anderen Dateien wurden von py2exe erstellt.
    Das Programm kann durch ausführen der "test.exe" gestartet werden.

    Ich würde mich freuen, wenn ihr ein paar Vergleichszahlen posten würdet.

    Gruß
    Paul

    0
  • C

    Wenn du wirklich eine C-Lösung suchst, bist du eine Etage höher besser aufgehoben 😉

    Ansonsten sollten für einen Vergleich auch identische Rahmenbedingungen bestehen - wenn ich dir sagen würde, wie schnell mein Rechner das verarbeiten würde, nützt dir das gar nichts. Und komplette Programme schreiben die wenigsten hier umsonst - wenn du Geld bietest, findest du vielleicht im Projekte-Board siher jemanden.

    0
  • ?

    Ansonsten sollten für einen Vergleich auch identische Rahmenbedingungen bestehen - wenn ich dir sagen würde, wie schnell mein Rechner das verarbeiten würde, nützt dir das gar nichts.

    Deswegen habe ich doch meine Python-Lösung angefügt; somit kann jeder sowohl die C-Version als auch die Python-Version laufen lassen und die Zeiten vergleichen.

    Und komplette Programme schreiben die wenigsten hier umsonst - wenn du Geld bietest, findest du vielleicht im Projekte-Board siher jemanden.

    Wie bist du denn drauf? 😮

    Gruß
    Paul

    0
  • C

    peak_me schrieb:

    Wie bist du denn drauf? 😮

    Ich bin Realist 😃 Und ich gehöre zu den Leuten, die anderen eher Tips geben, sich selbst zu helfen 😉

    PS: Ich würde deine Lösung fast 1:1 umsetzen, nur daß ich die einzelnen Werte direkt beim Einlesen einsortieren würde anstatt sie erstmal zwischenzuspeichern. (aber ich habe hier keinen Compiler einsatzbereit, um das umzusetzen)

    0
  • ?

    Ich bin Realist 😃 Und ich gehöre zu den Leuten, die anderen eher Tips geben, sich selbst zu helfen 😉

    Die gleiche Einstellung habe ich auch.
    Meinetwegen will ich den Quelltext des Programms auch garnicht haben; wir würden nur ein paar Vergleichszeiten oder Einschätzungen reichen.
    Ich habe mich gerade bei Python eingearbeitet und weiß nicht, ob der Aufwand sich lohnt, das gleiche für C zu tun.
    Wenn aber eine erhebliche Laufzeitverkürzung möglich wäre, würde ich es auf mich nehmen. 🙂

    0
  • ?

    Ich habe es mal schnell hingerotzt:

    int main()
{
	DWORD start = GetTickCount();
	std::ifstream is("t.txt");
	if(is.good())
	{
	    typedef std::map<BYTE, unsigned int> testmap;
		is.seekg(0,ios::end);
		std::vector<BYTE> data(is.tellg());
		cout << data.size() << " bytes\n";
		is.seekg(0,ios::beg);
		if(is.read(reinterpret_cast<char*>(&data[0]), data.size()))
		{
			testmap mymap;
			for(vector<BYTE>::iterator beg = data.begin(), end = data.end(); beg!=end; ++beg)
			{
				++mymap[*beg];
			}
			DWORD end = GetTickCount();

			cout << (end-start) << "ms\n";
			unsigned int sum = 0;
			for(testmap::iterator beg = mymap.begin(), end = mymap.end(); beg!=end; ++beg)
			{
				cout << setw(6) << (int)beg->first << "\t" << beg->second << "\n";
				sum+=beg->second;
			}
			cout << "gesamt : " << sum << endl;
		}
	}
}

    GetTickCount kann ja durch eine andere Funktion ersetzt werden.
    Ausgabe:

    10000000 bytes
1437ms
    50  98881
    51  98697
    52  98835
    53  98667
    54  98737
    55  98900
    56  98495
    57  99320
    58  99653
    59  98649
    60  99157
    61  98984
    62  98434
    63  99040
    64  98952
    65  99181
    66  99095
    67  99183
    68  99150
    69  99332
    70  99231
    71  99309
    72  99116
    73  98617
    74  98989
    75  99292
    76  99418
    77  98902
    78  99024
    79  99207
    80  99015
    81  98841
    82  99477
    83  98991
    84  98998
    85  99216
    86  99250
    87  98983
    88  98482
    89  99040
    90  99120
    91  99028
    92  98648
    93  99211
    94  99097
    95  98833
    96  99331
    97  99280
    98  99046
    99  98966
   100  99315
   101  99285
   102  98634
   103  99145
   104  98695
   105  98653
   106  98603
   107  98748
   108  99161
   109  98633
   110  98824
   111  99048
   112  98636
   113  99538
   114  98417
   115  98946
   116  99338
   117  99245
   118  98832
   119  99174
   120  99071
   121  98810
   122  99228
   123  98945
   124  99687
   125  99206
   126  98694
   127  98703
   128  99562
   129  99493
   130  99378
   131  99151
   132  99307
   133  99114
   134  98864
   135  99055
   136  98714
   137  98673
   138  98883
   139  98949
   140  98695
   141  98669
   142  98782
   143  98585
   144  99078
   145  98931
   146  98757
   147  99303
   148  98782
   149  99085
   150  99676
gesamt : 10000000

    Mit Windows-Dateihandles und ReadFile ging es nochmal einige ms schneller.
    Deine test.exe brauchte auf meinem alten Notebook ca. 7 Sekunden.

    0
  • ?

    Die Abfrage

    if(is.read(reinterpret_cast<char*>(&data[0]), data.size()))

    hat so natürlich keinen Effekt, es kam daher, dass ich erst mit Windows-Handles garbeitet hatte und in die if-Bedingung der Returnwert von Readfile war.

    0
  • ?

    1437ms

    Deine test.exe brauchte auf meinem alten Notebook ca. 7 Sekunden.

    Diese C++-Lösung wäre dann schonmal 5-Mal schneller.

    danke für die Werte!

    0
  • ?

    Last mal Überlegen.

    1. 10 MByte sollen Byteweise gelesen werden.
    2. Ein Array Eintrag soll je Inhalt des Bytes um eins Incrementiert werden.

    Mein erster Gedanke war:

    Wacht der Prozessor aus den "sleep" auf wenn er die Aufgabe sieht oder macht er das im Halbschlaf nebenbei. 😃

    Ich habe dann mal das Programm von c++..rulez modifiziert und komme hier auf einen Betagten Pentium D (2,8Ghz) auf ca. 0.350 msec. (Compeliert ohne Optimierung 🙄)

    Hier das Programm

    int __main(int argc, char *argv[])
{
    timeval start, end;
    gettimeofday(&start, NULL);

    typedef unsigned char   tInType;

    size_t Histo[std::numeric_limits< tInType >::max()];
    std::fill_n(Histo, std::numeric_limits< tInType >::max(), 0);

    ifstream In("rsapi.cgi");

    if(In.good())
    {
        In.seekg(0,ios::end);
        size_t Size = In.tellg();
        In.seekg(0,ios::beg);

        cout << Size << " bytes\n";

        for(size_t c = 0; c < Size; ++c) ++Histo[ (tInType)In.get()];
    }

    gettimeofday(&end, NULL);
    long seconds  = end.tv_sec  - start.tv_sec;
    long useconds = end.tv_usec - start.tv_usec;
    long mtime = ((seconds) * 1000 + useconds/1000);
    cout << mtime << " ms " << endl;

    size_t sum = 0;
    for(size_t c = 0; c < std::numeric_limits< tInType >::max(); ++c)
    {
        if(Histo[c])
        {
            cout << setw(6) << c << "\t" << Histo[c] << "\n";
            sum += Histo[c];
        }
    }
    cout << "gesamt : " << sum << endl;

    return EXIT_SUCCESS;
}

    PS: Verzeiht meinen Harte Cast 🤡

    Lichtlein

    0
  • ?

    Daten befinden sich im Festplatten Cache vom Betriebssystem. Wenn die Daten noch von der Festplatte geladen werden sollten dauert es ein wenig länger.
    Vielleicht noch mal 0.2 bis 0.3 Sec.

    Lichtlein

    0
  • I

    Nochmal ein kleines Beispiel für C++ vs Python beim Parsen großer Datenmengen: http://boost-spirit.com/home/2010/11/07/multi-threaded-qi-6-hours-37-seconds/ (hier mit Boost.Spirit, das wäre in unserem Beispiel natürlich viel zu overpowered, wenn auch nicht unbedingt langsamer).

    Ergebnis: Von 6h Python auf 4min C++, dann mit Threads nochmal runter auf 37s. Also ein Schub von mehr als 500x.

    0
  • ?

    Ich habe dann mal das Programm von c++..rulez modifiziert und komme hier auf einen Betagten Pentium D (2,8Ghz) auf ca. 0.350 msec. (Compeliert ohne Optimierung 🙄)

    @Lichtlein: Kannst du vielleicht nochmal mein Python-Referenz-Programm durchlaufen lassen, damit ich eine Vergleichszeit habe?

    0
  • ?

    Ist leider nicht möglich da ich nichts mit EXE dingens, anfangen kann.

    Lichtlein

    0
Anmelden zum Antworten