Mensajes

[Matriz sparse]

Buenas chicos, les traigo un laboratorio de C, que hice en un curso de cómputo científico, espero les sea de utilidad a alguno.

Matriz sparse: es una matriz cuyos elementos no nulos figuran una minoría entre todos. Por ejemplo, una matriz 1000x1000 tiene 10⁶ elementos, supongamos que de los cuales sólo el 10% son no-nulos (10⁵). A la hora de resolver diversos problemas se hace útil almacenarla de una manera especial teniendo en cuenta esto.

(Pueden encontrar un poco más de información del tema en la wikipedia en inglés, también hay papers en google académico)

El programa que se presenta pide un archivo el cual tiene la siguiente estructura

indices de fila de elementos no nulos
indices de columna de elementos no nulos
valores no nulos de la matriz asociados al conjunto de indices
valores de un vector b
.... (así sucesivamente)

Se pide un número de matrices a leer. La función leeMatriz lee una matriz específica en el archivo (1 si es la primera, 2 si es la segunda, etc). Se supone que cada elemento de la matriz tiene al menos un elemento no nulo en cada fila y columna. La función matrizPorVector devuelve el puntero hacia el comienzo del arreglo que contiene los valores del resultado de la multiplicación.

Sin más, acá el código

main.c

Código (c) [Seleccionar] Expandir

// Programa principal
//  Se encarga de establecer interfaz con el usuario.

#include <stdio.h>
#include <stdlib.h>

//Prototipo
int leeMatriz(
char *nomarch, int nummat,
int **ifil, int **icol, double **xval, double **b,
int *nfil, int *ncol);

double *matrizPorVector(int *ifil, int *icol, double *xval, double *b, int nza, int nfil);

int main()
{
char nombre[100];
char salida[] = "resultados.txt";
FILE *archivo;
int num;
double *xval;
double *b;
int *ifil, *icol;
int nfil, ncol;
int retorno, i, k;
double *resultado;

//Se pide al usuario que introduzca los datos para la lectura
printf("Introduce nombre de archivo: ");
scanf("%s", nombre);

printf("Introduce numero de matrices en el archivo: ");
scanf("%d", &num);

//Abrimos el archivo de salida
if ( (archivo = fopen(salida, "w+")) == NULL)
{
printf("No se ha podido abrir el archivo de salida %s \n", salida);
exit(EXIT_FAILURE);
}

//Leemos la cantidad de matrices que el usuario ingresó
for(k=1; k<=num; k++)
{
//Leemos la k-ésima matriz
retorno = leeMatriz(nombre, k, &ifil, &icol, &xval, &b, &nfil, &ncol);

//Damos un mensaje alusivo
fprintf(archivo, "La matriz numero %d\r\n", k);

//Imprimimos en el archivo de salida, dependiendo de lo que retornó leeMatriz
switch(retorno)
{

case -2:
fprintf(archivo, "Los tamaños de los vectores no son compatibles\r\n");
break;

case -1:
fprintf(archivo, "El tamaño del vector no coincide con el numero de columnas\r\n");
break;

default:
fprintf(archivo, "Los tamaños coinciden. El vector resultado es:\r\n");

//Procesamos los datos para obtener el resultado
resultado = matrizPorVector(ifil, icol, xval, b, retorno, nfil);
for(i=0; i<nfil; i++)
fprintf(archivo, "%lf   ", *(resultado+i) );

//Liberamos la memoria del vector resultado solo en este caso
free(resultado);
fprintf(archivo, "\r\n");
break;
}
//Liberamos la memoria reservada para volver a llamar
//de manera segura la función malloc dentro de las funciones

//Liberamos la memoria de los vectores que generan el par matriz-vector
//luego de esto, quedan apuntando a NULL, tal cosa es lo que espera
//la funcion leeMatriz, al final del programa esto se hace de último
//y por lo tanto nos aseguramos de que liberamos toda la memoria dinamica
//que se utilizó a lo largo del programa
free(ifil);
free(icol);
free(xval);
free(b);

fprintf(archivo, "\r\n");
}

//Cerramos el archivo de salida
fclose(archivo);


return 0;
}

matrizPorVector.c

Código (c) [Seleccionar] Expandir

// Funcion que realiza la multiplicacion de una matriz sparse por un vector
// Argumentos.
// Entrada:
// int *ifil, vector de indices de filas
//  int *icol, vector de indices de columnas
//  int nza, cantidad de valores no nulos
//  int nfil, orden de filas
// double *xval, *b, los valores no nulos y el vector

