Neste trabalho, cada aluno deve implementar um sistema de multiplicação de matrizes baseando-se em uma estratégia de segmentação em arquivo. Um arquivo M grande é fornecido no formato NxN com valores de ponto flutuante ou inteiros como entrada. Este é processado a partir de várias coordenadas introduzidas por um segundo arquivo, o coordenadas.txt. Em coordenadas.txt deve ser descrito por linha uma dupla de i e j correspondendo a posição inicial e final a ser lida. Por exemplo, as posições 2,4,6,10 indica que a leitura em M deve iniciar na linha 2 coluna 4 e seguir até a linha 6 coluna 10.
Feito a leitura da composição de M para um tipo matriz em C, a segunda etapa é produzir a transposta de M -= MT. Feito isso, produza a multiplicação e armazene em uma hash o resultado da multiplicação como valor para a dupla de i's e j's, os quais deverão ser utilizados como chaves da hash. Assim, para cada novo calculo, antes o sistema deve consular a hash para identificar se a multiplicação já foi realizada. Em caso afirmativo, retorne apenas a resposta já calculada. Caso contrário, elabore a multiplicação e armazene o conteúdo em cache.
Foi utilizado um arquivo .txt
, encontrado também no repositório , chamado matrix.txt. Nesse arquivo foi feita a criação da matriz de Tamanho NxN, que pode ser alterada pelo usuário alterando o valor da váriavel MAXTAM no arquivo aquecimento.hpp
. Essa matriz será utilizada para fazer o recorte de uma matriz menor, achar sua transposta e realizar a multiplicação entre as duas matrizes.
Nessa função foi realizada apenas a criação da matriz NxN no arquivo .txt
. Segue o corpo de código da função:
void writeText(){
int value;
ofstream file;
file.open("matrix.txt");
srand(time(NULL));
for(int i = 0; i < MAXTAM; i++){
for(int j = 0; j < MAXTAM; j++){
value = rand() % 100;
file << value << "\t";
}
file << endl;
}
file.close();
}
Nesta função, tem-se como parâmetro as coordenadas passadas pelo usuário, que transforma essa coordenadas em uma chave única para acesso na Tabela Hash. Segue o corpo de código da função:
double keyFunction(int iLine, int fLine, int iColumn, int fColumn){
return stoi((to_string(iLine)) + to_string(fLine) + to_string(iColumn) + to_string(fColumn));
}
Nesta função, é feita a verificação se a Tabela Hash já possui aquela chave. Se possuir a chave retorna 1, se não possuir retorna 0. Segue o corpo de código da função:
int verify(int key, unordered_map <int, int**> hashMatrix){
auto item = hashMatrix.find(key);
if(item != hashMatrix.end()){
return 1;
}
return 0;
}
Nessa função foi executado tudo que deveria ser feito no problema, desde a leitura da matriz interna até o calculo de multiplicação entre a matriz interna e sua transposta e implementação na Tabela Hash.
Iniciamos a função declarando as variáveis necessárias e pedindo ao usuário as coordenadas da matriz interna, começando as linhas e colunas em 0 e não em 1. Logo após pedir ao usuário as coordenadas, é utilizado os valores das coordenadas para calcular o máximo de elementos que essa matriz possui e criar as variáveis que serão necessárias para cálculo entre as matrizes e para pesquisa e inserção na Tabela Hash. Segue o corpo de código desta parte:
vector<string> token;
string numb;
ifstream file;
int initialLine, initialColumn, finalLine, finalColumn;
int count = 0, countColumn = 0;
cout << "Insira o número da linha inicial da matriz interna: ";
cin >> initialLine;
cout << "Insira o número da linha final da matriz interna: ";
cin >> finalLine;
cout << "Insira o número da coluna inicial da matriz interna: ";
cin >> initialColumn;
cout << "Insira o número da coluna final da matriz interna: ";
cin >> finalColumn;
int maxElements = ((finalLine+1) - initialLine) * ((finalColumn+1) - initialColumn);
int dynamicLine, dynamicColumn;
int **dynamicMatrix, **transposedMatrix, **calculatedMatrix;
int **matrixAux;
Logo após, a variável key
recebe a função keyFunction()
para gerar uma chave única. Gerando a chave única, é feita a pesquisa desta chave na Tabela Hash usando a função verify()
em uma condição, onde se a função retornar 1, a chave já está registrada e a matriz já foi calculada, logo o valor é retornado. Segue o corpo de código desta parte da função:
key = keyFunction(initialLine, initialColumn, finalLine, finalColumn);
if(verify(key, hashMatrix) == 1){
matrixAux = hashMatrix[key];
for(int i = 0; i < ((finalLine - initialLine) + 1); i++){
for(int j = 0; j < ((finalLine - initialLine) + 1); j++){
cout << matrixAux[i][j];
}
}
}
Se a função verify()
retornar 0, é porque a chave não está registrada e a matriz ainda não foi calculada, então o arquivo .txt
é aberto para ser feita a leitura da matriz, usando as coordenadas que o usuário passou para ser feito o recorte, iniciando-se pelas linhas e logo após pelas colunas. A partir do ponto que o caminhamento está nas coordenadas certas, é feita a tokenização de cada elemento até que atinja o máximo de elementos da matriz. Segue o corpo de código desta parte:
file.open("matrix.txt");
if(file.is_open()){ //Abrindo o arquivo txt
for(int i = 0; i < initialLine; i++){
getline(file, numb);
}
while(! file.eof()){
getline(file, numb, '\t');
if(count < maxElements){
if((countColumn >= initialColumn) && (countColumn <= finalColumn)){
token.push_back(numb);
count++;
}
}
countColumn++;
if(countColumn == MAXTAM){
countColumn = 0;
}
}
Sendo feita a tokenização, temos os elementos da matriz tokenizados como string
, o passo agora é transformá-los em inteiros e para isso, foi criado um vetor do tamanho do número de elementos da matriz para armazená-los. A transformação foi feita da seguinte forma:
int size = token.size();
int vetNumbers[size];
for(int i = 0; i < size; i++){
vetNumbers[i] = stoi(token[i]);
}
Possuindo todos os elementos da matriz tokenizados e do tipo inteiro, mas ainda em um vetor simples, é feita a criação da matriz dinâmica para armazenar os elementos e fechando o arquivo .txt
. Para criar essa matriz dinâmica, foi necessário a criação de duas variáveis, dynamicLine e dynamicColumn que irão auxiliar na criação da matriz simples e da matriz transposta, que é o tamanho do caminhamento da linha e da coluna. Segue o corpo de código desta parte:
dynamicLine = (finalLine - initialLine) + 1;
dynamicColumn = (finalColumn - initialColumn) + 1;
/* Matriz Dinâmica */
dynamicMatrix = new int *[dynamicLine];
for(int i = 0; i < dynamicLine; i++){
dynamicMatrix[i] = new int[dynamicColumn];
}
cout << "___________________________________________" << endl << "\tMatriz normal" << endl << endl;
int x = 0;
for(int i = 0; i < dynamicLine; i++){
for(int j = 0; j < dynamicColumn; j++){
dynamicMatrix[i][j] = vetNumbers[x];
cout << dynamicMatrix[i][j] << "\t";
x ++;
}
cout << endl;
}
file.close(); //Fecha o arquivo txt
Possuindo a matriz normal pronta, para criar a matriz transposta foi necessário apenas inverter linha e coluna. Segue o corpo de código desta parte:
/* Matriz Transposta */
transposedMatrix = new int *[dynamicColumn];
for(int i = 0; i < dynamicColumn; i++){
transposedMatrix[i] = new int[dynamicLine];
}
cout << "___________________________________________" << endl << "\tMatriz transposta" << endl << endl;
for(int i = 0; i < dynamicColumn; i++){
for(int j = 0; j < dynamicLine; j++){
transposedMatrix[i][j] = dynamicMatrix[j][i];
cout << transposedMatrix[i][j] << "\t";
}
cout << endl;
}
Possuindo a matriz normal e a matriz transposta prontas, podemos fazer a multiplicação e armazenar essa multiplicação em uma nova matriz dinâmica e na Tabela Hash. Segue o corpo de código desta parte:
/* Multiplicação das matrizes */
calculatedMatrix = new int *[dynamicLine];
for(int i = 0; i < dynamicLine; i++){
calculatedMatrix[i] = new int[dynamicLine];
}
cout << "___________________________________________" << endl << "\tMatriz calculada" << endl << endl;
for(int i = 0; i < dynamicLine; i++){
for(int k = 0; k < dynamicLine; k++){
calculatedMatrix[i][k] = 0;
for(int j = 0; j < dynamicColumn; j++){
calculatedMatrix[i][k] += dynamicMatrix[i][j] * transposedMatrix[j][k];
}
}
}
for(int i = 0; i < dynamicLine; i++){
for(int j = 0; j < dynamicLine; j++){
cout << calculatedMatrix[i][j] << "\t";
}
cout << endl;
}
hashMatrix.emplace(key, calculatedMatrix);
- Ao ser pedido ao usuário as coordenadas, o mesmo deverá inseri-las de forma que as coordenadas iniciais sejam menores que as coordenadas finais. Por exemplo: Linha inicial: 1, Linha final: 5, Coluna inicial: 2, Coluna final: 7.
- A contagem das coordenadas se inicia em 0, então se o usuário deseja, por exemplo, que a linha inicial seja a terceira, deverá inserir a coordenada de linha inicial como 4.
Ao executar o programa, o usuário se deparará com o programa aguardando a inserção das linhas e colunas iniciais e finais da matriz que o mesmo deseja recortar da matriz principal da seguinte forma:
Logo após isso, o programa retornará para o usuário a matriz que ele recortou, a matriz transposta da matriz que ele recortou e a multiplicação entre essas duas matrizes. Logo após imprimir os resultados, o programa deixa ao usuário a opção de recortar uma nova matriz ou sair do programa. Exemplo na imagem abaixo:
O repositório possui um arquivo Makefile que realiza todo o procedimento de compilação e execução. Para tanto, temos as seguintes diretrizes de execução:
Comando | Função |
make clean |
Apaga a última compilação realizada contida na pasta build. |
make |
Executa a compilação do programa utilizando o g++, e o resultado vai para a pasta build. |
make run |
Executa o programa da pasta build após a realização da compilação. |