più efficiente radi elemento della matrice di accesso

Question

ho scritto una piccola classe matrice sparsa con gli Stati:

std::map<int,std::map<int,double> > sm;

Il seguente metodo è la funzione che utilizzo per accedere agli elementi di una matrice, se non è possibile tramite un iteratore:

double matrix::operator()(int r,int c) const
{
    std::map<int,std::map<int,double> >::const_iterator i = sm.find(r);
    if(i==sm.end()) { return 0.0; }
    std::map<int,double>::const_iterator j = i->second.find(c);
    if(j==i->second.end()) { return 0.0; }
    return j->second;
}

Ancora questa funzione ha bisogno di ottenere chiamato molto spesso. Ha idea di qualcuno di come migliorare questa funzione? Grazie in anticipo.

Answer 1

Se si sta per scrivere il proprio codice anziché utilizzare una libreria, allora questo cambiamento può migliorare le prestazioni in modo drammatico:

std::map<std::pair<int,int>, double> sm;

Per aumentare più lontano si può andare a contenitori hash:

std::unordered_map<std::pair<int,int>, double> sm;

(uso TR1, esaltazione o C ++ 0x)

EDIT: nel primo caso è possibile iterare su row in questo modo:

for(auto& cell : make_pair(
    sm.lower_bound(make_pair(row, 0)), sm.lower_bound(make_pair(row+1, 0))))
{ ... }

Credo che si può fare quanto sopra da una chiamata a equal_range con un funtore appropriato se si utilizza Boost.MultiIndex.

su tutto:

for(auto& cell : sm)
{ ... }

per iterare su una colonna è necessario cercare per ogni cella separatamente. Si noti che il vostro datastructure non fornisce questa operazione sia.

Answer 2

probabilmente stai andando ad odiare questo, ma per il seguente (piccolo per la visualizzazione) riga di una matrice:

1 0 0 5 9 0 0 0

si potrebbe avere una matrice di bit (8 bit in questo caso) dove per ogni bit è stato impostato o azzerato per riflettere se c'era un non-zero o zero in quella posizione nella matrice.

Poi basta memorizzare i non-zero numeri in un array regolari imballati insieme come:

{ 1, 5, 9 }

e le bandiere binari

0x98 // binario 1001 1000

E per scorrere la riga di matrice si sarebbe solo utilizzare le operazioni di bit per scorrere l'array bit:

while (! /* not at the end of the bit array */ ) {
    f = get_next_from_bit_array();  // This is just bitwise shift and bitwise & 
    if (!f) {
       val = 0;
    } else {
       val = compressed_row[i];
       i++;
    }
    do_action(val);
}

Il mio codice qui è solo per dimostrazione e non è molto C ++, ma spero si può ottenere l'idea.

Uso della matrice di bit vi permetterà di esaminare un'area molto più piccola della memoria per le righe sparse, il che significa un minor numero di accessi alla memoria e una migliore località della cache.

Se le matrici si sta lavorando sono estremamente scarse, allora si potrebbe estendere questo per l'altra dimensione e (avendo matrice sparsa di righe), ma la possibilità di avere intere righe vuote è probabilmente bassa.