Problema com código

[Felipe]

Eu estou com um problema com um código em C, só quero passar para C++,
mas eu não consigo entender a parte dos defines. Alguém pode me
ajudar?

Segue abaixo o código:

/* */

#define MAX_FREQ 1.0e38
#define C(i,j) cost[i*(n+1)+j]
#define BEST(i,j) best[i*(n+1)+j]

int *opt_bin( double *rf, int n ) {
int i, j, k;
int *best;
double *cost, t;

best = (int *)calloc( (n+1)*(n+1), sizeof(int) );

cost = (double *)calloc( (n+1)*(n+1), sizeof(double) );

for(i=0;i<n;i++)
for(j=(i+1);j<(n+1);j++)
C(i,j) = MAX_FREQ;

for(i=0;i<n;i++) C(i,i) = rf[i];

for(i=0;i<(n+1);i++) C(i,i-1) = 0;


for(j=1;j<n;j++) {

for(i=1;i<=(n-j);i++) {

for(k=i;k<=(i+j);k++) {
t = C(i,k-1) + C(k+1,i+j);
if ( t < C(i,i+j) ) {
C(i,i+j) = t;
BEST(i,i+j) = k;
}
}

t = 0;
for(k=i;k<=(i+j);k++) t = t + rf[k];
C(i,i+j) = C(i,i+j) + t;
}
}
return best;
}

[Thiago Adams]

As macros foram criadas para acessar os valores de "cost" e "best"
como sendo uma matrix quadrada de tamanho (n+1).
Não existe uma classe para matrix no C++. Mas você deve facilmente
encontrar alguma lib para isso.

O que é possível fazer usando STL é criar um vetor de vetores.

std::vector< std::vector <int> > matrix;

Ou criar sua própria classe de matrix utilizando vector internamente.

[Thiago Adams]

Só por curiosidade vou colocar aqui uma implementação que fiz em 5
minutos de matriz.
(Está incompleta claro)

template<class T>
class matrix
{
std::vector<T> m_data;
int m_rows, m_cols;

template<class T> class matrix_row
{
friend class matrix;
T * m_pdata;
matrix_row(T *d) : m_pdata(d) {}
public:
T & operator [](int col) { return m_pdata[col]; }
};

public:
matrix(unsigned int numRows, unsigned int numCols)
: m_rows(numRows), m_cols(numCols), m_data(numRows * numCols)
{
}

matrix_row<T> operator [](int i) {
return matrix_row<T>(&m_data[i * cols()]);
}

unsigned int cols() const { return m_cols; }
unsigned int rows() const { return m_rows; }
};

A classe matrix_row é opcional mas pode ser usada em debug para chegar
se o indice está correto.

Em release poderia ser:

template<class T>
class matrix
{
std::vector<T> m_data;
int m_rows, m_cols;
public:
matrix(unsigned int numRows, unsigned int numCols)
: m_rows(numRows), m_cols(numCols), m_data(numRows * numCols)
{
}

T* operator [](int i) { return &m_data[i * cols()]; }
unsigned int cols() const { return m_cols; }
unsigned int rows() const { return m_rows; }
};

[Felipe Costa]

Obrigado pela ajuda e pela implementação da matrix.

 

Felipe

[Felipe Costa]

Apesar de preferir usar a STL, não posso usa-la por ser um trabalhinho de faculdade.

Felipe

[Felipe Costa]

vou usar array de ponteiros.

Felipe

[Cesar Mello]

Felipe,

 

Trabalhos de faculdade são ótimos pra usar STL e ensinar aos professores um pouco de C++. :-)

 

[]

Mello

[Felipe Costa]

Concordo, mas ele não quer que use.

Felipe

[Raphael Menezes]

Exatamente, Cesar. Há 2 anos atrás consegui mudar o cotidiano de um professor apresentando o MAP pra ele!

Alias, Felipe, seu professor usa drogas ?

On Mon, May 12, 2008 at 4:42 PM, Felipe Costa <felipe.h...@gmail.com> wrote:

Concordo, mas ele não quer que use.

Felipe

--
"Pra que ser mais ou menos se você pode C++?"

[Felipe Costa]

Que eu saiba não.

Agora, sobre a linguagem, ele sabe C++ e usa a STL também, mas a máteria dele é sobre organização de Dados. Por isso o motivo de não usar a STL.

 

Felipe H.

[Márcio Gil]

Uma solução utilizando templates:

template <typename T, size_t M, size_t N>
int* opt_bin( const T(*rf)[M][N] )
{
int i, j, k;
int (*best)[M+1][N+1]
T cost[M+1][N+1];
best = (int (*)[M+1][N+1])new int[(M+1)*(N+1)];
...
return (int*)best;
}

