Forum: PC-Programmierung c++ Code langsam


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Hansi (Gast)


Lesenswert?

hi

ich wollte in c++ eine Routine schreiben um in einem (einige Millionen 
Zeilen langem) csv in jeder Zeile  (ab Spalte 3) Duplikate zu löschen. 
Der Code ist folgender
1
#include <fstream>
2
#include <sstream>
3
#include <iostream>
4
#include <vector>
5
using namespace std;
6
int csv_len = 45;
7
string csv_entries[45];
8
9
10
int main()
11
{
12
    ifstream inFile("list.txt");
13
    ofstream outFile("nodup.txt");
14
15
    if (inFile.is_open())
16
    {
17
        string line;
18
        while (getline(inFile, line))
19
        {
20
            stringstream ss(line);
21
            for (int n = 0; n < csv_len; n++) {
22
                getline(ss, csv_entries[n], ';');
23
            }
24
25
            for (int n = 3; n < csv_len-1; n++) {
26
                for (int m = n+1; m < csv_len; m++) {
27
                    if (csv_entries[n] != "" && csv_entries[n] == csv_entries[m]) {
28
                        csv_entries[m] = "";
29
                    }
30
                }
31
            }
32
33
            for (int n = 0; n < csv_len; n++) {
34
                outFile << csv_entries[n] << ";";
35
            }
36
            outFile << "\n";
37
        }
38
    }   
39
    return 0;
40
}


Es funktioniert soweit, ist aber relativ langsam. Es wird gerade mal 10% 
der PC Leistung verwendet. Kann ich den Code irgendwie beschleunigen?

von Philipp K. (philipp_k59)


Lesenswert?

Hansi schrieb:
>ich wollte in c++ eine Routine schreiben um in einem (einige Millionen
>Zeilen langem) csv in jeder Zeile  (ab Spalte 3) Duplikate zu löschen.

ich würde das ganze in SQLite lösen...

dann hätte man mit einem optimierten insert Befehl Duplikatfreie 
Inserts.

von Hansi (Gast)


Lesenswert?

Philipp K. schrieb:
> ich würde das ganze in SQLite lösen...

ja ich weißt, es gibt bereits fertige Lsungen die wesentlich schneller 
wären. Ich möchte es aber in c++ bewerkstelligen, da ich noch andere, 
wesentlich komplexere File Manipulationen vorhabe. Zuerst möchte ich 
aber diesen relative simplen Code optimieren...

von Mladen G. (mgira)


Lesenswert?

Hansi schrieb:
> einige Millionen
> Zeilen langem) csv

Dein Code liest Zeilenweise ein, da wird wohl viel Zeit fuer 
unoptimierten IO verschwendet.

Hansi schrieb:
> Zuerst möchte ich
> aber diesen relative simplen Code optimieren...

Da kann ich Python mit Dataframes und/oder Numpy empfehlen.
CSV liest man schneller mit dataframes ein (inkl. memory mapping oder 
nicht), bei binaeren Dateien ist numpy schneller.

von Dirk B. (dirkb2)


Lesenswert?

Hansi schrieb:
> Es wird gerade mal 10%
> der PC Leistung verwendet.

Was ist denn das für ein PC?
Wenn der 8 Kerne hat, läuft das Programm maximal mit 12,5% 
Systemleistung.
Das ist der theoretische Wert.

Dazu kommt dann das ganze File I/O - und das ist langsam (im Vergleich 
zum Rest)

von Maik Hauguth (Gast)


Lesenswert?

Dein Code verwendet zwei verschachtelte for-Schleifen und benötigt ~n²/2 
Vergleiche, wobei n=csv_len ist. Bei n = 10^6 benötigt dein Verfahren 
5*10^11 Schritte.

Sinnvoller wäre z.B. die Datensätze z.B. mit Quicksort zu sortieren 
(n*lg(n) Vergleiche), danach die Liste durchlaufen und Duplikate 
entfernen (n Schritte) und gegebenenfalls nach ursprünglichen 
Zeilennummern zurück zu sortieren (n*lg(n)). Insgesamt also 2*n*lg(n) + 
n Schritte.

Bei n=10^6 sind das  ~41*10^6 Schritte

von Philipp K. (philipp_k59)


Lesenswert?

Hansi schrieb:
> ja ich weißt, es gibt bereits fertige Lsungen die wesentlich schneller
> wären.

Fakt ist, die Tabellen müssen in den Ram, dann kannst du mit mehreren 
Parallelen Aufgaben X mal schneller arbeiten.

Durch das Read Line by line und output kannst du technisch nicht 
parallel arbeiten. Wieviel Datenmasse ist das?

Vielleicht beim einlesen einen MD5 oder so speichern und dann beim 
nächsten einlesen im Ram als Variable vergleichen.

So wird das nichts. Wenigstens 1000 Zeilen vorladen oder am besten nen 
ganzes Megabyte oder so erhöht es schön um das x fache.

: Bearbeitet durch User
von Heinzel (Gast)


Lesenswert?

CSV Datei in ein tmpfs (RAM) kopieren oder SSD einsetzen.
Wenn CPU Auslastung <100%, dann ist die Festplatte der bottleneck (CPU 
könnte schneller, muss aber auf die Daten warten)...

Abgesehen davon ist der Algorithmus natürlich auch langsamer als nötig.

von Pandur S. (jetztnicht)


Lesenswert?

Erst mal eine Baumstruktur drueber legen. Einen blalancierten 
Binaerbaum, dann geht alles viel schneller.

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Maik Hauguth schrieb:
> Sinnvoller wäre z.B. die Datensätze z.B. mit Quicksort zu sortieren
> (nlg(n) Vergleiche), danach die Liste durchlaufen und Duplikate
> entfernen (n Schritte) und gegebenenfalls nach ursprünglichen
> Zeilennummern zurück zu sortieren (nlg(n)).

Genau das Sortieren nach dem Einlesen ist der richtige Ansatz. Dann 
liegen identische Datensätze nämlich hintereinander.

In der UNIX-Shell gibt man einfach ein:
1
sort <infile | uniq >outfile
oder noch kürzer, weils beide Schritte kombiniert:
1
sort -u <infile >outfile

P.S.
Die beiden Unix-Dienstprogramme sort und uniq sind trivial. Das kann man 
auch in C/C++ einfachst nachbauen.

: Bearbeitet durch Moderator
von Philipp K. (philipp_k59)


Lesenswert?

Es gibt da viele möglichkeiten.. z.B. 2 oder mehr  Threads.. der lesende 
eilt dem schreibenden 100MB vorweg, so hab ich etwas ähnliches in Java 
um das 200 fache optimiert.

Dazu noch einen Hash bei MD5 z.B 8 Byte bei 1.000.000 Zeilen 8Megabyte 
Ram, bei gleichem Hash erst nochmal Inhalt vergleichen um Fehler 
auszuschließen.

Also Threads und nur eine MD5 Tabelle mit nem  128Bit Integer anlegen.

Das würde ich so ausprobieren... Ob MD5 dann etwas langsamer macht 
keinen Plan, da kommt es auf die Länge des Inhalts der Zeilen an.

von Mikro 7. (mikro77)


Lesenswert?

Die Datei wird zeilenweise gelesen. Da puffern OS und std::stream in der 
Regel ausreichend.

Dann geht es um ein Array mit 45 Einträgen (aus der Zeile, halt CSV). 
Das sollte alles im CPU Cache sein. Imho bringt da auch ein Sort nicht 
viel.

Soweit keine weiteren Infos vom TS kommen, denke ich, dass der Prozess 
einfach nur idlet weil er auf Daten von der Platte wartet.

von Klaus W. (mfgkw)


Lesenswert?

Hansi schrieb:
> Es funktioniert soweit, ist aber relativ langsam. Es wird gerade mal 10%
> der PC Leistung verwendet. Kann ich den Code irgendwie beschleunigen?



Ist es relevant, die ursprüngliche Sortierung zu behalten (soweit nicht 
gelöscht wird)?

Falls nein: man kann alle Zeilen einlesen und mit einem passenden 
Vergleichskriterium in einem std::set speichern (elimiert automatisch 
alle Duplikate), danach das set wieder ausgeben.

Falls ja: Stattdessen einen std::vector nehmen, darin alle aufzuhebenden 
Zeilen speichern.
Um Duplikate zu erkennen, parallel dazu von jeder Zeile einen Hash-Wert 
berechnen und alle Hashwerte in einem std::set speichern. Vor dem 
Einfügen einer Zeile den zugehörigen Hashwert im set suchen und ggf. die 
Zeile ignorieren.

PS: im zweiten Fall kann man den vector natürlich auch weglassen und 
gleich ausgeben...

: Bearbeitet durch User
von Hansi (Gast)


Angehängte Dateien:

Lesenswert?

laut CPU Auslastungs Grafik scheint es, als ob 4 Kerne an der Aufgabe 
schuften, kann das sein? Die Runtime verwendet insg. etwa 11-12% von den 
angezeigten 15%.


Der PC hat eine SSD, also kein Flaschenhals dort.

von mh (Gast)


Lesenswert?

Hansi schrieb:
> Der PC hat eine SSD, also kein Flaschenhals dort.

Das hängt dann doch noch etwas von der SSD ab. Hast du mal den 
Datendurchsatz (Größe Input + Größe Output) / Zeit abgeschätzt? Den Wert 
vergleichst du dann mit den theoretischen Maximalwerten von SSD und RAM. 
Danach kannst du dann entscheiden, ob dein Programm langsam ist.

von Irgend W. (Firma: egal) (irgendwer)


Lesenswert?

Hansi schrieb:
> laut CPU Auslastungs Grafik scheint es, als ob 4 Kerne an der Aufgabe
> schuften, kann das sein? Die Runtime verwendet insg. etwa 11-12% von den
> angezeigten 15%.
>
> Der PC hat eine SSD, also kein Flaschenhals dort.

Da wird nur aus Termischen gründen zwichen vier Kernen gewechselt. Von 
der auslastung her ist es aber nur ein Kern der mit maximalleistun 
läuft. Das passt ja auch zu deinem Programmcode. Du hast ja dort nichts 
drin um die Arbeit auf mehrere Threads zu verteilen.

Such z.B. mal nach "multithreaded sorting c++"

https://www.heise.de/select/ix/2017/5/1492877730281965

https://www.boost.org/doc/libs/1_67_0/libs/sort/doc/html/sort/parallel.html

"openmp" ist auch so ein Stichwort dazu:

https://en.wikipedia.org/wiki/OpenMP


IO dauert immer seine Zeit, gerade wenn man gemütlich eine Zeile nach 
der anderen liest. Da ist auch eine SSD keine Rakete.
Probiere einfach mal wie lange es alleine dauert die Datei einzulesen 
ohne was mit den ganze for zu verarbeiten.

von Vincent H. (vinci)


Lesenswert?