// Salida (por return)
// double *, una dirección de memoria, el cual será el comienzo
//  del vector resultado de la multiplicación

#include <stdio.h>
#include <stdlib.h>

double *matrizPorVector(int *ifil, int *icol, double *xval, double *b, int nza, int nfil)
{
unsigned k; // unsigned i;
double *resultado;

if ( ( resultado = (double *) malloc ( nfil*( sizeof(double) ) ) ) == NULL )
{
printf("No hubo memoria disponible para la reserva de un resultado\n");
exit(EXIT_FAILURE);
}

//Inicializamos los valores del vector resultado
for(k=0; k<nfil; k++)
*(resultado + k) = 0.0f;

// Cada k tal que 0<=k<nza cumple que
// El elemento en la posicion *(ifil+k), *(icol+k) es *(xval+k)
// Sólo hay que recordar que el conjunto de indices en los
// vectores ifil, icol comienzan desde 1, no desde cero
// por lo tanto debemos restarle 1 cuando utilizamos este
// conjunto de indices

// Como resultado obtenemos un for más compacto, y además
// un algoritmo mucho más rapido para matrices muy grandes
for(k=0; k<nza; k++)
*(resultado+(*(ifil+k))-1) += (*(b - 1 + (*(icol+k))))*(*(xval+k));


// Retornamos la direccion de memoria del comienzo del arreglo
return resultado;
}


leeMatriz.c

Código (c) [Seleccionar] Expandir

// Funcion que lee matriz desde archivo de texto.
// Argumentos.
// Entrada:
// char *nomarch : nombre de archivo
// int nummat : numero de matriz a leer

// Salida (por referencia)
// int *ifil : vector de indices de filas
// int *icol : vector indices de columnas
// double *xval : vector de valores asociado a la matriz en los indices de ifil e icol
// double *b : vector asociado al par nummat de matrices-vectores
// int *nfil : numero de filas
// int *ncol : numero de columnas

// Salida (por return)
// -2, si los vectores xval, ifil e icol no tienen el mismo tamaño
// -1, el tamaño de b no corresponde con el nuero de columnas de la matriz
// a, si todos los valores se corresponden, donde a es el numero de elementos no nulos de la matriz


#include <stdio.h>
#include <stdlib.h>

int leeMatriz(
char *nomarch, int nummat,
int **ifil, int **icol, double **xval, double **b,
int *nfil, int *ncol)

