Newsgroup: it.comp.lang.c++
Titolo: Ancora sule matrici

Salve,
vorrei un consiglio.
ho una matrice 
MiaMat[1000][1000];
che è tutta vuota tranne che per alcune posizioni e vorrei cancellarla
senza doverla scorrere tutta ovviamente.
Come si può fare senza sapere dove è scritta e dove no?
Grazie,
Mic


memset ((void*)MiaMat,0,sizeof(tipovariabile)*matrice1*matrice)
non ho controllato spero di non aver fattoerrori ciao :)
--
-------
sito: 
www.dadev.it
ultime: Ocx per irc testi freeware
-------

 non ho controllato spero di non aver fattoerrori ciao :)
L'OP non ha specificato il tipo di dato, ma se si tratta di una classe
con distruttore usare memset non e' molto furbo. Ed in ogni caso la
matrice viene comunque scorsa tutta.
Ciao,
Nicola


Non c'e' modo, a meno che tu non ti costruisca una struttura dati che
tenga traccia di quali sono le caselle occupate. Tieni presente che se
sai che la tua matrice e' sparsa (ovvero ha pochi elementi "pieni")
usare un array a due dimensioni non e' la rappresentazione migliore.
Potresti ad esempio usare una lista di righe dove ogni elemento contiene
l'indice della riga ed un puntatore alla lista degli elementi della
riga. Ogni elemento conterrebbe l'indice ed iol valore vero e proprio.
Ciao,
Nicola


Non funziona, la matrice viene riempita di un valore per tipovaribile
e non č vuota.
Mi spiego:
il definisco al matrice con Matrice[1000][1000] e poi scrivo qui e lě.
Con il metodo qui sopra mi ritrovo una matrice scritta tutta uguale!
Tipo variabile č una classe con una stringa, un int e un booleano.
Mic

 matrice viene comunque scorsa tutta.
scusa ma il memset non scorre la matrice ..
ma conoscendoti forse volevi dire altro.
ciao


riga. Ogni elemento conterrebbe l'indice ed iol valore vero e proprio.
I miei dati li tengo in un vettore. Per la rappresentazione grafica li
metto nella matrice e poi questa viene letta a pezzettini a seconda
dell'offset e con una finestra grande come quella di visualizzazione.
Quando carico un'altro vettore metto i suoi dati dentro la matrice, ma
se scrive in posti diversi, questa si ricorda ancora del vettore di
prima.
Ciao,
Mic


sinceramente mi è rimasta un po oscura la cosa cmq se la stringa è un
vettore costante e non un puntatore la cosa mi sembra possibile..
mi sto rendendo conto però che forse mi sfugge qualcosa ciao :))