Die moderne Variante C++ zu parallelisieren ist Intels TBB 
(https://github.com/oneapi-src/oneTBB) bzw die parallel Algorithms der 
STD (hoffentlich irgendwann mal).

Aber wie bereits hundert mal erwähnt hier sicher nicht das "Bottleneck".

von Dirk B. (dirkb2)


Lesenswert?

Hansi schrieb:
> laut CPU Auslastungs Grafik scheint es,

Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU 
Auslastung?

von Εrnst B. (ernst)


Lesenswert?

Dirk B. schrieb:
> Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU
> Auslastung?

ist doch völlig egal. Das Programm ist, wie oben schön vorgerechnet 
wurde, aufgrund des ungeeigneten O(n²)-Algorithmus um einen 
Faktor >10000 langsamer als es sein müsste.
-> Sinnvolle Datenstrukturen verwenden (STL-Container können helfen), 
und schon verpasst du das Teil im Taskmanager komplett, wenn du im 
falschen Moment blinzelst.

: Bearbeitet durch User
von foobar (Gast)


Lesenswert?

Was einige wohl übersehen: es werden nicht doppelte Zeilen entfernt 
sondern nur doppelte Felder innerhalb einer Zeile.  Es existieren genau 
45 Felder in jeder Zeile, die Erkennung läuft daher (trotz des 
suboptimalen Algorithmus) mit konstanter Zeit ab - die Laufzeit des 
Programms ist also O(AnzahlZeilen).

Wenn man das parallelisieren will, geht das relativ einfach, indem man 
die Datei vorher in N Teile splittet, dann N-mal das Programm parallel 
auf die Einzeldateien loslässt, und anschließen die Ergebnisse wieder 
zusammenführt.

von Εrnst B. (ernst)


Lesenswert?

foobar schrieb:
> Was einige wohl übersehen: es werden nicht doppelte Zeilen entfernt
> sondern nur doppelte Felder innerhalb einer Zeile.

Ups. Stimmt, mein Fehler, so macht mein Post weiter oben natürlich 
keinen Sinn.

Hab mich da auf Maik verlassen...

von foobar (Gast)


Lesenswert?

> Kann ich den Code irgendwie beschleunigen?

Versuch die String-Klasse zu vermeiden, insb auch den stringstream für 
jede Zeile.  In einfachem C bekommst du das ohne Speicherallozierung hin 
und dürfte dann um einiges schneller sein.

von foobar (Gast)


Lesenswert?

> In einfachem C

Untested:
1
#include <stdio.h>
2
#include <string.h>
3
4
int main(int argc, char **argv)
5
{
6
    char buf[32768];
7
    char *field[64], *p;
8
    int c, i;
9
10
    field[i = 0] = p = buf;
11
    while ((c = getchar()) != EOF)
12
        if (c == ';')
13
        {
14
            *p++ = 0;
15
            if (i < sizeof(field)/sizeof(*field) - 1)
16
                field[++i] = p;
17
        }
18
        else if (c != '\n')
19
        {
20
            if (p < buf + sizeof(buf) - 2)
21
                *p++ = c;
22
        }
23
        else
24
        {
25
            *p = 0;
26
            for (int n = 3; n < i-1; n++)
27
                if (field[n][0])
28
                    for (int m = n+1; m < i; m++)
29
                        if (strcmp(field[n], field[m]) == 0)
30
                            field[m][0] = 0;
31
32
            for (int n = 0; n < i; n++)
33
                fputs(field[n], stdout), fputc(';', stdout);
34
            fputc('\n', stdout);
35
36
            field[i = 0] = p = buf;
37
        }
38
}

von mh (Gast)


Lesenswert?

foobar schrieb:
> In einfachem C bekommst du das ohne Speicherallozierung hin
> und dürfte dann um einiges schneller sein.
Und warum sollte es um "einiges" schneller sein? Und wieviel ist 
"einiges"?

foobar schrieb:
> Untested:
Und bist du sicher, dass man das nicht noch etwas unleserlicher und 
unflexibler schreiben kann?

von Dirk B. (dirkb2)


Lesenswert?

Εrnst B. schrieb:
> Dirk B. schrieb:
>> Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU
>> Auslastung?
>
> ist doch völlig egal. Das Programm ist, wie oben schön vorgerechnet
> wurde, aufgrund des ungeeigneten O(n²)-Algorithmus um einen
> Faktor >10000 langsamer als es sein müsste.
> -> Sinnvolle Datenstrukturen verwenden (STL-Container können helfen),
> und schon verpasst du das Teil im Taskmanager komplett, wenn du im
> falschen Moment blinzelst.

Es ging darum, dass das Programm den Prozessor nicht zu 100% auslastet - 
da wäre ungünstiger Code (sofern kein IO benutzt wird) ja vorteilhaft.

Das Programm kann - da ohne Threads - auf einem 8 Kern Rechner ja nur 
maximal 12,5% CPU Auslastung machen.
Wenn es 10% macht ist es ja auch ok.

von Rolf M. (rmagnus)


Lesenswert?

Frank M. schrieb:
> Genau das Sortieren nach dem Einlesen ist der richtige Ansatz. Dann
> liegen identische Datensätze nämlich hintereinander.
>
> In der UNIX-Shell gibt man einfach ein:
> sort <infile | uniq >outfile
> oder noch kürzer, weils beide Schritte kombiniert:sort -u <infile
>>outfile

Das entfernt aber Zeilen, die komplett gleich sind. Er will aber nicht 
duplizierte Zeilen löschen, sondern innerhalb jeder Zeile duplizierte 
Spalten, und das auch nur ab Spalte 3.
Zumindest ist das die Aussage aus dem Initialposting und passt auch zu 
dem Code.

: Bearbeitet durch User
von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Rolf M. schrieb:
> Er will aber nicht duplizierte Zeilen löschen, sondern innerhalb jeder
> Zeile duplizierte Spalten, und das auch nur ab Spalte 3.

Ja, sorry, das hatte ich missverstanden.

Was mir hier auffällt:
1
            for (int n = 3; n < csv_len-1; n++) {
2
                for (int m = n+1; m < csv_len; m++) {
3
                    if (csv_entries[n] != "" && csv_entries[n] == csv_entries[m]) {
4
                        csv_entries[m] = "";
5
                    }
6
                }
7
            }

Er startet die zweite for-Schleife unabhängig davon, ob csv_entries[n] 
leer ist oder nicht, um dies dann zigmal in der zweiten Schleife zu 
prüfen. Zieht man die erste Bedingung
1
csv_entries[n] != ""

vor die zweite Schleife, wird diese erst gar nicht (unnötigerweise) 
durchlaufen. Denn die Variable n ändert sich im zweiten 
Schleifendurchlauf gar nicht.

Also:
1
            for (int n = 3; n < csv_len-1; n++) {
2
                if (csv_entries[n] != "")
3
                {
4
                    for (int m = n+1; m < csv_len; m++) {
5
                        if (csv_entries[n] == csv_entries[m]) {
6
                            csv_entries[m] = "";
7
                        }
8
                    }
9
                }
10
            }

Dieses sollte einen spürbaren Geschwindigkeitsvorteil bringen.

Was mich irritiert: Da ist kein "break" in der zweiten Schleife, wenn 
die beiden zu vergleichenden Spalten ungleich sind. Will der TO 
tatsächlich auch Dubletten rauswerfen, die erst viel später wieder 
erscheinen, also:
1
irgendwas ... eins zwei drei eins
soll tatsächlich transferiert werden in
1
irgendwas ... eins zwei drei
? Oder will er nur hintereinanderliegende Dubletten rauswerfen?

Letzteres ist entscheidend für die Optimierung. Ein korrekt platziertes 
"break" würde nämlich die Verarbeitungsdauer nochmals verringern:
1
            for (int n = 3; n < csv_len-1; n++) {
2
                if (csv_entries[n] != "")
3
                {
4
                    for (int m = n+1; m < csv_len; m++) {
5
                        if (csv_entries[n] == csv_entries[m]) {
6
                            csv_entries[m] = "";
7
                        }
8
                        else
9
                        {
10
                            break;
11
                        }
12
                    }
13
                }
14
            }

Das ist aber noch nicht alles: Wenn tatsächlich nur gleiche Spalten 
hintereinander geleert werden sollen, kann man unmittelbar vor dem 
break noch einfügen:
1
                            n = m;

Das überspringt die bereits geleerten Spalten.

: Bearbeitet durch Moderator
von Sven B. (scummos)


Lesenswert?

Wie immer gilt: nicht herumraten, erstmal einen Profiler verwenden.

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Sven B. schrieb:
> Wie immer gilt: nicht herumraten, erstmal einen Profiler
> verwenden.

Profiler messen Dauer/Anzahl von Funktionsaufrufen. Der nützt Dir gar 
nichts innerhalb der while-Schleife.

Außer es wird jeder Stringvergleich in C++ in eine externe Funktion 
ähnlich zu strcmp() münden. Das bezweifele ich aber hier.

: Bearbeitet durch Moderator
von mh (Gast)


Lesenswert?

Frank M. schrieb:
> Dieses sollte einen spürbaren Geschwindigkeitsvorteil bringen.

Wenn das die Stelle ist, die die Geschwindigkeit begrenzt.

Frank M. schrieb:
> Letzteres ist entscheidend für die Optimierung.
Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm 
"zu langsam" ist. Dazu muss gemessen werden. Danach sucht man die 
Ursache. Dann sucht man nach Lösungen. Man fängt nicht mit dem letzten 
Schritt an.

von Sven B. (scummos)


Lesenswert?

Frank M. schrieb:
> Sven B. schrieb:
>> Wie immer gilt: nicht herumraten, erstmal einen Profiler
>> verwenden.
>
> Profiler messen Dauer/Anzahl von Funktionsaufrufen. Der nützt Dir gar
> nichts innerhalb der while-Schleife.

Also z.B. perf annotiert einzelne Assembly-Instructions mit einem 
geschätzten Gewicht. Mag sein, dass das nicht jeder Profiler kann, aber 
möglich ist es definitiv.

von mh (Gast)


Lesenswert?

Frank M. schrieb:
> Profiler messen Dauer/Anzahl von Funktionsaufrufen.

Dann solltest du dich mal etwas besser informieren, weil das so nicht 
stimmt.

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

mh schrieb:
> Entscheident ist erstmal festzustellen, ob das Programm "zu langsam"
> ist. Dazu muss gemessen werden. Danach sucht man die Ursache

Sehe ich anders.

Erstmal definiert man eine konkrete Aufgabenstellung, dann entwirft man 
einen Algorithmus dafür.

Leider hat der TO verschwiegen, ob er nur hintereinanderliegende 
Dubletten rauswerfen will oder alle. Und das ist entscheidend für den 
Algorithmus.

Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man 
mit einem pro Spalte auskommt, kann nicht optimal sein.

von Sven B. (scummos)


Lesenswert?

Frank M. schrieb:
> Außer es wird jeder Stringvergleich in C++ in eine externe Funktion
> ähnlich zu strcmp() münden. Das bezweifele ich aber hier.

Das wird zusätzlich auch noch passieren, das ist 
std::string::operator==. ;)

> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
> mit einem pro Spalte auskommt, kann nicht optimal sein.

Sicher, aber kein Algorithmus ist ideal. Man kann immer etwas besser 
machen, praktisch gesprochen. Es ist schon wichtig, zu wissen, was 
eigentlich das Problem ist.

: Bearbeitet durch User
von udok (Gast)


Lesenswert?

Ich habe das mal schnell compiliert, und dazu ein cvs File mit 100e3 
Zeilen
hergenommen:

Hans CPP (liest list.txt und generiert nodup.txt):
time ./test_hans.exe
real    0m6.766s
user    0m0.015s
sys     0m0.000s

foobar C:

time ./test_foobar.exe < list.txt > nodup2.txt
real    0m2.008s
user    0m0.000s
sys     0m0.015s

diff nodup.txt und nodup2.txt: Files sind identisch

von mh (Gast)


Lesenswert?

Frank M. schrieb:
> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
> mit einem pro Spalte auskommt, kann nicht optimal sein.

Es muss nicht optimal sein. Es muss den Anforderungen entsprechen. Und 
deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn 
das Programm nur auf die SSD wartet.

von udok (Gast)


Lesenswert?

Noch ein kurzes Update:

Ich habe den Spass mit Visual Studio compiliert.
Bei so einem modernen C sind alle Funktionen aus der libc
auf multithreaded ausgelegt, mit entsprechendem Overhead.

Gerade beim lesen einzelner Zeichen mit getchar() bricht die
Performance ziemlich ein.

Mit dem Macro
#define _CRT_DISABLE_PERFCRIT_LOCKS 1
lassen sich diese unnötigen Locks ausschalten.

Damit läuft die C Variante in 0.8 Sekunden durch.
Noch mal ein Faktor 2.5 :-)

Die C++ Variante braucht 4.5 Sekunden.

von Sven B. (scummos)


Lesenswert?

Erstmal muss rausgefunden werden, ob das Problem hier ist, dass 
unendlich viele memory allocations gemacht werden, oder ob es I/O bound 
ist.

von TotoMitHarry (Gast)


Lesenswert?

Rein Dateitechnisch sind 10 Millionen Lines einlesen was anderes als 
100MB in den Ram holen :D

von der Weiterverarbeitung mal abgesehen.

von mh (Gast)


Lesenswert?

TotoMitHarry schrieb:
> Rein Dateitechnisch sind 10 Millionen Lines einlesen was anderes als
> 100MB in den Ram holen :D
Weil die Zeilen nicht 10 Byte lang sind?

