Wer sieht hier Optimierungspotential (Nullstellen finden)



  • Hallo,

    ich habe einen Vektor ('vektor'), der Messdaten enthält: etwa 1,6 Mio. Einträge.
    Die Messwerte verlaufen des öfteren vom positiven Bereich in den negativen und umgekehrt. Ich möchte nun die Vektoreinträge identifizieren, an denen eine solche Nullstelle vorliegt. Bisher benutze ich dafür den folgenden C++ Code:

    [code]for i = 1 :(length(vektor)-1)
     if (vektor(i) == 0)
       nullstelle(z) = i;
       z = z+1;
     elseif ((vektor(i) < 0) & (vektor(i+1) > 0))
       nullstelle(z) = i;
       z = z+1;
     elseif ((vektor(i) > 0) & (vektor(i+1) < 0))
       nullstelle(z) = i;
       z = z+1;
     end;
    end;[/code]
    

    Das ganze funktioniert auch, dauert nur extrem lange (ca. 20 Minuten). Gibt es eine Möglichkeit meinen Code zu optimieren bzw. die Nullstellen irgendwie anders schneller zu finden?

    Grüße
    Timo



  • Was ist n das für ne sprache?



  • Matlab?



  • Oh, ja... habe das ganze in MatLab programmiert.
    Ich dachte das würde auf C++ basieren.

    Naja, aber im Prinzip ja ähnlich, oder?
    Sieht jemand (von mir aus auch in C++) Optimierungsansätze?



  • Das hat mit C++ überhaupt nichts zu tun. Optimierungen in Matlab laufen gewöhnlich darüber, dass man Code vektorisiert. Mehr als find(sign(vector(1:end-1)) ~= sign(vector(2:end))) ist mir noch nicht eingefallen, da fehlen noch die direkten Nullstellen, die keine Vorzeichenwechsel sind. Und ob die Indizes genauso rauskommen wie bei dir weiß ich auch nicht. Es läuft aber (2 Millionen Datenpunkte per Zufall erzeugt) in unter einer Sekunde bei mir...
    Du hast wahrscheinlich aber nullstellen nicht vorher alloziert, so dass der Vektor bei jeder gefundenen Nullstelle vergrößert werden muss? Das kostet auch massig.



  • eventuell ist das schneller:

    for i = 1 :(length(vektor)-1)
     if (vektor(i) * vektor(i+1) < 0 || vektor(i) == 0)
       nullstelle(z) = i;
       z = z+1;
     end;
    end;
    

    Bei Nullstelle ändert sich das vorzeichen -> produkt ist negativ. btw, matlab ist da nicht gerade das schnellste für, das dauert halt seine zeit. Vielleicht kannst du eine matlab-extension schreiben, die das ganze in c++ realisiert und in matlab aufgerufen wird. (z.B. mit SWIG)



  • Hab das mal mit C++ versucht. Braucht im Release Modus nicht mal ne Sekunde.

    const size_t num = 1600000;
    	size_t z=0;
    
    	std::vector<double> data(num);
    	std::vector<double> nullstelle(num);
    
    	//mit zufallswerten füllen
    	for(size_t i=0; i<num;i++) {
    		data[i]=static_cast<double>(rand()-rand())/(rand()+1);
    	}
    
    	for(size_t i=0; i<num-1;i++) {
    		if( data[i]==0 || (data[i]<0 && data[i+1]>0) || (data[i]>0 && data[i+1]<0) )
    			nullstelle[z++]=i;
    	}
    


  • Bashar schrieb:

    Optimierungen in Matlab laufen gewöhnlich darüber, dass man Code vektorisiert. Mehr als find(sign(vector(1:end-1)) ~= sign(vector(2:end))) ist mir noch nicht eingefallen, da fehlen noch die direkten Nullstellen, die keine Vorzeichenwechsel sind.

    Jep, das war der Tipp den ich brauchte! 🙂
    Der folgende Code läuft unter MatLab und benötigt kein C/C++

    ------------------------------------------------------------

    null_1 = find(sign(vektor(1:end-1)) ~= sign(vektor(2:end)));
    null_2 = find(vektor==0);
    
    nullstellen=[null_1 null_2];
    

    ------------------------------------------------------------

    Hat bei mir dann nur noch 0,9 sec. benötigt. Wie ihr schon gesagt habt, ist MatLab nur bei vektorisierter Schreibweise schnell... das mit der FOR- Schleife und der IF-Abfrage dauert ewig unter Matlab.

    Vielen Dank aber auch für alle anderen Tipps! Mir ist jetzt einiges klarer geworden in Bezug auf MatLab, vektorisierter Schreibweise und C++.

    ➡ Danke!



  • Dieser Ausdruck findet leider auch Übergänge von 0 auf positiv oder negativ und zurück, also war die Verwendung von sign wohl ein Schnellschuss. Besser so:

    find(v(1:end-1) < 0 & v(2:end) > 0 | v(1:end-1) > 0 & v(2:end) < 0);
    

    (was ja auch die Logik ist, die du vorher hattest)



  • Bashar schrieb:

    Besser so:

    find(v(1:end-1) < 0 & v(2:end) > 0 | v(1:end-1) > 0 & v(2:end) < 0);
    

    (was ja auch die Logik ist, die du vorher hattest)

    Jep, jetzt ist es perfekt.
    Vielen Dank!


Log in to reply