mi sto rendendo conto perň che forse mi sfugge qualcosa ciao :))
Invece č un puntatore....:-(
e che č un OP?
Mic

 Invece è un puntatore....:-(
allora il tutto è impossibile devi scorrerre la matrice
ciao :)

Nicola
Cos'è un OP?
Mic

 ma conoscendoti forse volevi dire altro.
In termini di elementi no, in termini di byte che li compongono si.
Certamente non ha bisogno di *leggere* il valore degli elementi per
sovrascriverli.
Ciao,
Nicola

 Cos'è un OP?
Original Poster, ovvero chi ha inviato il messaggio che ha aperto il
nuovo thread.
Ciao,
Nicola

 sovrascriverli.
ma è ovvio questa scappatoia è fatta per eliminare il ciclo.Come saprai
benissimo è usatissime per mettere a 0 matrici di byte



Puoi usare una matrice sparsa, implementata per esempio con 
std::map< std::pair<unsigned, unsigned> , TuoTipo >
In questo modo soltanto i valori utilizzati vengono effettivamente
memorizzati. Per scorrere i soli elementi utilizzati puoi usare un
iterator.
Ho provato a realizzare una classe template sparse_mat<T> che implementi
tali funzionalita' e non nascondo di aver trovato qualche difficolta'.
Il primo problema che si incontra e' come accedere ai dati tramite gli
operatori [][].
Ad esempio dovrebbe poter essere possibile accedere ai dati con
mat[i][j];
Un' altro problema e' quello di inserire un elemento nella matrice
solo se questo viene scritto e non se viene letto.
Si tratta cioe' di distinguere tra letture e scritture dopo aver
applicato
due volte l'operatore [].
Ad esempio un semplice 
  a = mat[i][j];
non deve inserire il dato nella map ma un 
  mat[i][j] = a; 
deve poterlo fare. 
Non basta distinguere tra 
   operator[](int);
e 
   operator[](int) const;
Perche' se hai un instanza non const di matrice, viene sempre invocato
l'operatore non const, indipendentemente dall'uso che se ne vuole fare.
Alla fine e' uscita fuori una classe molto piu' lunga e complessa del 
previsto.
Se interessa a qualcuno posso postarne il codice.
Saluti,
Fabio
-- 
Posted from 
flopiano.mm.eutelsat.org
 [194.214.173.28] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 deve poterlo fare.
ho letto qualcosa a riguardo della composizione di operatori, tempo fa, 
e mi sembra che il problema venisse risolto col Proxy:
una cosa del tipo
template <typename T>
ProxySparseMat<T> SparseMat<T>::operator[](int index); 
e poi i vari tipi di operazione su questo proxy:
template <typename T>
const T& ProxySparseMat<T>::operator[](int index) const; 
che non inserisce, chiamata nel primo caso
e invece
template <typename T>
void ProxySparseMat<T>::operator[](int index); 
che lo fa, chiamata nel secondo.
Pero' potrei sbagliarmi, non mi ricordo dove l'ho letto e come si 
poneva il problema. 
A naso, mi sembra comunque questa la strada

 poneva il problema.
e infatti mi sbaglio perche' c'e' overloading sul tipo di ritorno...  
comunque, giocando sul proxy, dovresti risolvere la cosa

 A naso, mi sembra comunque questa la strada
In realta' ho dovuto usare tre classi proxy
gli operatori [] (const e non const) della matrice tornano una 
classe riga i cui operatori [] permettono di accedere al valore.
le tre classi proxi sono:
  una classe per la riga const il cui operatore [] torna un valore, 
  una classe per la riga non const il cui operatore [] torna un altra 
  classe proxy con operatore di assegnamento (che modifica la map) e un 
  operatore di conversione a T che torna l'elemento di default o quello
nella mappa.
Non so se si riesce a eliminarne una.
Fabio Lopiano


 benissimo h usatissime per mettere a 0 matrici di byte
In realtà il ciclo viene eseguito comunque, solo che viene fatto in maniera
diversa.
Comunque quello che conta e' questo: se hai una matrice di 100.000.000 di interi
(che se un intero e' di 4 byte significa oltre 380 Mb) da azzerare e hai un modo
per sapere che la maggior parte di questi byte sono gia' a zero e solo alcuni
(purche' siano veramente pochi e tu possa calcolarne la posizione) vanno di
fatto azzerati, spesso conviene azzerare solo questi calcolandone la posizione
anche se il calcolo e' complesso e apparentemente lungo piuttosto che azzerarla
con un memset. Il motivo e' semplice: scrivere 380Mb significa comunque spostare
380 Mb di dati dalla CPU alla memoria attraverso le varie cache e con buona
probabilità (anche su sitemi moderni) scrivere una parte di questi dati sul file
di swap dato che non tutte le macchine sono attrezzate con sufficiente memoria
da permettere ad un singolo processo di avere 380Mb di allocati in RAM.
Pero' e' evidente che il solo sapere che ce ne sono pochi da azzerare non basta
per poter sfruttare questa ottimizzazione: bisogna che siano disponibili anche
informazioni (dati e/o algoritmi) per calcolare QUALI sono quelli da azzerare
(ovviamente intendo dire che bisogna saperlo SENZA accedere alla matrice).
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 Cos'è un OP?
Niente paura: non ha nulla a che vedere con l'OT! Si tratta semplicemente
dell'Original Poster (nella fattispece sei tu l'OP di questo thread).



però un algoritmo del genere rallenterebbe di molto il codice.Sai dirmi su
che tipo di applicazione viene usato di solito ?Credo che sia interessante
ma che crei molti problemi
ciao


 ma che crei molti problemi
Mica vero. Anzi, l'idea e' proprio quella di velocizzarlo. Se lo "spazio logico"
e' molto ampio (ovvero la dimensione della matrice e' grande) mentre lo "spazio
fisico" e' piccolo (ovvero ci sono pochi elementi che non sono 0) e' molto
probabile che il poter calcolare le coordinate di quei pochi elementi e
accederci direttamente e' piu' veloce che non accedere a tutta la matrice.
In C++ poi, dove l'interfaccia vista dal codice che usa la matrice puo' essere
separata dall'implementazione, puoi scrivere codice che funziona
indipendentemente dal tipo di matrice sottostante e usare implementazioni delle
matrici sparse come quella proposta, se non erro, da Griffini.


 Non so se si riesce a eliminarne una.
penso che si possa fare anche con una sola, considera
il seguente esempio
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
template < typename  T>
class Matrix {
  typedef std::pair< int, T >  element;  // conservo coppie
  typedef vector< element >::iterator  it; //(indice,valore)
  const T              emptyT_;
  vector< element >    vec_;
  int mutable          row_, col_;
  int                  rows_, cols_;
  struct compare : binary_function <element, int, bool> {
    bool operator()( const element& e, const int& pos )
    { return pos < e.first; }
  };
public:
  Matrix( int rows, int cols, T empty)
  : rows_(rows), row_(rows), cols_(cols), emptyT_(empty) {  }
  Matrix& operator[]( int row_or_col ) {         // Subscript restituisce
    ( row_ == rows_ ? row_ : col_ ) = row_or_col;// reference a se stesso
    return *this;                                // cosi' puo' essere
  }                                              // chiamato due volte
  const T& operator=( const T& valueT ) {   // Assegnamento
    int index = col_ + row_ * cols_;
    it  iter = vec_.begin();
    row_ = rows_;
    if ( vec_.size() ) {
      iter = lower_bound( vec_.begin(), vec_.end(), index , compare() );
      if ( iter != vec_.end() && index == iter->first )
        return iter->second = valueT;
    }
    vec_.insert( iter, element( index, valueT ) );
    return valueT;
  }
  operator const T( ) {                 // Conversione
    int index = col_ + row_ * cols_;
    row_ = rows_;
    if ( vec_.size() ) {
      it iter = lower_bound( vec_.begin(), vec_.end(), index , compare() );
 return(iter != vec_.end() && index == iter->first)? iter->second: emptyT_;
    }
    return emptyT_;
  }
  int size() { return vec_.size(); }
};
int main() {
  Matrix< double >  a( 5, 5, 0.0 );
  int               i,j;
  double d = a[1][3]; // lettura elemento vuoto in matrice vuota
  cout.setf(ios::fixed,ios::floatfield); // avrei usato cout << fixed
  cout.precision(2);                     // ma gcc 2.95 non gradisce
  cout << "a[1][3] = " << setw(7) << d << '\n';
  for ( i=0; i<5; ++i )
    a[i][i] = 15.3 - i;
  a[2][2] = 22.0; // scrivo su un elemento gia' nella Matrice
  a[3][2] = 32.0; // scrivo su elemento intermedio non nella Matrice
  d = a[1][3]; // lettura elemento vuoto
  cout << "a[1][3] = " << setw(7) << d << '\n';
  d = a[2][2]; // lettura elemento 'pieno'
  cout << "a[2][2] = " << setw(7) << d << '\n';
  cout << "\nElementi nel vettore interno: " << a.size() << '\n';
  for ( i=0; i<5; ++i ) {
    cout << '\n';
    for ( j=0; j<5; ++j )
      cout << setw(7) << (double) a[i][j] << " ";
  }
  cout << "\nElementi nel vettore interno: " << a.size() << '\n';
  cin.get();
  return 0;
}
--
ciao
Massimo

   int                  rows_, cols_;
Complimenti per la scelta dei nomi dei membri...
W la leggibilità!!!
-- 
Luc.

 Massimo
Comunque, ho allegato la mia versione
Saluti,
Fabio
------8<----------------- cut here ---------- 8<-----------
#include <iostream>
#include <map>
template <class T>
class sparse_mat
{
    typedef std::pair< unsigned, unsigned > coord_type;
    typedef std::map< coord_type, T > map_type;
    T  default_value;
    map_type the_map;
    template <class U>
    class sparse_item 
    {
       coord_type coords;
       map_type& map_ref;
       U   default_value;
    public:
       sparse_item(coord_type coords, 
                   map_type& map_ref,
                   const U &def_val) :
          coords(coords),
          map_ref(map_ref), 
          default_value(def_val) {}
       U& operator=(const U& val)
       {
          return (map_ref[ coords ] = val);
       }
 
       operator U() const
       {
          sparse_mat<U>::const_iterator it;
 
          it = map_ref.find(coords);
          if (it == map_ref.end())
          {
             return default_value;
          }  
          return (*it).second;
       }
    };
    template <class U>
    class sparse_row
    {
        int row;
        map_type & map_ref;     
        U default_value;        
     public:
        sparse_row(unsigned a_row,
                   map_type & a_map_ref,
                   const U & def_val) : 
        row(a_row),
        map_ref(a_map_ref),
        default_value(def_val) {}     
        sparse_item<U> operator[] (unsigned col) 
        {
                return sparse_item<U> (std::make_pair(row,col),
                                       map_ref, default_value);
        }
    };    template <class U>
    class const_sparse_row
    {
        int row;
        const map_type & map_ref;       
        U default_value;        
     public:
        const_sparse_row(unsigned a_row,
                         const map_type & a_map_ref,
                         const U & def_val) : 
           row(a_row),
           map_ref(a_map_ref),
           default_value(def_val) {}     
        U operator[] (unsigned col) const
        {
                coord_type coords = std::make_pair( row,col );
                map_type::const_iterator it = map_ref.find( coords );
                if ( it == map_ref.end() )
                {
                        return default_value;
                }
                else
                {
                        return (*it).second;
                }
        }
    };
public:
    typedef std::pair< unsigned, unsigned > coord_type;
    typedef std::map< coord_type, T > map_type;
    typedef map_type::const_iterator const_iterator;
    typedef map_type::iterator       iterator;
 
    sparse_mat(T def_val=T()) : default_value(def_val) {}
    const_sparse_row<T> operator[](unsigned row) const
    {
        return const_sparse_row<T> (row, the_map, default_value);
    }
 
    sparse_row<T> operator[](unsigned row)
    {
        return sparse_row<T>( row, the_map, default_value);
    }    
    const_iterator begin() const { return the_map.begin(); }
    const_iterator end() const   { return the_map.end(); }
    iterator begin()  { return the_map.begin(); }
    iterator end()    { return the_map.end(); }
};
void read_only_mat( const sparse_mat<int> & mat)
{
   std::cout << "mat[1][1] = " << mat[1][1] << std::endl;
   std::cout << "mat[10][100] = " << mat[10][100] << std::endl;
   std::cout << "mat[10][110] = " << mat[10][110] << std::endl;
   std::cout << "mat[15][110] = " << mat[15][110] << std::endl;
}
int main()
{
   typedef sparse_mat<int> Mat;
 
   Mat mat(0);
   mat[10][100] = 3;
   mat[15][110] = 5;
 
   read_only_mat( mat );
   std::cout << "mat[1][1] = " << mat[1][1] << std::endl;
   std::cout << "mat[10][100] = " << mat[10][100] << std::endl;
   std::cout << "mat[10][110] = " << mat[10][110] << std::endl;
   std::cout << "mat[15][110] = " << mat[15][110] << std::endl;
   Mat::const_iterator it;
   for( it = mat.begin(); it != mat.end(); ++it)
   {
      Mat::coord_type coords = (*it).first;
      int val = (*it).second;
      std::cout << "mat[ " 
         << coords.first << " ][ " 
         << coords.second << " ] = " 
         << val << std::endl;


 Non so se si riesce a eliminarne una.
Ieri sera ho lavorato un pochino su questa cosa. Il risultato che ho
ottenuto è un meccanismo generico incentrato su un'unica classe proxy
template che consente di implementare array sparsi a N dimensioni (o
comunque mappe a N dimensioni). Gli elementi a cui si fa riferimento non
vengono creati fin quando non viene assegnato loro un valore. Se a
qualcuno interessa, ecco il codice; sono poche righe; ho cercato anche di
commentarle.
#include <map>
#include <iostream>
#include <string>
template< class KeyT, class ValueT >
struct map_wrap // semplice wrapper per map dotato di metodo get_element() 
{
	typedef std::map<KeyT,ValueT>  map_type;
	typedef typename map_type::mapped_type mapped_type;
	typedef typename map_type::key_type    key_type;
	map_type map_;
	mapped_type* get_element(const key_type& k, bool create ) 
	{ if( create ) { return  &(map_[k]); }
	  else { map_type::iterator i = map_.find(k); 
	  if( i == map_.end() ) return 0;
	  return &(*i).second; }
	}
};
template< class T >
struct value_wrap 
// questo wrapper è necessario, perchè bound_key_map_proxy<> (sotto)
// deve poter far riferimento a mapped_type e key_type del mapped_type
// della mappa parent, anche se quello è un valore e non un map_wrap<> o 
// un bound_key_map_proxy<>
{
	typedef T             value_type;
	value_type val;
	typedef value_type    mapped_type; //dummy
	typedef void          key_type; //dummy
	void operator=(const value_type& v ) { val = v; }	
	operator value_type& () { return val; }
};
template< class MapLikeT > 
struct bound_key_map_proxy 
// incapsula un riferimento a elemento di una mappa 
// in forma di  coppia (puntatore a mappa parent,chiave)
// bound_key_map_proxy<> può esso stesso funzionare come mappa
// il rif. è risolto _solo_ in caso di assegnamento o di conversione
// la mappa può essere un map_wrap<> oppure un altro bound_key_map_proxy<>	
{
	typedef typename MapLikeT::key_type    parent_key_type;	
	typedef typename MapLikeT::mapped_type    parent_mapped_type;	
	MapLikeT*  map_r_;	
	const parent_key_type   key_;  
	bound_key_map_proxy( MapLikeT* m, const parent_key_type& k ) : 
		map_r_(m), key_(k)
	{ }
	typedef bound_key_map_proxy<MapLikeT>	this_type;
 
	typedef typename parent_mapped_type::mapped_type  mapped_type;
	typedef typename parent_mapped_type::key_type     key_type;
 
	bound_key_map_proxy< this_type >
	operator[]( const key_type& k ) { 
		return bound_key_map_proxy< this_type > (this,k); 
	// crea temporaneo con this come mappa di riferimento
	}	
	mapped_type*
	get_element(const key_type& key, bool create ) 
	// restituisce (ed eventualmente crea) elemento
	{  parent_mapped_type* val =  map_r_->get_element(key_,create); 
	   return val ? val->get_element(key,create) : 0;	
	  // NB: il mapped_type della parent map è anch'esso una mappa	
	}
	void
	operator=(const mapped_type& value )
	{  parent_mapped_type* val = map_r_->get_element(key_,true); 
  // richiede (e fa creare) il valore nella mappa parent corrisp. a key_
	   *val = value; // assegna valore [esempio di commento inutile]	
	}
	operator mapped_type() 
	{ parent_mapped_type* val = map_r_->get_element(key_,false);
	  // richiede il valore nella mappa parent corrisp. a key_
	  // sarà 0 se la chiave key_ non esiste
	  return  val ? *val : mapped_type(); 
	  // restituisce valore effettivo o quello di default
	}
 
};
template< typename T >
struct sparse_array3 // esempio di array sparso a 3 dimensioni
{
	typedef map_wrap< int, value_wrap<T> >  array1_map_type;
	typedef map_wrap< int, array1_map_type >   array2_map_type;
	typedef map_wrap< int, array2_map_type >   array3_map_type;
	array3_map_type	map_;
	typedef bound_key_map_proxy< array3_map_type > top_proxy_type;
 
	top_proxy_type operator[](const array3_map_type::key_type& v ) 
	{ return	top_proxy_type( &map_, v );	}
};
int main()
{
 
 sparse_array3<std::string>	mat;
 
 mat[0][12][1] = "ciao"; // crea elemento e assegna valore
 
 std::string s1 = mat[0][12][1]; // assegna "ciao"
 std::string s2 = mat[0][12][2]; // assegna stringa vuota (non crea elemento)
 
 cerr << s1 << endl;	
 cerr << s2 << endl;	
}
Max

 a = mat; //  legale: adesso torna 3
In effetti gli operatori operator =()  e operator const T() andrebbero
dichiarati
privati mentre dovrebbero essere esposti quelli che copiano una Matrix<T> e
fanno il cast ad un T t[][] esteso. Non ho messo tutti i controlli sugli
indici,
al posto del mutable row si potrebbe usare un bool che non generi malintesi
e non
vi e' niente di male ad usare una class Dummy etc. etc e sono convinto che
dovendo
usare una matrice sparsa varrebbe la pena una implementazione molto + simil
c
o Fortran, dipende se si devono fare operazioni matriciali o che altro.
Era solo per notare come si possa estendere il formalismo del c++.
ciao
Massimo