Matrix Addition effizient mit Sparse

Braunstein

Hallo,

Vielleicht kannst du auch mal hier reinschauen
Komponenten entwerfen mit der C++ STL, Ulrich Breymann
Komponenten entwerfen mit der C++ STL | ISBN: 3827314747
Kapitel 9.4 beschäftigt sich mit dünn besetzten Matrizen.

bucada

Könnte mir jemand diesen Ausdruck erklären?

map<int,double> *s;

Wie genau werde die Elemente dort gespeichert?

CStoll

Das ist ein Zeiger auf eine map, die irgendwo im Speicher liegt - in der map werden die Objekte als Binärbaum aus pair<const int,double> (sortiert nach den "const int"-Anteil) verwaltet.

bucada

Ja, soweit ist das klar, doch wie kommen hier die Zeilen und Spalten der Matrizen rein?

CStoll

Du initialisierst das mit "s=new map<...>[n];" im Konstruktor - d.h. der Zeiger verweist auf ein Array von n einzelnen map's (vermutlich eine pro Matrixzeile).

Jester

Neku schrieb:

Lohnt sich das wirklich?
Das dürfte doch nur effektiv sein, wenn man wirklich oft viele Nullen hat? Das Suchen nach Nullen bzw. das Zuordnen der Werte zu Zeilen/Spalten dürfte doch mehr Rechenzeit verbrauchen, als das Rechnen?

Stell Dir vor, Du hast ne 1000x1000-Matrix und da sind nur 5000 Werte ungleich 0 drin. Da ist es schon allein vom Speicher her effizienter, lieber die Zahlen ungleich 0 und wo sie stehen zu speichern, als trotzdem alle Zahlen aufzulisten. Und bei Rechenoperationen sparste auch nochmal ne ganze Menge.

Neku

Jester schrieb:

Neku schrieb:

Lohnt sich das wirklich?
Das dürfte doch nur effektiv sein, wenn man wirklich oft viele Nullen hat? Das Suchen nach Nullen bzw. das Zuordnen der Werte zu Zeilen/Spalten dürfte doch mehr Rechenzeit verbrauchen, als das Rechnen?

Stell Dir vor, Du hast ne 1000x1000-Matrix und da sind nur 5000 Werte ungleich 0 drin. Da ist es schon allein vom Speicher her effizienter, lieber die Zahlen ungleich 0 und wo sie stehen zu speichern, als trotzdem alle Zahlen aufzulisten. Und bei Rechenoperationen sparste auch nochmal ne ganze Menge.

An so große Matrizen habe ich gar nicht gedacht. Wozu braucht man die?

*mal rechnet*

Matrix: 1000x1000
Typ: double (~ 8 Byte)
Positionsspeicher: 2 ushort (x und y, ~ je 2 Byte)
Anzahl Elemente: uint (~ 4 Byte)

Normal: 1000 * 1000 * 8 = 8.000.000 Byte
Sparse (5000 Elemente != 0): 5000 * (8 + 4) + 4 = 60.004 Byte
Sparse (5000 Elemente == 0): 995.000 * (8 + 4) + 4 = 11.940.004 Byte

Stimmt, bis zu 666.666 Elementen != 0 (schöne Zahl :)) ist Sparse hier effizienter.

camper

den overhead von nodebasierten containern wie map sollte man dann aber nicht unterschlagen da map typischerweise auf einem red-black tree basiert, macht das zwei zeiger pro node, also nochmal jeweils 8 byte extra bei 32bit architektur. pi mal daumen würde ich schätzen, dass sich das ganze lohnt (bzgl. speicherplaz und rechenaufwand) wenn weniger als 10% der matrix besetzt sind. für richtige große matrizen ist eine unordered_map wahrscheinlich noch günstiger - eine hashfunktion dafür ist ja recht trivial.

CStoll schrieb:

Du initialisierst das mit "s=new map<...>[n];" im Konstruktor - d.h. der Zeiger verweist auf ein Array von n einzelnen map's (vermutlich eine pro Matrixzeile).

das macht wenig sinn. eine einzige map genügt, z.b. per:

struct Pos { unsigned short x,y; };
map<Pos,double> s;

mit geeignetem prädikat, oder man bildet gleich auf unsigneds ab per: index = zeile * spaltenzahl + spalte, was im grunde nichts anderes ist.

Werner Salomon

camper schrieb:

... oder man bildet gleich auf unsigneds ab per: index = zeile * spaltenzahl + spalte, was im grunde nichts anderes ist.

genau das würde ich auch vorschlagen. Weiter würde ich bucada empfehlen, keine Pointer als Member zu nutzen sondern die STL-Container unmittelbar zu aggregieren. Das spart viel Arbeit und verkleinert die Fehlerwahrscheinlichkeit.

Eine weitere Vereinfachung ist es statt eines

Sparse* operator+ (const Sparse& A) const;

lieber einen

Sparse& operator+=( const Sparse& A ) const;

zu schreiben und den fehlenden operator+ dann so zu erzeugen

Sparse operator+( Sparse a, const Sparse& b )
{
    return a += b;
}

Aus der Klasse Sparse wird dann etwa:

#include <cassert>
#include <iostream>
#include <iomanip>
#include <map>

class Sparse
{
public:
    typedef std::size_t size_type;

    Sparse( size_type zeilen, size_type spalten )
        : m_nZeilen( zeilen )
        , m_nSpalten( spalten )
    {}

    Sparse& operator+=( const Sparse& b )
    {
        assert( m_nZeilen == b.m_nZeilen );
        assert( m_nSpalten == b.m_nSpalten );
        std::map< size_type, double >::const_iterator i2 = b.m_data.begin();
        for( std::map< size_type, double >::iterator i1 = m_data.begin(), j = i1
            ; i1 != m_data.end() && i2 != b.m_data.end(); )
        {
            if( i1->first < i2->first )
                ++i1;   // b[i2] == 0, *i1 übernehmen
            else if( i1->first == i2->first )
            {
                // beide Werte sind != 0 -> also addieren
                i1->second += i2->second;
                ++i1;
                ++i2;
            }
            else // i2->first < i1->first
            {
                // *i1 == 0, *i2 übernehmen
                j = m_data.insert( j, *i2 );
                ++i2;
            }
        }
        m_data.insert( i2, b.m_data.end() );    // Rest hinzufügen
        return *this;
    }

private:
    size_type m_nZeilen;
    size_type m_nSpalten;
    std::map< size_type, double > m_data;
};

Gruß
Werner

Werner Salomon

Neku schrieb:

An so große Matrizen habe ich gar nicht gedacht. Wozu braucht man die?

Zum Beispiel hier für. Bei mittleren Problemen erhält man lineare Gleichungssysteme mit Matrizen von mehreren Tausend Elementen Kantenlänge. Dabei sind weniger als 1% der Werte != 0.

Gruß
Werner