von Rolf M. (rmagnus)


Lesenswert?

mh schrieb:
> Frank M. schrieb:
>> Letzteres ist entscheidend für die Optimierung.
> Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm
> "zu langsam" ist.

Das ist ja die Ausgangsbasis für die ganze Diskussion. Das steht bereits 
in der Überschrift.

> Dazu muss gemessen werden.

Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das 
messen?

> Danach sucht man die Ursache.

Aber genau das macht Frank doch.

mh schrieb:
> Frank M. schrieb:
>> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
>> mit einem pro Spalte auskommt, kann nicht optimal sein.
>
> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.

Die Anforderung hier ist: "Soll schneller werden, wenn möglich".

> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
> das Programm nur auf die SSD wartet.

Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.

von mh (Gast)


Lesenswert?

Rolf M. schrieb:
> mh schrieb:
>> Frank M. schrieb:
>>> Letzteres ist entscheidend für die Optimierung.
>> Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm
>> "zu langsam" ist.
>
> Das ist ja die Ausgangsbasis für die ganze Diskussion. Das steht bereits
> in der Überschrift.
>
>> Dazu muss gemessen werden.
>
> Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das
> messen?
Wenn du dir die Beiträge des TO nochmal anguckst, beruht seine 
Einschätzung "zu langsam" auf einer niedrigen CPU Auslastung. Weitere 
Infos, was dieses "zu langsam" bedeutet, fehlen.

Rolf M. schrieb:
>> Danach sucht man die Ursache.
> Aber genau das macht Frank doch.
Also hat er das Problem schon gefunden? Wie?

> mh schrieb:
>> Frank M. schrieb:
>>> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
>>> mit einem pro Spalte auskommt, kann nicht optimal sein.
>>
>> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.
> Die Anforderung hier ist: "Soll schneller werden, wenn möglich".
Dafür muss man erstmal wiessen, warum es aktuell nicht schnell genug 
ist.

Rolf M. schrieb:
>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>> das Programm nur auf die SSD wartet.
>
> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.
Deswegen bin ich dafür erst zu messen bevor ich Annahmen mache.

Die Info die es bis jetzt gibt ist effektiv "Ich glaube mein Programm 
ist zu langsam, weil sich die CPU langweilt."
Gibt es hier wirklich jemanden der ernsthaft der Meinung ist, dass der 
beste nächste Schritt die Reduktion der CPU Last ist?

von Sven B. (scummos)


Lesenswert?

Rolf M. schrieb:
>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>> das Programm nur auf die SSD wartet.
>
> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.

Genau, deshalb muss man mit einem Profiler messen, und nicht annehmen, 
dass das Problem vielleicht eine bestimmte Operation ist. ;)

von Philipp K. (philipp_k59)


Lesenswert?

Sven B. schrieb:
> Genau, deshalb muss man mit einem Profiler messen

Ja eben nicht, es gab hier ja genug Verbesserungen die jedem der das 
schon umgesetzt hat aufgefallen sind.

mmap -> muss man zwar selber auf Zeilenende testen aber liest dann ohne 
Overhead direkt.

Sort -> ich glaube bis so eine Datei sortiert ist, ist dann Weihnachten.

nicht Zeilenweise -> in größeren Häppchen einlesen (Overhead beim lesen 
begrenzen)

Multithreaded -> gekonnt an der richtigen Stelle ist das ganz anders als 
automatisches Multithreading.

Richtiger Ansatz -> Skippen anstatt Leer rechnen lassen.

etc.. etc. etc.. Wer messen will braucht einen Vergleich.

von Rolf M. (rmagnus)


Lesenswert?

mh schrieb:
>> Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das
>> messen?
> Wenn du dir die Beiträge des TO nochmal anguckst, beruht seine
> Einschätzung "zu langsam" auf einer niedrigen CPU Auslastung. Weitere
> Infos, was dieses "zu langsam" bedeutet, fehlen.

Was soll es schon bedeuten? Er will, dass es weniger Zeit braucht. Nicht 
hinter allem, was ein Bastler macht, steckt ein hartes Requirement.

> Rolf M. schrieb:
>>> Danach sucht man die Ursache.
>> Aber genau das macht Frank doch.
> Also hat er das Problem schon gefunden?

Wenn man etwas sucht, bedeutet das nicht, dass man es automatisch auch 
gefunden hat, auch wenn in Software der Button "Suchen" heute gerne 
durch "Finden" ersetzt wird, weil das so schön positiv klingt. Er hat 
Tipps gegeben, was man ändern könnte, und dann kann man das einfach mal 
ausprobieren. Ist es schneller - Ziel erreicht. Ist es nicht schneller - 
wieder was gelernt.

>>> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.
>> Die Anforderung hier ist: "Soll schneller werden, wenn möglich".
> Dafür muss man erstmal wiessen, warum es aktuell nicht schnell genug
> ist.

Ja, und das kann man entweder durch eine hochkomplexe Analyse im 
tiefsten Detail erreichen, bevor man überhaupt erwägt, etwas zu ändern, 
oder bei einem so trivialen Programm auch einfach durch ausprobieren.

> Rolf M. schrieb:
>>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>>> das Programm nur auf die SSD wartet.
>>
>> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.
> Deswegen bin ich dafür erst zu messen bevor ich Annahmen mache.
>
> Die Info die es bis jetzt gibt ist effektiv "Ich glaube mein Programm
> ist zu langsam, weil sich die CPU langweilt."

Die CPU langweilt sich offenbar nur deshalb, weil sie aus vielen Kernen 
besteht, von denen nur einer genutzt werden kann und die anderen 
Däumchen drehen.

> Gibt es hier wirklich jemanden der ernsthaft der Meinung ist, dass der
> beste nächste Schritt die Reduktion der CPU Last ist?

Sieht so aus. Und die geposteten Werte scheinen dieser Meinung recht zu 
geben.

von udok (Gast)


Lesenswert?

Philipp K. schrieb:
> mmap -> muss man zwar selber auf Zeilenende testen aber liest dann ohne
> Overhead direkt.

mmap war in meinen Versuchen immer etwas langsamer als read/write.
Dazu ist die Fehlerbehandlung schwierig, und die Performance hängt stark
vom RAM ab.  Ist nur empfehlenswert, wenn man viel im File herumhüpft.

von Sven B. (scummos)


Lesenswert?

Philipp K. schrieb:
> Sven B. schrieb:
>> Genau, deshalb muss man mit einem Profiler messen
>
> Ja eben nicht, es gab hier ja genug Verbesserungen die jedem der das
> schon umgesetzt hat aufgefallen sind.

Keine Ahnung, ich sehe das anders. Wenn du alle Vorschläge umsetzt, ist 
es vermutlich schnell, ja. Aber 50-70% davon werden vermutlich kein 
Prozent Performance bringen, weil sie einfach etwas optimieren, was 
überhaupt nicht das Bottleneck ist.

Warum Zeit mit Optimieren verschwenden an Stellen, wo es nichts bringt?

von Mladen G. (mgira)


Lesenswert?

Sven B. schrieb:
> Warum Zeit mit Optimieren verschwenden an Stellen, wo es nichts bringt?

Weil man noch nix von Knuth und "Premature optimisation is the root of 
all evil" gehoert hat? ;)

Menschen sind erstaunlich schlecht darin vorherzusagen was an einem 
Program am langsamsten ist, genau dafuer nimmt man Profiler, die 80/20 
Regel ist eben meist die 95/5 Regel.

Ansonsten denke ich immer noch dass man einfacheren und schnelleren Code 
fuer diese Aufgabe mit Python/pandas/numpy hinbekommt (Vectorization!), 
ist quasi dafuer gemacht.

C++ mit so einem naiven Ansatz ist weder schneller, noch einfacher 
umzusetzen.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Ansonsten denke ich immer noch dass man einfacheren und schnelleren Code
> fuer diese Aufgabe mit Python/pandas/numpy hinbekommt (Vectorization!),
> ist quasi dafuer gemacht.

Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und 
numpy beherschen.

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und
> numpy beherschen.

Wie gesagt, ich wuerde darauf Wetten, ist ein triviales Problem dafuer, 
und man kann noch viel komplexere Dinge sehr einfach damit umsetzten.

"drop_duplicates" ist sogar schon implementiert, da kann man auch die 
Spalten angeben welche ein Duplikat ausmachen:
https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.drop_duplicates.html

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und
>> numpy beherschen.
>
> Wie gesagt, ich wuerde darauf Wetten, ist ein triviales Problem dafuer,
> und man kann noch viel komplexere Dinge sehr einfach damit umsetzten.
>
> "drop_duplicates" ist sogar schon implementiert, da kann man auch die
> Spalten angeben welche ein Duplikat ausmachen:
> 
https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.drop_duplicates.html

Zu dumm, dass die Funktion nicht das gleiche macht, wie das hier 
gezeigte Programm.

von udok (Gast)


Lesenswert?

Mladen G. schrieb:
> Weil man noch nix von Knuth und "Premature optimisation is the root of
> all evil" gehoert hat? ;)
>
Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.

Was machst du denn, wenn das Program zu langsam ist?
Blöde Sprüche klopfen, wie 9 von 10 es hier machen, löst das Problem 
nicht.

> Menschen sind erstaunlich schlecht darin vorherzusagen was an einem
> Program am langsamsten ist, genau dafuer nimmt man Profiler, die 80/20
> Regel ist eben meist die 95/5 Regel.

Ich würde sagen, Menschen, die sich keine Gedanken machen
sind erstaunlich schlecht darin irgendwas sinnvolles vorherzusagen...

Mich hat es gerade mal 10 Minuten gekostet, das Program um
einen Faktor 5 schneller zu machen.
Es würde mich noch mal 20 Minuten kosten, einen weiteren
Faktor 4 herauszuholen.
Und das ohne irgendwas an dem simplen Algorithmus zu ändern.

Kauf dir doch mal einen PC, der statt 4 GHz, 80 GHz schnell ist...

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Zu dumm, dass die Funktion nicht das gleiche macht, wie das hier
> gezeigte Programm.

Naja, da koennte man sich fragen ob das hier gezeigte Programm zur 
Problemstellung passt, "Duplikate loeschen", das Programm interessiert 
sich ja nur fuer aufeinanderfolgende Duplikate.

Dass C++ "mit Schleifen" nicht schneller sein kann bei grossen 
Datenmengen als "vektorisierte" Verarbeitung in Python/pandas ist IMO 
schon gegeben.

von udok (Gast)


Lesenswert?

Mladen G. schrieb:
> Dass C++ "mit Schleifen" nicht schneller sein kann bei grossen
> Datenmengen als "vektorisierte" Verarbeitung in Python/pandas ist IMO
> schon gegeben.

Hängt von den Daten ab. Wenn die Einträge grad mal 1-30 Zeichen lang 
sind,
würde ich nicht drauf wetten.  Da ist der Overhead der Parallelisierung
viel zu hoch.

von mh (Gast)


Lesenswert?

udok schrieb:
> Mladen G. schrieb:
>> Weil man noch nix von Knuth und "Premature optimisation is the root of
>> all evil" gehoert hat? ;)
>>
> Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.
>
> Was machst du denn, wenn das Program zu langsam ist?
Herausfinden warum es langsam ist.

udok schrieb:
> Mich hat es gerade mal 10 Minuten gekostet, das Program um
> einen Faktor 5 schneller zu machen.
> Es würde mich noch mal 20 Minuten kosten, einen weiteren
> Faktor 4 herauszuholen.
> Und das ohne irgendwas an dem simplen Algorithmus zu ändern.
Schön, dass du die korrekten Daten und den korrekten Rechner hast, um 
das "relativ langsam" des TO zu reproduzieren.

von udok (Gast)


Lesenswert?

mh schrieb:
> Schön, dass du die korrekten Daten und den korrekten Rechner hast, um
> das "relativ langsam" des TO zu reproduzieren.

Das war jetzt der leichtest Teil, ich gebe zu ich habe
einen nicht wissenschaftlichen Ansatz gewählt :-)

von udok (Gast)


Lesenswert?

