Funktion zum Zusammenfassen der firsts von gleichen seconds (std::pair) arbeitet nicht immer



  • Huhu,

    folgende Funktion:

    void sum_coeff(vector<pair<double, double>> &pValues)
    {
    	vector<pair<double, double>>::iterator i;
    	vector<pair<double, double>> nVec;
    
    	for(i = pValues.begin(); i != pValues.end(); ++i)
    	{
    		// aktuelle Potenz abspeichern
    		double cur_pot = i->second;
    		// der dazugehörige Koeffizient
    		double tmp = i->first;
    		double tmp2 = i->first;
    
    		// temporäre pairs, die später in nVec geschrieben werden
    		pair<double, double> tmp_p;
    
    		// davon hängt ab, ob von der endsumme noch der startwert abgezogen wird, falls die potenz nur einmal vorkommt
    		bool found = false;
    
    		decltype(i) j = i+1;
    
    		for(j; j != pValues.end(); ++j)
    		{
    			// vergleich der potenzen
    			if(cur_pot == j->second)
    			{
    				// wenn gleich, wird der koeffizient draufgerechnet
    				tmp += j->first;
    
    				found = true;
    
    				// dieser koeffizient muss gelöscht werden
    				pValues.erase(j);
    
    				// wieder alles auf anfang, sonst gibts speicherüberlauf-fehler
    				j = pValues.begin();
    				i = pValues.begin();
    			}
    		}
    
    		tmp_p.first = (found) ? tmp-tmp2 : tmp;
    		tmp_p.second = cur_pot;
    
    		nVec.push_back(tmp_p);
    	}
    
    	pValues = nVec;
    }
    

    Was gemacht werden soll:

    Als Argument erhält die Funktion einen Verweis auf einen vector<pair<double, double>>, der in den firsts Koeffizienten enthält, und in den seconds dazugehörige Potenzen.

    Der Sinn der Funktion ist nun, den vector nach gleichen Potenzen zu durchsuchen, deren Koeffizienten zu addieren und mit der dazugehörigen Potenz in einen neuen vector nVec zu schreiben. Anschließend wird der eingegeben vector mit nVec überschrieben.

    Problem ist nun, dass es mal funktioniert, mal nicht. Mal werden die Koeffizienten korrekt in den neuen vector geschrieben, mal wird eine Potenz ausgelassen, mal wird falsch addiert. Wovon das abhängt weiss ich nicht. Offenbar wird irgendwo etwas zu früh rausgelöscht, aber selbst Einzelschritte im Debugger bringen mich da nicht weiter..

    Hat da jemand eine Idee?

    Vielen Dank, 🙂

    Ceriana



  • Radeon schrieb:

    Der Sinn der Funktion ist nun, den vector nach gleichen Potenzen zu durchsuchen, deren Koeffizienten zu addieren und mit der dazugehörigen Potenz in einen neuen vector nVec zu schreiben. Anschließend wird der eingegeben vector mit nVec überschrieben.

    Anderer Ansatz: Sortiere deinen Vektor nach der Potenz, dann sind gleiche Potenzen aufeinanderfolgend und du kannst die Koeffizienten solange addieren, wie die Potenzen stimmen.

    Das ist schneller, statt O(n²) nur noch O(n·log(n)), und ausserdem kürzer.

    struct sort_second {
      template <typename LHS, typename RHS>
      bool operator()(LHS const& lhs, RHS const& rhs)
      { return lhs.second < rhs.second; }
    };
    
    void sum_coeff(vector<pair<double, double>> &terms)
    {
      sort(terms.begin(), terms.end(), sort_second());
    
      auto in = terms.begin(), out = terms.begin(), end = terms.end();
      for (; in != end; ++out) {
        *out = *in;
        while ((++in)->second == out->second)
          out->first += in->first;
      }
    
      terms.erase(out, end);
    }
    


  • Double auf Gleichheit zu prüfen hat öfters merkwürdige Effekte.


  • Mod

    for (; in != end; ...) {
    ...
        while ((++in)->second == out->second)
          ...
      }
    

    ob das wohl gutgeht?



  • @Firepro: Dankeschön, das funktioniert super 🙂

    @manni66 und @camper: Ich denke, eure Einwände hängen zusammen. Welches Problem seht ihr?



  • Radeon schrieb:

    @Firepro: Dankeschön, das funktioniert super 🙂

    Nein, es funktioniert nicht. In der while-Schleife muss noch überprüft werden, ob ++it == end, bevor it dereferenziert wird.
    Alternativ kann NAN gepushbackt werden und end = end()-1 gesetzt werden, dann macht man die Schleife etwas schneller.

    Den Fix überlasse ich dir.


  • Mod

    Radeon schrieb:

    @manni66 und @camper: Ich denke, eure Einwände hängen zusammen.

    Ich glaube nicht. Meine Kritik richtet sich gegen die Art und weise, wie der Iterator verwendet wird (wenn die Schleife terminiert, dann ist das bloss Zuafll und in jedem Fall UB, da end-Iteratoren typischerweise nicht dereferenziert werden dürfen).

    if ( in != end )
          ++in;
      for (; in != end; ++in)
          if ( in->second == out->second )
              out->first += in->first;
          else
              ++out = *in;
    


  • #include <iostream>
    
    int main()
    {
      double a = 69.82;
      double b = 69.2 + 0.62;
      if( a == b ) std::cout << "gleich\n";
      else std::cout << "ungleich\n";
    }
    

    gibt "ungleich" aus. Wären die beiden Zahlen in deinem Container, würden sie "falsch" ausgewertet.


Log in to reply