O "cost" não precisa ser alocado. O best deve ser acessado assim:
(*best)[i][j]

Uma dúvida para os experts da lista: Porque não posso fazer assim?

best = new int[M+1][N+1]; // Não funciona!!!

Márcio Gil.

> -----Mensagem original-----
> De: ccppb...@googlegroups.com
> [mailto:ccppb...@googlegroups.com] Em nome de Felipe
> Enviada em: segunda-feira, 12 de maio de 2008 00:05
> Para: ccppbrasil
> Assunto: Problema com código

[Thiago Adams]

Não faz sentido querer saber o tamanho do array com templates e depois
fazer uma alocacao dinamica.
Ou voce faz uma coisa ou outra.
Para passar um array e descobrir o tamanho com templates ele tem que
ser alocado na pilha e voce tem que usar referencia.

> > }- Hide quoted text -
>
> - Show quoted text -

[Felipe Costa]

Nesse caso, fica assim:

best = new int*[M];
   
    for (int i = 0; i < n; i++)
            best[i] = new int[M];



--
Abraços,
Felipe H.

[Márcio Gil]

---- Mensagem original ----
> De: ccppb...@googlegroups.com Em nome de Felipe Costa

>
> Nesse caso, fica assim:
>
> best = new int*[M];
>
> for (int i = 0; i < n; i++)
> best[i] = new int[M];
>
>

Ok vai funcionar muito bem. Só que você terá que mudar a sua função
para:

int **opt_bin( double **rf, int n )
{
...
}

e se você declarou a sua matriz como:

double matriz[n][n];

não vai poder passar esta matriz diretamente para a função. Terá que
declarar assim:

double **matriz;

matriz = new double*[n];

for (int i = 0; i < n; i++)

matriz[i] = new double[n];
...
int **best = opt_bin( matriz, n );

ou fazer assim:

double matriz[n][n]
double *rf[n];

for (int i = 0; i < n; i++)

rf[i] = matriz[i];
...
int **best = opt_bin( rf, n );

Atenciosamente,

Márcio Gil.

[Márcio Gil]

> -----Mensagem original-----
> De: ccppb...@googlegroups.com Em nome de Thiago Adams

>
> Não faz sentido querer saber o tamanho do array com templates e depois

> fazer uma alocação dinâmica.

Porque não faz sentido? O código original recebia uma matriz quadrada que
era tratada como se fosse um vetor unidimensional justamente porque em C não
dá para passar uma matriz de tamanho desconhecido. Em seguida ele alocava o
espaço para uma nova matriz quadrada de dimensão n+1. Em C ou C++
"int[3][4]" é a especificação para um tipo "matriz inteira 3 x 4", logo o
template não me dá o tamanho do array mas a especificação das dimensões do
tipo da matriz passada.

> Ou você faz uma coisa ou outra.

Se eu trabalhar sem alocação dinâmica não vou poder retornar uma matriz
maior do que a recebida. Se trabalhar só com ponteiro para inteiro e
alocação dinâmica vou ter que continuar trabalhando com a fórmula
(i*(n+1)+j). A minha sugestão era para ele deixar de utilizar
"best[i*(n+1)+j]" e passar a utilizar "(*best)[i][j]".

> Para passar um array e descobrir o tamanho com templates ele tem que

> ser alocado na pilha e você tem que usar referencia.

O que a função está recebendo é um ponteiro para matriz, não vai alocar uma
matriz na pilha não, só um ponteiro. Se você prefere:

int* opt_bin( const T(&rf)[M][N] )

Não vai mudar quase nada. Apenas que ao invés de escrever "(*rf)[i][j]" só
vai precisar escrever "rf[i][j]". Neste caso (para simplificar a escrita) eu
concordo que a referência é melhor que o ponteiro. Como comecei meus estudos
com o ANSI-C estou mais acostumado a trabalhar com ponteiros que com
referências.

E o ponteiro retornado desta versão em C++ seria perfeitamente compatível
com a versão em C.

Dizer que "não faz sentido" sem primeiro testar se funciona ou não é meio
agressivo não é? Só quis mostrar que existem outras soluções além de uma
classe matrix, gostar ou não já é outra história.

Asseguir a função refeita com template:

template <typename T, size_t M, size_t N>