{
int a = 0; // Valor de retorno
int nbytes; // Identificador para el retorno de fscanf */
int nval, nb; // Numero de valores no nulos de la matriz, y numero de valores del vector */
char c;
// Caracter que se lee después de los valores */
int foo, aux;
// Un contador y una variable auxiliars */
int bar[4]; // Variables logicas auxiliares

FILE *archivo;

// Validamos la correcta apertura del archivo
if ( (archivo = fopen(nomarch, "r")) == NULL)
{
printf("No se ha podido abrir el archivo %s \n", nomarch);
exit(EXIT_FAILURE);
}




// Saltamos las lineas necesarias hasta la matriz que se nos pide
for (foo = 1; foo<=4*(nummat-1); foo++)
{
do
{
fscanf(archivo, "%c" , &c );
} while( c != '\n' && c != '\r' );
}

//Inicializamos la salida, suponemos que los vectores apuntan a nulo en esta llamada.
//Los arreglos (leidos en ese orden)

//Guardamos como valor logico cada uno de los siguientes.
bar[0] = ( *ifil = (int *) malloc( sizeof(int) ) ) == NULL;
bar[1] = ( *icol = (int *) malloc( sizeof(int) ) ) == NULL;
bar[2] = ( *xval = (double *) malloc( sizeof(double) ) ) == NULL;
bar[3] = ( *b = (double *) malloc( sizeof(double) ) ) == NULL;

//Si alguno de los malloc retorna NULL, imprimimos un mensaje alusivo y salimos
if(bar[0] || bar[1] || bar[2] || bar[3])
{
printf("No hubo memoria disponible al inicializar los pares de vectores asociados a la matriz\n");
exit(EXIT_FAILURE);
}
//El contador de ifil, icol, y del arreglo b


//Nota importante: los punteros son pasados por referencia, o sea punteros a punteros de tipo
//Las lineas de arriba dicen el contenido del puntero a puntero (que es un puntero) es la direccion
//de memoria que retorna la función malloc en el tamaño especificado

*nfil = *ncol = nval = nb = 0;

//Leemos la entrada que se nos pide. La lectura completa consta de 4 líneas
//Con este for lo que pretendo es ahorrarnos líneas repetitivas


for(foo = 1; foo<=4; foo++)
{
do
{
switch(foo)
{

//Lectura de ifil

case 1:
fscanf(archivo, "%d" , (*ifil+(*nfil)) );
*ifil = (int *) realloc( *ifil, (++(*nfil)+1)*sizeof(int) );
break;


//Lectura de icol
case 2:
fscanf(archivo, "%d" , (*icol+(*ncol)) );
*icol = (int *) realloc( *icol, (++(*ncol)+1)*sizeof(int) );
break;

//Lectura de xval
case 3:
fscanf(archivo, "%lf" , *xval+nval);
*xval = (double *) realloc( *xval, (++nval+1)*sizeof(double) );
break;

//Lectura de b
case 4:
fscanf(archivo, "%lf" , *b+nb);
*b = (double *) realloc( *b, (++nb+1)*sizeof(double) );
break;


}

} while ( (nbytes = fscanf(archivo, "%c", &c)) != EOF && c != '\n' && c != '\r' );
//Cada iteración del for lee una línea
}

fclose(archivo);

//Dado que, cuando llega al fin de línea igualmente se le agrega
//un espacio a los vectores, quitamos este espacio extra

//Damos esta solución para el problema de validar que se ha hecho la reserva
//de manera correcta, en lugar de uno por uno, se haen todos, si alguno
//no ha salido como se esperaba, el programa no tiene sentido que continue
bar[0] = ( *ifil = (int *) realloc( *ifil, (*nfil)*sizeof(int) ) ) == NULL;
bar[1] = ( *icol = (int *) realloc( *icol, (*ncol)*sizeof(int) ) ) == NULL;
bar[2] = ( *xval = (double *) realloc( *xval, (nval)*sizeof(double) ) ) == NULL;
bar[3] = ( *b = (double *) realloc( *b, (nb)*sizeof(double) ) ) == NULL;

//Si alguno de los realloc retorna NULL, imprimimos un mensaje alusivo y salimos
if(bar[0] || bar[1] || bar[2] || bar[3])
{
printf("No hubo memoria suficiente para hacer realloc a los vectores de una matriz\n");
exit(EXIT_FAILURE);
}

if ( *nfil != *ncol || (*nfil != nval || *ncol != nval)  ) return -2;


//Se toma el mayor valor de los indices de filas/columnas como orden de la matriz
aux = **ifil;
for(foo=1; foo<*nfil; foo++)
if( *(*ifil+foo) > aux )
aux = *(*ifil+foo);
*nfil = aux;

aux = **icol;
for(foo=1; foo<*ncol; foo++)
if( *(*icol+foo) > aux )
aux = *(*icol+foo);
*ncol = aux;
//Para este punto, *nfil tiene el orden de la matriz en cuanto
//a filas y *ncol en cuanto a las columnas y por tanto podemos
//comparar con el segundo if para retornar

//Por defecto se retorna el numero de elementos no nulos encontrados en xval
a = nval;
//De encontrarse un problema de consistencia, cambiamos el valor de a

if ( *ncol != nb ) a = -1;

//Retornamos
return a;
}

Saludos, quizá pronto traiga más de este tema

Nota quiero agradecer a mi profesor quien hizo esfuerzo a lo largo del curso trayendo laboratorios interesantes.

PD: como siempre, acepto sugerencias y consejos

Sigo apoyando lo que dice Regexp pero corrijo algo burbuja no es n², es n! Ya que cada ciclo mayor resuelve uno :p
[...]

Sino mal recuerdo es O(N²), o al menos, en el peor de todos los casos. El caso "medio" es un poco menor, pero para valores muy grandes de N, en una ecuación de segundo grado A*N²+B*N+C puede aproximarse simplemente a N². Como dirían por ahí, hay infinitos más grandes que otros. http://www.c.conclase.net/orden/?cap=burbuja

De ser N! sería totalmente imposible de usar , dado que N! es aún mayor que la exponencial desde un cierto N.

N! >= 2^N, para toda N>=4, prueba por inducción

Cuando lo que se busca es que los algoritmos tiendan a tener complejidad logarítmica, dado que

log(N)<=N<=e^N, para toda N>=1, prueba por crecimiento y decrecimiento de las funciones.

El caso N² es especial, para valores pequeños de N, no es problemático... en cuanto crece.. el algoritmo no escala.

En cuanto a hacerlo por condicionales... la mejor manera sería como ha dicho nuestro compañero engel lex, por fuerza bruta, en tal caso para N elementos pueden existir N-1 posibles cadenas que vienen después (o antes, dependiendo de la implementación), y así, al ser sólo 3 cadenas de caracteres, tendrías 3*2*1=3!=6 posibles secuencias de cadenas ordenadas.