Mladen G. schrieb:
> Naja, da koennte man sich fragen ob das hier gezeigte Programm zur
> Problemstellung passt, "Duplikate loeschen", das Programm interessiert
> sich ja nur fuer aufeinanderfolgende Duplikate.

Man kann sich viel fragen, so z.B. warum der TE (der mal wieder den
Kopf in den Sand steckt), überhaupt so grossse cvs Files braucht,
und was da drinnen steht.

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.
>
> Was machst du denn, wenn das Program zu langsam ist?
> Blöde Sprüche klopfen, wie 9 von 10 es hier machen, löst das Problem
> nicht.

Soweit bist du der einzige mit bloeden Spruechen hier.

Was ich mache hab ich doch schon gesagt: Profiler nutzten

udok schrieb:
> Mich hat es gerade mal 10 Minuten gekostet, das Program um
> einen Faktor 5 schneller zu machen.
> Es würde mich noch mal 20 Minuten kosten, einen weiteren
> Faktor 4 herauszuholen.
> Und das ohne irgendwas an dem simplen Algorithmus zu ändern.
>
> Kauf dir doch mal einen PC, der statt 4 GHz, 80 GHz schnell ist...

Das Problem in diesem Thread sollte sich in weniger als 15 Minuten 
komplett loesen lassen (weniger wenn man Erfahrung hat), ist ja wirklich 
trivial, und zwar so, dass da auch sehr schell laeuft.

von udok (Gast)


Lesenswert?

Mladen G. schrieb:

> Soweit bist du der einzige mit bloeden Spruechen hier.
Ah ha.

> Was ich mache hab ich doch schon gesagt: Profiler nutzten

Und was soll dir das bringen?


> Das Problem in diesem Thread sollte sich in weniger als 15 Minuten
> komplett loesen lassen (weniger wenn man Erfahrung hat), ist ja wirklich
> trivial, und zwar so, dass da auch sehr schell laeuft.

Wieder mal ein blöder Spruch ohne Nutzen.

von mh (Gast)


Lesenswert?

udok schrieb:
> mh schrieb:
>> Schön, dass du die korrekten Daten und den korrekten Rechner hast, um
>> das "relativ langsam" des TO zu reproduzieren.
>
> Das war jetzt der leichtest Teil, ich gebe zu ich habe
> einen nicht wissenschaftlichen Ansatz gewählt :-)

Ich hätte nicht so positive Worte gewählt, um dein Vorgehen zu 
beschreiben. Deine Zahlen sind vermutlich richtig auf deinem Rechner, 
haben aber vermutlich nichts mit dem Problem des TO zu tun.

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Hängt von den Daten ab. Wenn die Einträge grad mal 1-30 Zeichen lang
> sind,
> würde ich nicht drauf wetten.  Da ist der Overhead der Parallelisierung
> viel zu hoch.

Ich verarbeite hier "zum Spass" Daten (time series) gerne CSV bzw. 
Binaerdaten von mehreren GB, da kommt man mit selbstgemachtem "Zeug" 
nicht hin.

Vektorisierung ist nicht wirklich Parallelisierung im Sinne von mehreren 
Threads.
Anstatt die Daten iterativ zu verarbeiten, macht man das "alles auf 
einmal", sehr vereinfacht ausgedrueckt.

von udok (Gast)


Lesenswert?

Mladen G. schrieb:
> Anstatt die Daten iterativ zu verarbeiten, macht man das "alles auf
> einmal", sehr vereinfacht ausgedrueckt.

Davon träumen wir alle, wenn der Tag lang ist...

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Davon träumen wir alle, wenn der Tag lang ist...

SIMD in den Desktopprozessoren traeumt auch davon oefter benutzt zu 
werden..

: Bearbeitet durch User
von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> udok schrieb:
>> Davon träumen wir alle, wenn der Tag lang ist...
>
> SIMD in den Desktopprozessoren traeumt auch davon oefter benutzt zu
> werden..

Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu 
nutzen?

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
> nutzen?

Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife 
einfach so vektorisiert.

von Heinzel (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>> nutzen?
>
> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
> einfach so vektorisiert.

"autovectorization"

Folie 17ff: 
http://hpac.cs.umu.se/teaching/sem-accg-16/slides/08.Schmitz-GGC_Autovec.pdf

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>> nutzen?
>
> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
> einfach so vektorisiert.

https://godbolt.org/z/GMjdx5nWd

von Mladen G. (mgira)


Lesenswert?

Heinzel schrieb:
> Mladen G. schrieb:
>> mh schrieb:
>>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>>> nutzen?
>>
>> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
>> einfach so vektorisiert.
>
> "autovectorization"
>
> Folie 17ff:
> http://hpac.cs.umu.se/teaching/sem-accg-16/slides/08.Schmitz-GGC_Autovec.pdf

Ja danke fuer den Link, aber da sieht man doch schon warum zB. der Code 
oben in diesem Thread nicht vektorisiert werden kann.

> Loop to be vectorized must be innermost loop if nested

Wenn man das selber explizit macht, wird es eben doch besser.
Geht natuerlich auch mit C++, gibt ja SIMD Bibliotheken dafuer, aber 
dafuer muss man sich erstmal die Schleifen abgewoehnen bzw. das 
iterative Denken.
Aber das mit C++ zu machen zu wollen uebersteigt ja wohl die 
Faehigkeiten der meisten, und ich bezweifle stark das es dann messbar 
schneller waere..

Das mit Python/Pandas/Numpy zu machen is dagegen trivial, wie gesagt 
sind dafuer gemacht.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Das mit Python/Pandas/Numpy zu machen is dagegen trivial, wie gesagt
> sind dafuer gemacht.

Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.

Guter Vorschlag!

Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so, 
dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen 
diese aber nciht zusammenhaengen
1
import pandas as pd
2
  
3
df = pd.read_csv("list.txt")
4
df = df.drop_duplicates(subset=["alle", "spalten", "die", "duplikate", "definieren"])
5
df.to_csv("no_dup.txt")

Ist ungetestet, aber sobald mir jemand Testdaten zuer Verfuegung stellt 
aendert sich das, dann kann man schon mal vergleichen zwischen 
verschiedenen Implementierungen.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so,
> dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen
> diese aber nciht zusammenhaengen

Zum zweiten Mal, drop_duplicates hilft hier nicht.

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Zum zweiten Mal, drop_duplicates hilft hier nicht.

Schieb mal lieber Testdaten rueber anstatt hier von oben herab zu reden.

von Jan K. (jan_k)


Lesenswert?

Es geht hier doch einzig und alleine um Duplikate einer Zeile oder 
nicht?

Ich hätte es so übersetzt

"Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind. 
Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."

Nicht korrekt?
Gibt's Beispiel Daten?

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Zum zweiten Mal, drop_duplicates hilft hier nicht.
>
> Schieb mal lieber Testdaten rueber anstatt hier von oben herab zu reden.
Das mache ich, nachdem du erklärt hast was das Programm des TO macht und 
was drop_duplicates macht.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.
>
> Guter Vorschlag!
>
> Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so,
> dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen
> diese aber nciht zusammenhaengen
> import pandas as pd
>
> df = pd.read_csv("list.txt")
> df = df.drop_duplicates(subset=["alle", "spalten", "die", "duplikate",
> "definieren"])
> df.to_csv("no_dup.txt")

Um nochmal auf den SIMD Teil zurückzukommen auf den sich meine 
Aufforderung bezogen hat. Wo genau setzt drop_duplicates SIMD ein, das 
nicht automatisch vom C Compiler erzeugt wurde?

von udok (Gast)


Angehängte Dateien:

Lesenswert?

Anbei Testdaten mit 100e3 Zeilen.

Hans CPP Program braucht auf meinem Lappi 3.8 Sekunden,
Die Foobar C Implementierung mit ein paar Optimierunen 0.46 Sekunden.

Zeig mal, was du kannst :-)

von Andreas M. (amesser)


Lesenswert?

Wie oben bereits korrekt angemerkt ist kommt der größte Teil des 
Performance-Verlustes durch Verwendung der klasse "string" um den Wert 
der einzelnen Felder zu speichern. Viel zu umständlich.

Für diese Aufgabe wäre es besser die Zeilen "on-the-fly" in Felder zu 
zerlegen und direkt wieder in den Ausgabestream zu schreiben. Schon 
geschriebene Feldewerte merkt man sich in einem extra Array (sinnvoll 
wenn der selbe Werte mehrfach vorkommt) oder sucht einfach immer wieder 
vom begin des ersten relevanten Feldes (wenn Duplikate eher vereinzelt 
auftreten). Letzteres kann man auch noch ein bisl optimieren, in dem man 
den Suchanfang nachzieht wenn man ein Duplikat findet.

von udok (Gast)


Lesenswert?

Jan K. schrieb:
> Es geht hier doch einzig und alleine um Duplikate einer Zeile oder
> nicht?
>
> Ich hätte es so übersetzt
>
> "Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind.
> Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."
>
> Nicht korrekt?
> Gibt's Beispiel Daten?

Ja, so ist es. 4 weil C++ von 0 wegzählt. Daten sind im vorherigen Post.

von Jan K. (jan_k)


Lesenswert?

udok schrieb:
> Jan K. schrieb:
>> Es geht hier doch einzig und alleine um Duplikate einer Zeile oder
>> nicht?
>>
>> Ich hätte es so übersetzt
>>
>> "Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind.
>> Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."
>>
>> Nicht korrekt?
>> Gibt's Beispiel Daten?
>
> Ja, so ist es. 4 weil C++ von 0 wegzählt. Daten sind im vorherigen Post.

Ich weiß, dass C ab 0 beginnt ;) der OP schrieb aber "ab dem dritten 
Eintrag". Nicht, dass da schon ein Bug vorliegt. Ich probiere es Mal mit 
Matlab und Julia 😁

von Mikro 7. (mikro77)


Lesenswert?

udok schrieb:
> Anbei Testdaten mit 100e3 Zeilen.

Solch rege Beteiligung und erst ein alternativer Vorschlag?!

Wer weitere Testdaten braucht...
1
awk 'BEGIN { OFS=";" ; srand(0) ; while (1) { for (i=1;i<=45;++i) $i=int(10 * rand()) ; print }}'

Minimalösung mit awk:
1
dd if=data status=progress | awk -F ';' '{ OFS=FS ; for (i=4 ; i<NF ; ++i) if ($i != "") for (j=i+1 ; j<=NF ; ++j) if ($i==$j) $j="" ; print }' >/dev/null
Läuft mit ca. 1 MB/s.

Das Program des TS mit ca. 6 MB/s.
Das Programm foobar mit ca. 28 MB/s.
Im "Leerlauf" ca. 360 MB/s.

Alles auf einem alten i3 und Ubuntu.

Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen 
langsamer als der FILE stream (zumindest bei meiner Gcc Version).

von mh (Gast)


Lesenswert?

Mikro 7. schrieb:
> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream (zumindest bei meiner Gcc Version).

Vergleichst du das Programm des TO mit dem von foobar?

von Heinzel (Gast)


Lesenswert?

Mikro 7. schrieb:
> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream (zumindest bei meiner Gcc Version).

https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

von Mikro 7. (mikro77)


Lesenswert?

mh schrieb:
> Vergleichst du das Programm des TO mit dem von foobar?

Genau. Allerdings habe ich die fstreams durch cin/cout ersetzt.

Heinzel schrieb:
> https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

Interessant!

Mit std::ios_base::sync_with_stdio(false) kommt das Programm des TS 
jetzt auf 7,5 MB/s. (btw: alle Programme mit -O3)

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Anbei Testdaten mit 100e3 Zeilen.
>
> Hans CPP Program braucht auf meinem Lappi 3.8 Sekunden,
> Die Foobar C Implementierung mit ein paar Optimierunen 0.46 Sekunden.
>
> Zeig mal, was du kannst :-)

Danke, damit kann man schon ich mehr anfangen.

Anscheinend hast du nur ints und floats, also keine Strings, die Datei 
ist im Textformat.

Was mir jetzt noch fehlt ist die Datei mit der Ausgabe, vielleicht noch 
dein Code, oder zumindest die Aussage was da denn alles mitreingerechnet 
wird an Zeit, lesen, verarbeiten und schreiben?

