Problem mit algo

Hi

Häng hier fest, der algo rennt ewig durch die Schlaufe, find aber nicht raus wieso

struct EqualSymbol
:   public std::binary_function<Fraction, std::string, bool>
{
    bool operator()( const Fraction& lhs, const std::string& rhs ) const
    {
        return lhs.m_symbol == rhs;
    }
};

//
        bool do_it = true;
        for( FractionTableT::iterator it = ret.begin();
        it != ret.end(); it++ )
        {
            if( it->m_symbol == "NNN" )
            {
                do_it = false;
            }
            while( do_it )
            {
                FractionTableT::iterator findit 
                    = find_if( ret.begin(), ret.end(), 
                        bind2nd( EqualSymbol(), it->m_symbol ) );
                if( findit == ret.end() )
                {
                    do_it = false;
                }
                it->m_coeff *= findit->m_coeff;
                findit->m_symbol = "NNN";
            }
        }

Kann mir jemand helfen?

Danke

Werner Salomon

Schon beim ersten Durchlauf wird ein Eintrag mit 'it->m_symbol' gefunden, nämlich wenn it und findit gleich sind, dieser wird selbst (!) auf "NNN" gesetzt. Bei jedem nächsten Durchlauf in der while-Schleife wird der gleiche Eintrag von "NNN" gefunden und jetzt bleibt die while-Schleife kleben, da hier immer wieder der gleiche "NNN"-Eintrag gefunden wird.

Ich glaube, das was Du willst ist das (an Stelle der Zeilen 15-30)

if( it->m_symbol == "NNN" )
            {
                continue;
            }
            for( FractionTableT::iterator findit = it + 1 // hinter it beginnen
                ; (findit = std::find_if( 
                        findit, ret.end(),  // erst ab 'findit' weitersuchen
                        bind2nd( EqualSymbol(), it->m_symbol ) )
                  ) != ret.end(); ++findit )
            {
                it->m_coeff *= findit->m_coeff;
                findit->m_symbol = "NNN";
            }

Gruß
Werner

Danke.

Hab nun mein Code entsprechend umgebaut

struct EqualSymbol
:   public std::binary_function<Fraction, std::string, bool>
{
    bool operator()( const Fraction& lhs, const std::string& rhs ) const
    {
        return ( 0 == lhs.m_symbol.compare( rhs ) );
    }
};

struct IsDummy
:   public std::unary_function<Fraction, bool>
{
    bool operator()( const Fraction& elem ) const
    {
        return ( 0 == elem.m_symbol.compare( "NNN" ) );
    }
};

//...

for( FractionTableT::iterator it = ret.begin();
     it != ret.end(); it++ )
{
    if( 0 == it->m_symbol.compare( "NNN" ) )
        break;
    for( FractionTableT::iterator it2 = it + 1;
         it2 != ret.end(); it2++ )
    {
        FractionTableT::iterator findit 
            = find_if( ret.begin(), ret.end(),
                       bind2nd( EqualSymbol(), it->m_symbol ) );
        if( findit == ret.end() || findit == it )
            break;
        it->m_coeff += findit->m_coeff;
        findit->m_symbol = "NNN";
        }
}
ret.erase( std::remove_if( ret.begin(), ret.end(), IsDummy() ),
            ret.end() );        // alle mit "NNN" entfernen

Tut nun auch was er soll, aber kann man das noch optimieren oder 'verschönern'?

ceplusplus

Jetzt ist er zumindest mal vernünftig lesbar:

struct EqualSymbol : public std::binary_function<Fraction, std::string, bool> 
{ 
    bool operator() (const Fraction& lhs, const std::string& rhs) const 
    { 
        return (0 == lhs.m_symbol.compare(rhs)); 
    } 
}; 

struct IsDummy : public std::unary_function<Fraction, bool> 
{ 
    bool operator() (const Fraction& elem) const 
    { 
        return (0 == elem.m_symbol.compare("NNN")); 
    } 
}; 

for(FractionTableT::iterator it = ret.begin(); it != ret.end(); it++) 
{ 
    if(0 == it->m_symbol.compare("NNN"))
		break; 

    for(FractionTableT::iterator it2 = it + 1; it2 != ret.end(); it2++) 
    { 
        FractionTableT::iterator findit = find_if(ret.begin(), ret.end(), bind2nd(EqualSymbol(), it->m_symbol));

        if(findit == ret.end() || findit == it) 
            break; 

        it->m_coeff += findit->m_coeff; 
        findit->m_symbol = "NNN"; 
    } 
} 

ret.erase(std::remove_if(ret.begin(), ret.end(), IsDummy()), ret.end());

Werner Salomon

Evil Knevil schrieb:

Tut nun auch was er soll, aber kann man das noch optimieren oder 'verschönern'?

Ja. Dein Algo hat die Komplexität O(n^2). Das kann bei einem n - also der Anzahl der Elemente in dem Container - von ein paar 100 aufwärts irgendwann zum Problem werden. Wenn es ok ist, die Elemente in einer anderen Reihenfolge zu erzeugen, so sollte man sie vorher nach 'm_symbol' sortieren. Das hat bei den üblichen Algorithmen die Komplexität O(n*log(n)); das wäre noch ok.
Weiter braucht man die Elemente nicht erst markieren und danach wegwerfen, sondern kann das gleich in einem Aufwasch tun. In Kombination mit einer Output-Iterator-Schnittstelle für die Ausgabe wird es auch recht flexibel.

Alles zusammen könnte das so aussehen:

struct LessFraction
{
    bool operator()( const Fraction& a, const Fraction& b ) const
    {
        return a.m_symbol < b.m_symbol;
    }
};

template< typename OutItr >
void mach( const FractionTableT& table, OutItr out )
{
    FractionTableT ret = table; // lokale Kopy - nur wenn notwendig
    FractionTableT::iterator first = ret.begin();
    FractionTableT::iterator last = ret.end();

    if( first == last )
        return;
    sort( first, last, LessFraction() ); // erst sortieren, sonst funkt die Schleife nicht
    FractionTableT::iterator it = first;
    for( ; ++first != last; )
        if( it->m_symbol == first->m_symbol )
            it->m_coeff *= first->m_coeff;
        else
        {
            *out++ = *it;
            it = first;
        }
    *out++ = *it;   // letzten auch wegschreiben
    return;
}

aufrufen kann man das dann mit

mach( table, ostream_iterator< Fraction >( cout << "> ", " " ) );

wenn man nur eine Ausgabe haben will oder mit back_inserter, um sie in den Zielcontainer zu stecken.

Gruß
Werner

PS.: warum denn das einfache & klare 'it->m_symbol == "NNN"' gegen das hässliche '0 == it->m_symbol.compare("NNN")' austauschen?

Hi

Danke Werner, für die Erklärung und den Code.

PS.: warum denn das einfache & klare 'it->m_symbol == "NNN"' gegen das hässliche '0 == it->m_symbol.compare("NNN")' austauschen?

Hatte immer wieder Fehler und darum verschiedenes ausprobiert. Kommt wieder weg.

Ich versteh eine Zeile nicht, in dem Code:

*out++ = *it;

Was tut die genau?

Und auf was zeigt out am Ende?
Und wie krieg ich nun nur die zusammengerechneten Fractionen raus? Also nur eine je Symbol?

Danke nochmal