int* opt_bin( const T(&rf)[M][N] )
{
size_t i, j, k;
int (*best)[M+1][N+1];
T cost[M+1][N+1], t;

best = (int (*)[M+1][N+1])new int[(M+1)*(N+1)];

for(i=0;i<N;i++)
for(j=(i+1);j<(N+1);j++)
cost[i][j] = MAX_FREQ;

for(i=0;i<N;i++) cost[i][i] = rf[0][i];

for(i=0;i<(N+1);i++) cost[i][i-1] = 0;

for(j=1;j<N;j++) {

for(i=1;i<=(N-j);i++) {

for(k=i;k<=(i+j);k++) {
t = cost[i][k-1] + cost[k+1][i+j];
if ( t < cost[i][i+j] ) {
cost[i][i+j] = t;
(*best)[i][i+j] = k;
}
}

t = 0;
for(k=i;k<=(i+j);k++) t = t + rf[0][k];
cost[i][i+j] = cost[i][i+j] + t;
}
}
return (int*)best;
}

[Thiago Adams]

Note que no código original o “rf” é um vetor e não uma matriz NxM.

int *opt_bin( double *rf, int n )
{

…

for(i=0;i<n;i++) C(i,i) = rf[i];

…
}

Este vetor é usado para setar a diagonal da matriz C (cost) que é
alocada dinamicamente.
(Inclusive no seu exemplo esta usando sempre rf[0][i])
Para conhecer o tamanho do “rf” em tempo de compilação é preciso que
ele tenha alocação estática. Se o “cost” ou “best“ forem alocados
dinamicamente você estará misturando a alocação estática com a
dinâmica. Apesar de ser possível, não faz sentido pois o tamanho é
conhecido ou não em tempo de compilação – Não existe meio conhecido.
Se você conhecer o tamanho N e for viável de ser alocado na pilha,
então uma solução 100% estática seria boa em relação à performance. O
retorno poderia ser um argumento passado por referência para a função.

----x---

Existe uma distância muito grande no que é para ser feito em aula do
que seria feito na prática.
Mas, eu concordo que se alguém não sabe o que um vector faz
internamente é melhor entender os conceitos de alocação dinâmica e
ponteiros primeiro.
Segundo nossas enquetes, http://www.cbrasil.org/wiki/index.php?title=Enquetes
52% das pessoas do grupo usam C/C++ profissionalmente e 48% como
estudos / hobby.
Então é papel de quem usa a linguagem profissionalmente (como é meu
caso) mostrar como o problema seria resolvido na prática.
Não sou contra aos “temas de casa” desde que o tópico seja útil para
outras pessoas e que o objetivo não seja apenas entregar mas entender
o que está acontecendo. Acho que dos 48% de integrantes que usam a
linguagem como estudos, a quantidade de perguntas é ainda baixa.
Nesta pergunta especificamente, já que foi colocado uma boa parte do
código, seria interessante dizer qual era o objetivo da função.

---x---

O que aconteceu com aquela competição de escrever o código que
multiplicava matrizes?

[Márcio Gil]

> -----Mensagem original-----
> De: ccppb...@googlegroups.com Em nome de Thiago Adams

>
> Note que no código original o “rf” é um vetor e não uma matriz NxM.
>

Tudo bem, esta parte eu não havia entendido, pensei que 'rf' fosse realmente
uma matriz quadrada.

Então temos duas soluções:

template <typename T, size_t N>
int* opt_bin( const T(&rf)[N] )
{
int (*best)[N+1][N+1];
T cost[N+1][N+1], t;
best = (int (*)[N+1][N+1])new int[(N+1)*(N+1)];
...
for(i=0;i<N;i++) cost[i][i] = rf[i];
...
return (int*)best;
}

se, por exemplo, o vetor foi declarado:

double vetor[4];

Ou então podemos fazer assim, se o vetor original foi alocado dinamicamente:

int* opt_bin( const double *rf, int n )
{
double **cost;
int **best;
cost = new double*[n+1];
cost[0] = new double[(n+1)*(n+1)];
best = new int*[n+1];
best[0] = new int[(n+1)*(n+1)];
for(i=1;i<=n;i++) {
{ cost[i] = cost[i-1]+(n+1);
best[i] = best[i-1]+(n+1);
}
...
for(i=0;i<n;i++) cost[i][i] = rf[i];
...
delete[] cost[0];
delete[] cost;
int *result = best[0];
delete[] best;
return result;
}

Desta maneira não vai ser necessário fazer 2*(n+2) alocações, serão sempre
quatro, e o ponteiro retornado será compatível com a versão em C. Também
poderíamos modificar a função para:

int** opt_bin( const double* rf, int n )
{
...
delete[] cost[0];
delete[] cost;
return best;
}

O que facilitaria a interpretação do retorno da função.