Das finden der Duplikate dauert mit
1
df.duplicated(subset= df.columns[4:])
bei auf meiner Maschine 0.18799471855163574 Sekunden, aber das heisst 
natuerlich nix weil du wohl andere HW hast.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Was mir jetzt noch fehlt ist die Datei mit der Ausgabe

Die korrekte Ausgabe ist durch das Programm im ersten Post definiert.

von Εrnst B. (ernst)


Lesenswert?

Mladen G. schrieb:
> bei auf meiner Maschine 0.18799471855163574 Sekunden, aber das heisst
> natuerlich nix weil du wohl andere HW hast.

und das pro Zeile? Kommt mir reichlich langsam vor.

Bin ich weiter oben auch darauf reingefallen:

Eingabgedatei und Ausgabedatei haben gleichviel Zeilen. Nur werden 
manche Zeilen kürzer.

Ich glaube dein Code macht was Anderes.

von Mladen G. (mgira)


Lesenswert?

Εrnst B. schrieb:
> und das pro Zeile? Kommt mir reichlich langsam vor.

Fuer alle Daten ohne einlesen, schreiben etc. pp.
Nur die Duplikate finden/markieren.

Εrnst B. schrieb:
> Eingabgedatei und Ausgabedatei haben gleichviel Zeilen. Nur werden
> manche Zeilen kürzer.

Danke!

Εrnst B. schrieb:
> Ich glaube dein Code macht was Anderes.

Bestimmt, bin ja auch von etwas anderem ausgegangen.

: Bearbeitet durch User
von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Εrnst B. schrieb:
>> Ich glaube dein Code macht was Anderes.
>
> Bestimmt, bin ja auch von etwas anderem ausgegangen.
Ich hab dich schon 2 Mal darauf hingewiesen, dass drop_duplicates was 
anderes macht als das Programm des TO...

von (Gast)


Lesenswert?

Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt 
und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles 
C++ und std::string_view sollte einiges an Laufzeit einsparen.

von udok (Gast)


Lesenswert?

rµ schrieb:
> Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt
> und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles
> C++ und std::string_view sollte einiges an Laufzeit einsparen.

Schaut so aus, als wäre C++ noch immer eine ewige Baustelle.
In den letzen Jahren hat sich viel positives getan,
aber der Speed von C ist noch in weiter Ferne, zumindest wenn
man in C++ nicht C programmieren will.

Unter Visual Studio bringt std::ios_base::sync_with_stdio(false)
gar nichts...

Ergebnisse ohne "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 19 (gelinkt mit ucrt.dll):
1
test_awk.sh     Seconds=7.51   MB/sec=4.92   Lines/sec=13311
2
test_hans.exe   Seconds=1.39   MB/sec=26.53  Lines/sec=71762
3
test_uk1.exe    Seconds=0.47   MB/sec=78.28  Lines/sec=211742

Ergebnisse mit "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 19 (gelinkt mit ucrt.dll):
1
test_awk.sh     Seconds=7.41   MB/sec=4.99   Lines/sec=13501
2
test_hans.exe   Seconds=1.49   MB/sec=24.84  Lines/sec=67196
3
test_uk1.exe    Seconds=0.47   MB/sec=77.95  Lines/sec=210837

test_hans.exe ist um 0.1 sec langsamer geworden.

Ergebnisse ohne "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 15 (gelinkt mit msvcrt.dll):
1
test_awk.sh     Seconds=7.39   MB/sec=5.00   Lines/sec=13523
2
test_hans.exe   Seconds=3.73   MB/sec=9.90   Lines/sec=26790
3
test_uk1.exe    Seconds=0.45   MB/sec=81.51  Lines/sec=220484

Programmgrösse (VS19):
1
-rwxr-xr-x 1 udo Kein 249344 May  6 18:20 test_hans.exe
2
-rwxr-xr-x 1 udo Kein 105984 May  6 18:20 test_uk1.exe

Programmgrösse (VS15):
1
-rwxr-xr-x 1 udo Kein 294912 May  6 18:18 test_hans.exe
2
-rwxr-xr-x 1 udo Kein  56832 May  6 18:18 test_uk1.exe

Also grosses Program != schnelles Program.

von Heinzel (Gast)


Lesenswert?

rµ schrieb:
> Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt
> und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles
> C++ und std::string_view sollte einiges an Laufzeit einsparen.
1
#include <array>
2
#include <fstream>
3
#include <iostream>
4
#include <string_view>
5
#include <string>
6
7
std::array<std::string_view, 45> csv_entries;
8
9
int main()
10
{
11
    using namespace std;
12
13
    std::ifstream inFile("list.txt");
14
    std::ofstream outFile("nodup.txt");
15
    std::ios_base::sync_with_stdio(false);
16
17
    if (!inFile.is_open()) {
18
        return -1;
19
    }
20
21
    string line;
22
    while (getline(inFile, line)) {
23
        std::string_view line_view = line;
24
        for (std::size_t a = 0, b, i = 0;
25
             (b = line_view.find(';', a)) != std::string_view::npos;
26
             a = b + 1) {
27
            csv_entries[i++] =
28
                std::string_view(line.data() + a, b + 1 - a);
29
        }
30
        for (std::size_t i = 3; i < csv_entries.size() - 1; ++i) {
31
            for (std::size_t j = i + 1; j < csv_entries.size(); ++j) {
32
                if (!csv_entries[i].empty() &&
33
                    csv_entries[i] == csv_entries[j]) {
34
                    csv_entries[j] = ";";
35
                }
36
            }
37
        }
38
        for (const auto sv : csv_entries) {
39
            outFile.write(sv.data(), sv.length());
40
        }
41
        outFile.put('\n');
42
    }
43
    return 0;
44
}
1
g++ -O3 -std=c++17 -Wall -o to-opt to-opt.cpp

In einem tmpfs von einem i7-8650U (1.90GHz) ausgeführt:
1
[shell:/tmp/cpp]$ time ./to
2
real  0m0,931s
3
user  0m0,901s
4
sys  0m0,030s
5
6
[shell:/tmp/cpp]$ time ./to
7
real  0m0,927s
8
user  0m0,905s
9
sys  0m0,022s
10
11
[shell:/tmp/cpp]$ time ./to
12
real  0m0,930s
13
user  0m0,917s
14
sys  0m0,013s
15
16
[shell:/tmp/cpp]$ mv nodup.txt nodup.txt-ref
17
18
[shell:/tmp/cpp]$ time ./to-opt 
19
real  0m0,310s
20
user  0m0,289s
21
sys  0m0,022s
22
23
[shell:/tmp/cpp]$ time ./to-opt 
24
real  0m0,310s
25
user  0m0,296s
26
sys  0m0,014s
27
28
[shell:/tmp/cpp]$ time ./to-opt 
29
real  0m0,316s
30
user  0m0,286s
31
sys  0m0,031s
32
33
[shell:/tmp/cpp]$ cmp nodup.txt* && echo $?
34
0

speedup ggü. TOs Original:
1
octave:2> mean([901 905 917]) / mean([289 296 286])
2
ans =  3.1263

PS: Wenn ich list.txt mit nodup.txt vergleiche, dann entfernt das 
originale Programm vom TO gar keine Felder, außer in der allerersten 
Zeile. Wirkt recht sinnlos auf mich.

von udok (Gast)


Lesenswert?

Heinzel schrieb:
> PS: Wenn ich list.txt mit nodup.txt vergleiche, dann entfernt das
> originale Programm vom TO gar keine Felder, außer in der allerersten
> Zeile. Wirkt recht sinnlos auf mich.

Das ist richtig, ist aber bei dem Algorithmus
egal, da sowieso nicht vorher abgebrochen wird.

Du kannst das awk Skript von mikro77 verwenden, das verwendet
Zufallsdaten.

Ich habe versucht dein C++ zu übersetzen, ging leider weder unter
VS15, noch unter VS19:

test_heinzel.cpp(4): fatal error C1083: Cannot open include file: 
'string_view': No such file or directory

von Heinzel (Gast)


Lesenswert?

udok schrieb:
> Ich habe versucht dein C++ zu übersetzen, ging leider weder unter
> VS15, noch unter VS19:
>
> test_heinzel.cpp(4): fatal error C1083: Cannot open include file:
> 'string_view': No such file or directory

benötigt C++17 für string_view

von Heinzel (Gast)


Lesenswert?

Zum Vergleich auf meinem Rechner: foobars C-Code:
1
[shell:/tmp/cpp]$ gcc -O3 -Wall -march=native -o foobar foobar.c; for i in `seq 3`; do time ./foobar < list.txt > nodup.txt; done
2
3
real  0m0,439s
4
user  0m0,428s
5
sys  0m0,011s
6
7
real  0m0,458s
8
user  0m0,442s
9
sys  0m0,016s
10
11
real  0m0,532s
12
user  0m0,512s
13
sys  0m0,020s

Somit ist der C++ Code schneller :-)

von Jan K. (jan_k)


Lesenswert?

Hier, unter Windows mit MinGW g++.exe (x86_64-posix-seh-rev0, Built by 
MinGW-W64 project) 8.1.0 sieht das alles etwas anders aus.

Alles mit g++, O3 und std c++17 kompiliert.

foobars c Version, ich schätze, da ist aber einfach Get-Content auch 
lahmarschig...
1
~\Git\juliaVsCpp                                                                                                                                   [20:11]  
2
❯ Measure-Command { Get-Content list.txt | & .\removeDuplicatesInRow_foobar.exe }
3
4
5
Days              : 0
6
Hours             : 0
7
Minutes           : 0
8
Seconds           : 8
9
Milliseconds      : 352

Heinzels cpp Variante:
1
~\Git\juliaVsCpp                                                                                                                                   [20:11]  
2
❯ Measure-Command { .\removeDuplicatesInRow_Heinzel_cpp17.exe }
3
4
5
Days              : 0
6
Hours             : 0
7
Minutes           : 0
8
Seconds           : 1
9
Milliseconds      : 916

OPs cpp Variante
1
~\Git\juliaVsCpp                                                                                                                                   [20:13]  
2
❯ Measure-Command { .\removeDuplicatesInRow_OP.exe }
3
4
5
Days              : 0
6
Hours             : 0
7
Minutes           : 0
8
Seconds           : 2
9
Milliseconds      : 249

Das ist irgendwie alles etwas langsamer als bei euch ;) Aber auch hier 
gewinnt die moderne C++ Variante. Gibt's die C Version auch mit fopen() 
oder so? Denke, der stdin in der Powershell ist der Flaschenhals.

von udok (Gast)


Angehängte Dateien:

Lesenswert?

Ich habe dir die foobar Version mit fopen() ins 7zip kopiert.

Es ist auch ein bash Skript run.sh und build.sh dabei,
dass die Programme ausführt, und die MB/sec berechnet.

Jetzt brauchen wir noch einen Python Experten :-)

von mh (Gast)


Lesenswert?

udok schrieb:
> Jetzt brauchen wir noch einen Python Experten :-)

Hier eine Python Version von einem 
SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten. 
Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante, 
also < 1 Sekunde auf meinem Rechner.
1
import csv
2
3
def main():
4
    with open('list.txt', mode='r') as fin, open('nodup.py.txt', mode='w') as fout:
5
        reader = csv.reader(fin, delimiter=';')                                                                                                                                                                                                   
6
        for row in reader:                                                                                                                                                                                                                        
7
            known_elements = set()                                                                                                                                                                                                                
8
            out = ';'.join(row[:3])                                                                                                                                                                                                       
9
            for element in row[3:]:                                                                                                                                                                                                       
10
                out += ';'                                                                                                                                                                                                                
11
                if element not in known_elements:                                                                                                                                                                                         
12
                    out += element
13
                    known_elements.add(element)
14
            print(out, file=fout)
15
                                                                                                                                                                                                                       
16
if __name__ == '__main__':                                                                                                                                                                                             
17
    main()

von MaWin (Gast)


Lesenswert?

mh schrieb:
> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
> also < 1 Sekunde auf meinem Rechner.

Das läuft bei mir nicht?

von mh (Gast)


Lesenswert?