Saludos

¿Estás obligado a hacerlo sin arreglos?

Los algoritmos de ordenamiento NO son un problema trivial, han sido estudiados ampliamente y son algo bastante complejos. El algoritmo de burbuja es el más "intuitivo" y sencillo de implementar. Si te fijas, son dos for anidados, cada uno recorre la cantidad de elementos a ordenar, es decir 3x3, conforme el numero de palabras crece digamos a N, la cantidad de iteraciones es N². Es decir, tendrías que hacer... MUY cuidadosamente 9 condicionales para este caso.

Eso lo convierte en una solución muy tediosa de hacer. No te lo recomiendo. A menos que estés obligado porque así te lo han pedido tus profesores (o así dice el libro/ejercicio), hazlo con arreglos.

Saludos

Tal como dice engel lex, con cualquier algoritmo de ordenamiento sirve porque las letras están en orden alfabético en la tabla Ascii, en otras palabras 'a' < 'x' y así.

Si quieres verlo con strcmp puedes, dado que n=strcmp( str1, str2 ) devuelve:
n=0, si las cadenas de caracteres son iguales
n>0, si el primer carácter en el que las cadenas son diferentes tiene mayor valor en la tabla ascii en str1
n<0, si el primer carácter en el que las cadenas son diferentes tiene mayor valor en str2

Por ejemplo si str1="abcz"; str2="abcx", el primer caracter en el que difieren es en el 4 (contando desde 1), y como bien sabemos 'z'>'x', entonces strcmp(str1, str2)>0

Un problema interesante es si las cadenas difieren justamente en una mayúscula o minúscula, por ejemplo "ABCD" y "ABCa", te dará un problema, dado que strcmp devolvería negativo, causando que el algoritmo tenga problemas en el ordenamiento.

La solución mas sencilla a esto sería convertir la cadena completa en todo a mayúsculas o todo a minúsculas, recorrer cada letra de cada palabra con la función toupper, o tolower, es decir:

Código (c) [Seleccionar] Expandir

palabras[x][y]=tolower( palabras[x][y] )

De resto te podría recomendar el quick sort, pero a efectos de tres palabras la diferencia en tiempo de ejecución sería mínima, casi imposible de percibir.

También puedes hacer tu función strcmp específica para este problema, no es más que tratar una cadena de caracteres como un numero representado en la base "cantidad de caracteres admitidos en las cadenas", 255 con la tabla Ascii básica o 26 sólo con letras. Cada espacio del arreglo viene siendo la cifra correspondiente, donde str[0] es la cifra de mayor importancia (la primera letra). Viéndolo así, simplemente basta con extrapolar el algoritmo para determinar si un numero es mayor que otro que aprendiste en la escuela a algo un poco más general. Un numero es menor que otro si el primero se encuentra a la izquierda del segundo en la recta numérica.

Espero sea de ayuda.

Saludos

[Edit]

Hola gentica.

Os vengo a comentar que estoy trasteando con arduino y raspberry pi, y bueno, el caso es que tengo creado un archivo index.php con un código para que se conecte al puerto serial de arduino e imprima los datos.

La conexión es correcta, lo que los datos no salen bien, es decir, tengo que refrescar la página muchas veces para que salga correctamente: Humedad 35.00% Temperatura: 28 *C (por poneros un ejemplo)
Y lo que sale otras veces es nada, o a mitad, etc.

Alguien sabe como podría leer correctamente estas cadenas de caracteres y que PHP las mostrara bien?He pensado quizás haciendo con un array, pero claro, el código de arduino también es muy especial, y no estoy seguro de si funcionará si pongo los datos que recoge por separado.

Si alguien alguna vez ha hecho algo, o sabe de algún método por favor que me lo diga. Llevo bastante rato buscando por internet, probando diferentes "soluciones" si se pueden llamar así, pero no me sirven ninguna.

Un saludo.

EDITO: JUU enserio no sabe nadie? joer, pero esque nose como hacer que PHP muestre la lectura entera que recibe del puerto serial conectado a Arduino, llevo días intentando solucionarlo, por favor si alguien le ha pasado lo mismo o tiene idea de como hacerlo que porfavor me diga alguna manera. Un saludo.

No tengo mucha experiencia con arduino, no en este sentido. Pero mirando tu código es posible que te sea útil cambiar fgets por file_get_contents() para leer el "archivo" completo en lugar de una sola línea, sino, hacer un ciclo.. Dado que arduino seguirá imprimiendo en un loop infinito ¿no?