MaWin schrieb:
> mh schrieb:
>> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
>> also < 1 Sekunde auf meinem Rechner.
>
> Das läuft bei mir nicht?

Wenn du Hilfe willst, musst du schon nen paar Infos rausrücken. Sowas 
wie eine genaue Beschreibung was "läuft nicht" bedeutet.

von MaWin (Gast)


Lesenswert?

mh schrieb:
> nen paar Infos rausrücken

Ok, schwarze console sonst nichst. :-(

von mh (Gast)


Lesenswert?

Wie rufst du das Skript auf? Was ist die Ausgabe nach Strg-C? Hast du 
überhaupt Python installiert?

von Jan K. (jan_k)


Lesenswert?

Das Python skript gibt ja auch nix aus ;)

Bei mir läufts (hab aber das Ergebnis nicht kontrolliert)
1
❯ Measure-Command { C:/Users/janka/anaconda3/python.exe c:/Users/janka/Git/juliaVsCpp/removeDuplicatesInRow_python.py  }
2
3
4
Days              : 0
5
Hours             : 0
6
Minutes           : 0
7
Seconds           : 3
8
Milliseconds      : 43

von foobar (Gast)


Lesenswert?

> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream

Ich denke nicht - std:string dürften den größten Unterschied ausmachen.

> Somit ist der C++ Code schneller :-)

;-)  Nun ja, das war eine Quick'n'Dirty Trivialimplementation.  Das 
Einzelzeichenlesen dürfte einiges kosten.  Umstellen auf zeilenweisen 
I/O sollte schon einiges bringen:
1
#include <stdio.h>
2
#include <string.h>
3
4
int main(int argc, char **argv)
5
{
6
    char buf[32768];
7
8
    // if (!freopen("list.txt", "r", stdin)) return 1;
9
    // if (!freopen("nodup.txt", "w", stdout)) return 1;
10
11
    while (fgets(buf, sizeof(buf), stdin))
12
    {
13
        char *field[64], *p;
14
        int i;
15
16
        for (field[i = 0] = p = buf; (p = strchr(p, ';')); p++)
17
            if (i < sizeof(field)/sizeof(*field) - 1)
18
                *p = 0, field[++i] = p+1;
19
20
        for (int n = 3; n < i-1; n++)
21
            if (field[n][0])
22
                for (int m = n+1; m < i; m++)
23
                    if (strcmp(field[n], field[m]) == 0)
24
                        field[m][0] = 0;
25
26
        p = buf;
27
        for (int n = 0; n < i; n++)
28
        {
29
            char *s = field[n];
30
            while (*s)
31
                *p++ = *s++;
32
            *p++ = ';';
33
        }
34
        *p++ = '\n';
35
        *p = 0;
36
        fputs(buf, stdout);
37
    }
38
    return 0;
39
}

Das ist die Krux mit C++: benutzt man es wie eine High-Level-Sprache, 
bekommt man auch die Performance einer High-Level-Sprache.  Man kann nur 
gewinnen, wenn man entweder auf C-Niveau programiert oder komplexe 
Konstrukte ausnutzen kann (wie z.B. unten im Lua-Kode Patternmatching 
oder Assoziativarrays).

> Jetzt brauchen wir noch einen Python Experten :-)

Wie wär's mit Lua oder LuaJIT? ;-)
1
-- io.input"test.txt"
2
-- io.output"nodup.txt"
3
local out = io.write
4
5
for l in io.lines() do
6
    local seen = {}
7
    local a,b = l:match"(.-;.-;.-;)(.*)"
8
    out(a)
9
    for f in b:gmatch".-;" do
10
        if seen[f] then
11
            out";"
12
        else
13
            out(f)
14
            seen[f] = true
15
        end
16
    end
17
    out"\n"
18
end

von Heinzel (Gast)


Angehängte Dateien:

Lesenswert?

foobar schrieb:
> ;-)  Nun ja, das war eine Quick'n'Dirty Trivialimplementation.  Das
> Einzelzeichenlesen dürfte einiges kosten.  Umstellen auf zeilenweisen
> I/O sollte schon einiges bringen:

Anscheinend bringt das gar nicht mal so viel:
1
[cvs_fun]$ cat test_hans.timing 
2
user  0m1,997s
3
user  0m1,968s
4
user  0m1,972s
5
user  0m1,976s
6
user  0m2,011s
7
[cvs_fun]$ cat test_foobar2.timing 
8
user  0m1,705s
9
user  0m1,788s
10
user  0m1,776s
11
user  0m1,753s
12
user  0m1,742s
13
[cvs_fun]$ cat test_foobar3.timing 
14
user  0m1,500s
15
user  0m1,478s
16
user  0m1,552s
17
user  0m1,510s
18
user  0m1,528s
19
[cvs_fun]$ cat test_heinzel.timing 
20
user  0m1,000s
21
user  0m1,014s
22
user  0m0,994s
23
user  0m1,023s
24
user  0m1,010s
25
[cvs_fun]$ cat test_heinzel2.timing
26
user  0m1,002s
27
user  0m0,982s
28
user  0m0,989s
29
user  0m0,997s
30
user  0m1,020s

Diesmal auf einem anderen (alten) Rechner ausgeführt: Intel Core2 T7200, 
2.00GHz. Deinen neuen Code bezeichne ich als "test_foobar3.c".

Kompiliert (gcc 8) und in einem tmpfs/RAM ausgeführt mit:
1
g++ -O3 -std=c++17 -Wall -march=native -o test_hans test_hans.cpp
2
gcc -O3 -std=c17 -Wall -march=native -o test_foobar2 test_foobar2.c
3
gcc -O3 -std=c17 -Wall -march=native -o test_foobar3 test_foobar3.c
4
g++ -O3 -std=c++17 -march=native -Wall -o test_heinzel test_heinzel.cpp
5
g++ -O3 -std=c++17 -march=native -Wall -o test_heinzel2 test_heinzel2.cpp
6
7
# analog für die anderen
8
for i in `seq 5`; do time ./test_foobar2; done 2>&1 | grep user > test_foobar2.timing

Die angehängte test_heinzel2.cpp enthält einen fix: Die Überprüfung auf 
ein leeres Feld war unnötig (dead code), weil die extrahierten CSV 
Felder immer den ; beinhalten und deshalb nie leer sein können. Sie ist 
nochmal geringfügig schneller als die ursprüngliche Implementierung. 
Seltsamerweise wird sie langsamer, wenn man statt
1
csv_entries[i++] = std::string_view(line.data() + a, b + 1 - a);

die substr-Funktion verwendet:
1
csv_entries[i++] = line_view.substr(a, b + 1);

bzw. ganz ohne die "a" Variable und mit remove_prefix:
1
for (std::size_t b, i = 0;
2
     (b = line_view.find(';')) != std::string_view::npos;
3
     )
4
{
5
    csv_entries[i++] = line_view.substr(0, b + 1);
6
    line_view.remove_prefix(b + 1);
7
}

Bei foobars C Implementierung hätte ich mir eigentlich etwas mit strtok 
vorgestellt. IMO sollte es möglich sein, dass die C und C++ 
Implementierungen am Ende gleich schnell sind.

von udok (Gast)


Angehängte Dateien:

Lesenswert?

mh schrieb:
> Hier eine Python Version von einem
> SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten.
> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
> also < 1 Sekunde auf meinem Rechner.

Super :-)

Nur macht es nicht, was die anderen Programme machen...

Im Anhanng ein 10 Zeilen Input mit soll und ist Ausgabe.

von Sven B. (scummos)


Lesenswert?

foobar schrieb:
> Das ist die Krux mit C++: benutzt man es wie eine High-Level-Sprache,
> bekommt man auch die Performance einer High-Level-Sprache.

Das stimmt nicht. Der Trick ist, dass man es wie eine High-Level-Sprache 
benutzen muss, während man trotzdem noch versteht was intern daraus 
wird. Dann ist C++ trotz hohem Abstraktionsniveau (z.B. für den Leser 
des Codes) schneller als viele andere vergleichbar abstrakte Sprachen.

von Sven B. (scummos)


Angehängte Dateien:

Lesenswert?

Ausserdem wird hier immer noch wild herumgeraten. Das langsame an dem 
heinz-Programm ist das Vergleichen der Strings, hier muss man 
optimieren, wenn man es schneller haben will. Evtl. helfen eine 
sortierte liste oder eine std::map.

von udok (Gast)


Lesenswert?

Heinzel schrieb:
> Bei foobars C Implementierung hätte ich mir eigentlich etwas mit strtok
> vorgestellt. IMO sollte es möglich sein, dass die C und C++
> Implementierungen am Ende gleich schnell sind.

Sollte möglich sein, nur schaut dann das C++ Program so aus wie das C 
Program.

Aktuelle Daten mit VS 2019 unter Win10 kompiliert (-O2):
1
test_mikro77_awk.sh  Seconds=7.28   MB/sec=5.08   Lines/sec=13736
2
test_foobar_lua.sh   Seconds=3.15   MB/sec=11.75  Lines/sec=31771
3
test_hans.exe        Seconds=1.17   MB/sec=31.59  Lines/sec=85457
4
test_heinzel.exe     Seconds=0.74   MB/sec=49.78  Lines/sec=134643
5
test_heinzel2.exe    Seconds=0.71   MB/sec=52.34  Lines/sec=141563
6
test_foobar3.exe     Seconds=0.48   MB/sec=77.37  Lines/sec=209267
7
test_foobar2.exe     Seconds=0.47   MB/sec=79.45  Lines/sec=214901

Die Performance der C++ Programme hängt ziemlich stark von
der jeweiligen Version des Compilers und der Runtime ab (Faktor 3),
wenn es überhaupt compiliert...

C ist viel gutmütiger, compiliert immer, und liefert immer dieselbe gute 
Performance.

Einzelne Zeichen lesen ist kein Performance Problem,
solange die Funktion ein Makro ist.

strcmp ist ebenfalls kein grosses Performanceproblem in C.

Python fehlt noch :-/

von udok (Gast)


Lesenswert?

Hier noch die Werte für die Zufallsdaten, generiert mit dem awk Skript 
von foobar:
1
test_mikro77_awk.sh  Seconds=3.06   MB/sec=2.97   Lines/sec=32643
2
test_foobar_lua.sh   Seconds=1.35   MB/sec=6.75   Lines/sec=74179
3
test_hans.exe        Seconds=0.78   MB/sec=11.68  Lines/sec=128321
4
test_heinzel.exe     Seconds=0.74   MB/sec=12.38  Lines/sec=136012
5
test_heinzel2.exe    Seconds=0.62   MB/sec=14.74  Lines/sec=162021
6
test_foobar3.exe     Seconds=0.20   MB/sec=45.52  Lines/sec=500170
7
test_foobar2.exe     Seconds=0.17   MB/sec=52.26  Lines/sec=574303

Jeder Eintrag ist nur eine Ziffer, daher sind die Files deutlich 
kleiner,
und die MB/sec sind kleiner.

von mh (Gast)


Lesenswert?

Sven B. schrieb:
> Ausserdem wird hier immer noch wild herumgeraten. Das langsame an dem
> heinz-Programm ist das Vergleichen der Strings, hier muss man
> optimieren, wenn man es schneller haben will. Evtl. helfen eine
> sortierte liste oder eine std::map.
Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der 
Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD 
anders aussehen...

udok schrieb:
> mh schrieb:
>> Hier eine Python Version von einem
>> SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten.
>> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
>> also < 1 Sekunde auf meinem Rechner.
>
> Super :-)
>
> Nur macht es nicht, was die anderen Programme machen...
>
> Im Anhanng ein 10 Zeilen Input mit soll und ist Ausgabe.
Bei mir liefert das Skript eine Ausgabe, die identisch zu deiner 
nodup_soll.txt ist. Bist du dir sicher, dass du das Skript richtig 
kopiert hast? Also auf die Leerzeichen geachtet? Ich wüsste auch nicht, 
wie die nodup_ist.txt heruskommen soll.

von Yalu X. (yalu) (Moderator)


Lesenswert?

udok schrieb:
> Nur macht es nicht, was die anderen Programme machen...

Das print ist bei dir zwei Stufen zu weit eingerückt. Es sollte die 
gleiche Einrückung wie das darüberliegende for haben.

von udok (Gast)


Lesenswert?

Im Python Skript war ein Leerzeichen falsch, jetzt läuft es durch,
und mit einer super Performance.

Ich habe noch mit dem Mingw Compiler experimentiert, das
bringt aber nix gutes.
Letztendlich ist die Qualität der Runtime der entscheidende Faktor bei 
der Performance.
1
test_mikro77_awk.sh         Seconds=7.46   MB/sec=4.96   Lines/sec=13411
2
test_foobar_lua.sh          Seconds=3.15   MB/sec=11.74  Lines/sec=31768
3
test_mh_python.sh           Seconds=1.59   MB/sec=23.25  Lines/sec=62894
4
test_hans.exe               Seconds=1.18   MB/sec=31.42  Lines/sec=84996
5
test_heinzel2_mingw.exe     Seconds=0.89   MB/sec=41.31  Lines/sec=111738
6
test_heinzel.exe            Seconds=0.77   MB/sec=47.89  Lines/sec=129524
7
test_heinzel2.exe           Seconds=0.70   MB/sec=52.48  Lines/sec=141943
8
test_foobar2_mingw.exe      Seconds=0.64   MB/sec=57.48  Lines/sec=155468
9
test_foobar3.exe            Seconds=0.48   MB/sec=77.38  Lines/sec=209302
10
test_foobar2.exe            Seconds=0.47   MB/sec=78.94  Lines/sec=213523

von Sven B. (scummos)


Lesenswert?

mh schrieb:
> Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der
> Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD
> anders aussehen...

Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh 
nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern 
relativ aehnlich aussehen.

udok schrieb:
> C ist viel gutmütiger, compiliert immer, und liefert immer dieselbe gute
> Performance.

Wir haetten einfach alle bei F77 bleiben sollen. Exception Handling und 
Resource Management mit goto ist sicherlich der Weisheit letzter 
Schluss; der Versuch, aehnlich effiziente Sprachen zu entwickeln, die 
dafuer bessere Loesungen haben, ist ein Irrweg. /s

: Bearbeitet durch User
von udok (Gast)


Lesenswert?

Sven B. schrieb:
> Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh
> nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern
> relativ aehnlich aussehen.

In den Tests sind die Daten nach dem 2. Durchlauf eh im RAM.
Die Festplatte/SSD ist da wurscht.

von udok (Gast)


Lesenswert?

Sven B. schrieb:
> Wir haetten einfach alle bei F77 bleiben sollen. Exception Handling und
> Resource Management mit goto ist sicherlich der Weisheit letzter
> Schluss; der Versuch, aehnlich effiziente Sprachen zu entwickeln, die
> dafuer bessere Loesungen haben, ist ein Irrweg. /s

Vielleicht kannst du ja ein Fortran Program herzeigen?
Dann können wir ja drüber nachdenken.

von mh (Gast)


Lesenswert?

Sven B. schrieb:
> mh schrieb:
>> Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der
>> Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD
>> anders aussehen...
>
> Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh
> nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern
> relativ aehnlich aussehen.

Wenn das OS im Hintergrund die Datei langsam in den RAM lädt, kann die 
CPU machen was sie will, solange sie ihre Arbeit erledigt bevor der 
nächste Block im Filecache ist (abgesehen von Randeffekten für die 
letzte Zeile).

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Python fehlt noch :-/

Hi,

wie ich feststellen musste, laesst sich das nicht vektorisieren mit 
Pandas/Numpy, da die Verarbeitung innhalb der einzelnen Zeilen 
stattfindet, anstatt dass alle Zeilen auf einmal verarbeitet werden 
koennen.

Damit bleibt nix anderes uebrig, als da wieder zu iterieren, bzw. ich 
finde da keinen anderen Weg.
1
import pandas as pd
2
3
df = pd.read_csv("list.txt", sep=';', header=None, skipinitialspace=True)
4
is_duplicated = df.apply(pd.Series.duplicated, axis=1)
5
df = df.where(~is_duplicated, "")
6
df.to_csv("nodup.txt", sep=';', header=None, )
Das laeuft so sehr langsam (insgesamt ca. 14 Sekunden bei mir), da eben 
keine Vektorisierung moeglich ist bei finden der Duplikate in einer 
Zeile, das ersetzten dagegen laeuft wiederum vektorisiert.

diese Zeile dauert ca. 12 Sekunden, laueft iterativ (apply(..)) ueber 
alle Zeilen:
1
is_duplicated = df.apply(pd.Series.duplicated, axis=1)

D.h. diese Zeile braucht bei mir 0,2540872097015381 Sekunden
1
df = df.where(~is_duplicated, "")
Damit werden alle gefundenen Duplikate ersetzt.

C++ ist da schneller.

von Jan K. (jan_k)


Lesenswert?

udok schrieb:
> Ich habe dir die foobar Version mit fopen() ins 7zip kopiert.
>
> Es ist auch ein bash Skript run.sh und build.sh dabei,
> dass die Programme ausführt, und die MB/sec berechnet.
>
> Jetzt brauchen wir noch einen Python Experten :-)

Vielen Dank! Wie lässt du die sh file bei dir laufen unter Windows? 
Cygwin oder Git Bash oder im WSL?

edit: in beidem läuft dein run.sh nicht (nachdem es Probleme mit dem 
Zeilenumbruch gab, kann aber auch an GIT gelegen haben)

WSL2, Ubuntu
1
find-duplicates-benchmark/cvs_fun$ ./run.sh
2
gawk: cmd. line:1: BEGIN { print  - ; }
3
gawk: cmd. line:1:                  ^ syntax error

edit: ich muss erstmal bash v5 installieren... sonst gibts 
$EPOCHREALTIME nicht. Gehe ich also davon aus, dass du in der WSL 
unterwegs bist?

: Bearbeitet durch User
von udok (Gast)


Angehängte Dateien:

Lesenswert?

Jan K. schrieb:
> Vielen Dank! Wie lässt du die sh file bei dir laufen unter Windows?
> Cygwin oder Git Bash oder im WSL?

Ich verwende https://www.msys2.org - wenn die bash aktuell ist, laufen 
die Skripts auch mit Cygwin, WSL2 und Linux.

Die aktuellen Source Files mit den compilierten Programmen
für Win10 und den Skripten run.sh und build.sh sind angehängt.

> edit: in beidem läuft dein run.sh nicht (nachdem es Probleme mit dem
> Zeilenumbruch gab, kann aber auch an GIT gelegen haben)

Sollten Unix Zeilenumbrüche sein, sonst gibt es nur Ärger.

@mgira
> wie ich feststellen musste, laesst sich das nicht vektorisieren mit
> Pandas/Numpy, da die Verarbeitung innhalb der einzelnen Zeilen
> stattfindet, anstatt dass alle Zeilen auf einmal verarbeitet werden
> koennen.

Die Python Variante läuft eigentlich schon sehr schnell,
da ist nicht viel Unterschied zu C++ ohne string_view,
was es erst in C++17 gibt.

Ich habe noch ein Windows Native Program angehängt, das ganz
ohne C Runtime auskommt, alle Programme sind dynamisch mit der MS 
Runtime
gelinkt, hier die Ergebnisse:
1
test_mikro77_awk.sh       Progsize=233     Seconds=7.19   MB/sec=5.14   Lines/sec=13913
2
test_foobar_lua.sh        Progsize=360     Seconds=3.13   MB/sec=11.82  Lines/sec=31978
3
test_mh_python.sh         Progsize=553     Seconds=1.55   MB/sec=23.86  Lines/sec=64548
4
test_hans.exe             Progsize=34304   Seconds=1.26   MB/sec=29.26  Lines/sec=79135
5
test_heinzel.exe          Progsize=27648   Seconds=0.75   MB/sec=49.59  Lines/sec=134130
6
test_heinzel2.exe         Progsize=27648   Seconds=0.78   MB/sec=47.63  Lines/sec=128846
7
test_foobar3.exe          Progsize=11264   Seconds=0.42   MB/sec=87.83  Lines/sec=237571
8
test_foobar2.exe          Progsize=11264   Seconds=0.42   MB/sec=88.68  Lines/sec=239869
9
test_win_native.exe       Progsize=4096    Seconds=0.34   MB/sec=109.97 Lines/sec=297456

Das schnellste Program schafft 110 MB/sec, und hat gerade mal 1844 Bytes
und belegt einen 4k Sektor auf der SSD.
Die SSD schafft über 1GB/sec, die Programme sind zumindest
bei den relativ kleinen Files nicht IO limitiert.

von Jan K. (jan_k)


Lesenswert?

Hab auch nochmal mit Matlab rumgespielt. High level Sprache, also auch 
nicht zu viel auf low level rumfrickeln, sondern vektorisieren wo geht.

Das Kernproblem ist, dass ML column major die Daten im Speicher ablegt. 
Man kann also wunderbar eine gesamte Spalte oder ein Subset daraus lesen 
und bearbeiten, manuell dadurch zu iterieren, um alle Spalten und eine 
Zeile zu bekommen ist ein Graus. Da hab' ich nach einigen Minuten mal 
abgebrochen bei der Trivial Lösung mit `table` Datentyp.

Da wir hier aber ja keine Fancy Operationen auf coolen Datentypen machen 
wollen, sondern eine String Matrix vollkommen reicht, kann man auch 
`readmatrix` nehmen.

Interessanterweise spielt es dann doch keine Rolle, ob man über Zeilen 
oder Spalten iteriert.

Es findet alles im RAM statt, also wird die Lösung irgendwann abkacken, 
wenn die Dateien zu groß sind...

Ich bin mit den selben Voraussetzungen dran gegangen, was delimiter, 
#Variables und so weiter angeht, ein automatisches Erkennen dauert ein 
paar hundert Millisekunden mehr.
1
function T = mat()
2
opts = delimitedTextImportOptions('NumVariables',45,"Delimiter",";","VariableTypes",repmat("string",45,1)); % kommentieren, um floats zu bekommen
3
T = readmatrix("list.txt", opts);
4
5
delIdx = true(size(T));
6
7
for iRow = 1:height(T) % iterate through rows
8
    [~,ia] = unique(T(iRow,4:end)); 
9
    delIdx(iRow, [(1:3)'; ia+3]) = false;
10
end
11
12
T(delIdx) = missing;
13
writematrix(T, "nodup_matlab.txt","Delimiter",";");
14
end

Timings:
1
./test_awk.sh        Seconds=6.31   MB/sec=1.44   Lines/sec=15851
2
./test_hans.exe      Seconds=2.30   MB/sec=3.96   Lines/sec=43465
3
./test_foobar2.exe   Seconds=0.27   MB/sec=34.20  Lines/sec=375803
4
./matlab_string      Seconds=9.52
5
./matlab_double      Seconds=4.39


@mgira, bei dir fehlt noch, dass alles ab der 4. Spalte geprüft werden 
muss. Und bringt es evtl. was, den Datensatz zu transponieren?

Quintessenz für mich:
1) Meine Güte, ist table lahmarschig... egal ob rowfun oder manuelle 
Iteration. Habe beim selben Test nach 200 Sekunden abgebrochen
2) Matlab ist auf Augenhöhe mit Pandas, wenn man einen primiveren 
Datentyp (string matrix) verwendet
3) Strings in ML sind gar nicht mehr so langsam wie sie mal waren
4) Output Variablen werden berechnet, obwohl sie nicht gebraucht werden 
(~), wtf...
5) row vs col major ist wohl doch nicht so wichtig
6) der Profiler ist wichtig
7) arrayfun ist langsamer als manuelles loopen :(

von Vorschlag (Gast)


Lesenswert?

Hier noch eine Idee grob skizziert:

File mit readahead in Speicher mappen (mmap)

Sich zum n-ten Separator via Pointer ranrobben.
Nach dem n-ten Seperator Hash bis zum Zeilenende bilden.
Den Hash in der Hash-Tabelle suchen und ggf. Hashinput vergleichen.
  Falls gefunden
    weiter
  Falls nicht
    Hash in Tabelle speichern und den Hashinput als Pointer in die 
gemappte Datei speichern
    Zeile ausgeben (vorher den Pointer auf den aktuellen Zeilenanfang 
sichern)

nächste Zeile

Die Anzahl der Hashbuckets in der Hashtabelle ist kritisch, dafür bietet 
sich eine Heuristik über die Dateigrösse an.

Richtig implementiert sollte man mit wenig speicherkopieren und wenig 
zusätzlichen Speicher und funktionsaufrufen auskommen.

Evtl. lässt sich das auf mehrere CPUs verteilen wenn man den Input auf 
die CPUs aufteilt und die Hashsuche nur in einer Instanz laufen lässt.

von Mladen G. (mgira)


Lesenswert?

udok schrieb:
> Die Python Variante läuft eigentlich schon sehr schnell,
> da ist nicht viel Unterschied zu C++ ohne string_view,
> was es erst in C++17 gibt.

Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und 
Vektorisierung in Python/Pandas darzustellen, denn damit haette 
Python/pandas eine echte Chance schneller zu sein, theoretisch.


Jan K. schrieb:
> @mgira, bei dir fehlt noch, dass alles ab der 4. Spalte geprüft werden
> muss. Und bringt es evtl. was, den Datensatz zu transponieren?

Ja das fehlt noch.
transform ist eine sehr gute Idee! :)
Den dataframe "kippen", dann koennte man spaltenweise vektorisiert 
arbeiten und muss nur ueber die 44 Spalten iterieren, anstatt ueber alle 
Zeilen zu iterieren.