Espero te sea de ayuda, sino, un amigo en la universidad hizo algo por el estilo, también para una raspberry pi, pero en lugar de PHP usó python, lo que hace es twittear la temperatura, cada vez que llega a un punto crítico. Tiene el repositorio en github.


Edit

Quizá para resolver este problema te sirva que arduino lea, si existe determinada entrada (o si simplemente existe), imprima las últimas mediciones de temperatura. De manera que el PHP, le diga al arduino que imprima la última medición y le de un tiempo estipulado para hacer esto último.

Acá encontré algo que puede ser útil, para usar fgets y fwrite. http://stackoverflow.com/questions/13114275/php-serial-port-data-return-from-arduino

Saludos

Muchas Gracias.

De hecho estaba creando un modulo para que el dueño del documento elija que usuarios pueden modificar ese documento.
Ahi queria ver si ese usuario con permisos podia continua editando el documento donde quedo la ultima vez. Pense por un momento en generar una rama para que quede salvado el documento anterior por si este se manda alguna cagada en la edicion, con eso podria volver atras lo ultimo que se hizo.

Como es texto plano, puedo darle un id para el que sea el original y otro para ver cual es el que se genero ultimo.

Con esas lineas me has dado algunas ideas, ahora tengo que ver como loguear git en segundo plano para que los usuarios no lo vean.

Si tiene ideas tiren que puede ser util para proyectos futuros de control de versiones.

Saludos.

Quizás en lugar de crear dos archivos diferentes, te sirva crear un branch por usuario autorizado y luego el dueño tenga la opción de hacer merge cuando lo decida. Una característica que quizá se te pueda hacer interesante es la siguiente situación:

El usuario A, comienza a editar su branch desde el master el día lunes. Y llega el usuario B de vacaciones el miercoles y quiere comenzar a editar, su branch estará actualizada para el master y no con la del A.

Sería interesante que se informara al usuario B de los cambios que se ha hecho el usuario A para darle la opcion de actualizar su branch a los cambios que ha hecho él.

Al final de la semana, el dueño hace merge.

No se si te sea de ayuda también , sino puedes hacer en una base de datos por tablas, pero entonces se complicaría el asunto conforme la cantidad de documentos crezca.

Saludos

Muchas gracias Regexp,

Esto es lo que he entendido:

if (exponente%2  == 0 ){
      return potencia( potencia(base, exponente/2),2);
   }

Exactamente 

Saludos

[edit]

Gracias ivancea, pero no te he entendido, es decir, yo lo he conseguido hacer haciendo base * potencia(base, exponente -1) y en el ejercicio me lo pide de otras formas.


Saludos

Hola sora_ori, creo el ejercicio se basa en manejar bien los operadores aritméticos y las llamadas a funciones. Haciendo un poco al aire el asunto, creo que sería así

Código (c) [Seleccionar] Expandir


// [...] declaracion de funcion, main, prototipo, etc.
// [...] funcion potencia(x, n)
// n de tipo entero

// [...] Los condicionales basicos que ya hiciste, 1 si n=0 o x si n=1

// dejo el caso si n es par: (x^(n/2))^2
if ( n%2 == 0 ) return exponencial( exponencial(x, n/2), 2 );
// es decir, la base de la primera exponencial es una exponencial

// aca iría el caso si n no es par

// [...] fin de la función



Ya tienes una parte, falta que, basándote en el ejemplo que te dí, termines el ejercicio.  

edit el ejercicio propone hacer una función recursiva para exponencial (entero), que se llame menos veces a sí misma.

Saludos

[Edit:]

Podría ser con git, pero se me ocurre que podrías tener el problema de que haga el seguimiento de tu propio código.. Imagino que no querrás mostrar el histórico de todos los archivos, sino de ése específicamente.

Código (php) [Seleccionar] Expandir


<?php
$usuario = $_POST['usuario'];
// [...] ~ modifico archivo...
system("git add archivo-de-texto.txt");
system("git commit -m 'modificado por $usuario'");
// [...]
?>




Edit: con la función exec(string $s) obtendrás la salida del comando $s, para luego (de alguna manera), interpretarlo y mostrarlo como código HTML hacia el navegador.

Saludos

¡Buen aporte! 

Me ha gustado bastante, de hecho, lo tendré en mente para futuros proyectos. La solución fue bastante sencilla. Creo que estaría muy bien hacer un plugin para Cake o algún otro framework.

Saludos