Ich probier das mal.

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und
> Vektorisierung in Python/Pandas darzustellen, denn damit haette
> Python/pandas eine echte Chance schneller zu sein, theoretisch.

Kannst du mal genau erklären, was deiner Meinung nach der Unterschied 
zwischen Iteration in C++ und Vektorisierung in Python ist?

Mladen G. schrieb:
> Ja das fehlt noch.
> transform ist eine sehr gute Idee! :)
> Den dataframe "kippen", dann koennte man spaltenweise vektorisiert
> arbeiten und muss nur ueber die 44 Spalten iterieren, anstatt ueber alle
> Zeilen zu iterieren.
Welche Operationen können dann deiner Meinung nach vektorisiert 
ausgeführt werden?

von Mladen G. (mgira)


Lesenswert?

mh schrieb:
> Kannst du mal genau erklären, was deiner Meinung nach der Unterschied
> zwischen Iteration in C++ und Vektorisierung in Python ist?

Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist, 
egal in welcher Sprache.
Mein naiver Ansatz war wohl zu naiv um das zu zeigen, kann auch sein 
dass ich da komplett falsch liege.

mh schrieb:
> Welche Operationen können dann deiner Meinung nach vektorisiert
> ausgeführt werden?

Das suchen nach Duplikaten pro Zeile, aber da Pandas da nicht mitmacht, 
muss ich das wohl erst in ein Format bringen bei dem Pandas das macht, 
da kam der Vorschlag mit transform, also den "dataframe zur Seite 
kippen", Zeilen zu  Spalten, dann sollte es auch mit der Vektorisierung 
klappen, iterieren muesste man dann nur noch ueber die Spalten.
Ob das dann mit dem ganzen umwandeln des DF schneller ist, muesste ich 
dann mal sehen.

von Jan K. (jan_k)


Lesenswert?

mh schrieb:
> Welche Operationen können dann deiner Meinung nach vektorisiert
> ausgeführt werden?

Bei Matlab und Python heißt vektorisieren eher, auf kompletten Spalten 
(also allen Zeilen gleichzeitig) zu operieren. Das meinte ich oben mit 
column Major. Dann kann es sehr schnell werden, weil die Bereiche im 
Speicher hintereinander liegen. Man kann z.b. sowas machen
1
A = rand (1000, 1000); % 1000x1000 matrix
2
Col1 = A(:,1) + 200;

Man muss also nicht explizit über alle Elemente iterieren, sondern 
operiert direkt auf Vektoren (oder auch Matrizen, geht aber im TO 
Beispiel nicht). I
In meinem Beispiel wird 200 auf alle Elemente der ersten Spalte addiert. 
Und das ist zig Fach schneller, als das in einem Loop zu machen. Es wird 
dann direkt die richtige BLAS Funktion aufgerufen und teilweise kann das 
auch über SIMD wirklich in der CPU vektorisiert werden afaik. Aber ich 
weiß nicht, wann das kickt und wann eben nicht.
Jedenfalls sollte man in beiden Sprachen so wenig wie möglich iterativ 
auf einzelnen Elementen machen und eher "größer" denken. Ist mehr 
mathematisch angehaucht finde ich. Am Ende muss man das allerdings auch 
so machen, weil beide Sprachen als interpretierte Sprachen keine Chance 
haben gegen C und co

von Jan K. (jan_k)


Lesenswert?

Mladen G. schrieb:
> Das suchen nach Duplikaten pro Zeile, aber da Pandas da nicht mitmacht,
> muss ich das wohl erst in ein Format bringen bei dem Pandas das macht,
> da kam der Vorschlag mit transform, also den "dataframe zur Seite
> kippen", Zeilen zu  Spalten, dann sollte es auch mit der Vektorisierung
> klappen, iterieren muesste man dann nur noch ueber die Spalten.
> Ob das dann mit dem ganzen umwandeln des DF schneller ist, muesste ich
> dann mal sehen.

In Matlab ist es das jedenfalls nicht :( aber das heißt nix. Fand die 
Idee gut :P

Mladen G. schrieb:
> Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist,
> egal in welcher Sprache.
> Mein naiver Ansatz war wohl zu naiv um das zu zeigen, kann auch sein
> dass ich da komplett falsch liege.

Davon ging ich zuerst auch aus. Bei näherem Nachdenken bin ich mir nicht 
mehr so sicher. Die Low Level libs, BLAS und Co könnten das auch wieder 
nur in eine iterative Form bringen. Und damit ist das alles 
syntaktischer Zucker. Ich suche Mal, ob es dazu Infos gibt. Noch denke 
ich auch, dass vektorisiert schneller ist. Bin gespannt

von mh (Gast)


Lesenswert?

Mladen G. schrieb:
> mh schrieb:
>> Kannst du mal genau erklären, was deiner Meinung nach der Unterschied
>> zwischen Iteration in C++ und Vektorisierung in Python ist?
>
> Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist,
> egal in welcher Sprache.
Du gehst also davon aus, ohne beschreiben zu können, was es überhaupt 
ist.

Jan K. schrieb:
> Man muss also nicht explizit über alle Elemente iterieren, sondern
> operiert direkt auf Vektoren (oder auch Matrizen, geht aber im TO
> Beispiel nicht).
Du glaubst also, dass da im Hintergrund nicht iteriert wird? Ich 
verstehe das Argument nicht.

von Jan K. (jan_k)


Lesenswert?

mh schrieb:
> Du glaubst also, dass da im Hintergrund nicht iteriert wird? Ich
> verstehe das Argument nicht.

Aus Anwenderperspektive nicht. Im Hintergrund hängt es von der konkreten 
Implementierung ab, wie ich in dem anderen Post schrieb, gehe ich aber 
durchaus davon aus, dass da auch Vektor Instruktionen der CPU zu trage 
kommen. Weiß aber noch nicht wann und in welchem Ausmaß.

Als Hinweis für dich, ich glaube, dass vektorisieren je nach Kontext 
unterschiedlich interpretiert wird. Und hier möglicherweise zwei Welten 
aufeinander prallen. Im Falle von Matlab und Python (beide kommen aus 
dem wissenschaftlichen Rechnen) ist es so wie ich oben schrieb. Und es 
wird so auch in gängiger Literatur zu den Programmen propagiert. Was Low 
level passiert steht auf nem anderen Blatt.

von mh (Gast)


Lesenswert?

Jan K. schrieb:
> Als Hinweis für dich
Ich hätte es vielleicht dazuschreiben sollen, ich bin mir bewusst, wie 
numpy (ich gehe davon aus wenn du python schreibst meinst du numpy oder 
pandas) funktioniert. Ich arbeite jeden Tag damit. Was ich nicht 
verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy 
oder matlab schneller machen soll als C oder C++.

von Sven B. (scummos)


Lesenswert?

mh schrieb:
> Was ich nicht
> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
> oder matlab schneller machen soll als C oder C++.

Schneller nicht, aber unter Umständen "nicht langsamer".

von mh (Gast)


Lesenswert?

Sven B. schrieb:
> mh schrieb:
>> Was ich nicht
>> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
>> oder matlab schneller machen soll als C oder C++.
>
> Schneller nicht, aber unter Umständen "nicht langsamer".
Das ist immer noch sehr optimistisch ;-). Ich habe es bis jetzt noch 
nicht erlebt, dass für realistische Aufgaben numpy an C oder C++ 
herankommt. Mladen G. glaubt aber, dass pandas schneller sein kann:
Mladen G. schrieb:
> Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und
> Vektorisierung in Python/Pandas darzustellen, denn damit haette
> Python/pandas eine echte Chance schneller zu sein, theoretisch.

von Jan K. (jan_k)


Lesenswert?

mh schrieb:
> Jan K. schrieb:
>> Als Hinweis für dich
> Ich hätte es vielleicht dazuschreiben sollen, ich bin mir bewusst, wie
> numpy (ich gehe davon aus wenn du python schreibst meinst du numpy oder
> pandas) funktioniert. Ich arbeite jeden Tag damit. Was ich nicht
> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
> oder matlab schneller machen soll als C oder C++.

Okay :) ja ich meine numpy/Pandas.

Gibt es echt keine Fälle, wo das sein kann? Optimieren Standard C (GCC, 
clang) compiler z.B. enge Schleifen, Skalarprodukte, Linearkombination 
und so direkt zu SIMD Instruktionen?
Zumindest ML (und numpy mit Sicherheit auch) tun das wohl 
https://stackoverflow.com/questions/45770057/how-does-vectorization-in-matlab-work

von mh (Gast)


Lesenswert?

Jan K. schrieb:
> Gibt es echt keine Fälle, wo das sein kann?
Keine Fälle würde ich nicht sagen. Aber wenn in numpy und in C++ die 
gleiche Arbeit verrichtet wird, ist C++ sehr sehr sehr Wahrscheinlich 
schneller. Wenn in numpy weniger Arbeit verrichtet wird, weil ein besser 
Algo verwendet wird, ist es kein fairer Vergleich. An dieser Stelle 
liegt der Vorteil von numpy. Es ist wahrscheinlich, dass man einen 
akzeptabel optimierten Algo in numpy oder scipy findet.

> Optimieren Standard C (GCC,
> clang) compiler z.B. enge Schleifen, Skalarprodukte, Linearkombination
> und so direkt zu SIMD Instruktionen?
Das kommt drauf an. Schleifen ja, das ist allerdings nicht perfekt. 
Skalarprodukte, Linearkombinationen und ähnliches wird bei numpy und 
vermutlich Matlab von BLAS erledigt, einer Lib, die in C oder Fortran 
geschrieben ist.

von Sven B. (scummos)


Lesenswert?

Jan K. schrieb:
> Gibt es echt keine Fälle, wo das sein kann?

numpy ist ja in C/Fortran geschrieben. Klar kannst du C-Code schreiben, 
der langsamer ist, aber es wird offensichtlich für jeden Anwendungsfall 
möglich sein, C-Code zu schreiben, der gleich schnell oder schneller 
ist.

von Schnittstelle (Gast)


Lesenswert?

Sven B. schrieb:
> numpy ist ja in C/Fortran geschrieben.

Darum verstehe ich nicht wie hier C mit "Python" verglichen wird ;-)

Genauso wie bei Rust: Rust ist mindestens genauso schnell wie C/C++ bla, 
bla, bla!

Tja, wenn Rust LLVM (also die gleichen Optimierungen)  benutzt....

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

OK, angebissen. Hat jemand eine Erklärung dafür, dass der Python code 
(s.o.) im Gegensatz zu den obigen Ergebnissen bei mir nahezu *doppelt so 
schnell* ist wie der originale C++ code (0.42s vs 0.82s)? (Linux Mint 
20.1, Python 3.8.5, gcc 9.3.0). Kann das jemand unter Linux bestätigen?

Die Ausgabe habe ich natürlich verglichen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.