##Análisis empírico Se analizará por separado cada estructura, comentando en su código el costo de cada línea. Se considera O(1) las operaciones free, calloc y malloc. Se preguntó esto a un ayudante.
ArrayList* arraylist_init(){
ArrayList* array = malloc(sizeof(ArrayList)); // O(1) malloc
array->size = 2; // O(1) asignacion
array->datasize = 0; // O(1) asignacion
array->data = malloc(sizeof(int*) * array->size); // O(1) malloc
return array; // O(1) return
}La operación es O(1), ya que no hay iteraciones y son todas las lineas O(1).
Esta operación duplica el tamaño del arreglo, haciendo que pueda almacenar el doble de números en comparación a su tamaño anterior.
void double_size(ArrayList* list){
list -> size *= 2; // O(1) duplicar el valor de un int.
int *new_data; // O(1) crear un puntero
new_data = calloc( (list->size), sizeof(int*)); // O(1) asignar memoria al puntero y limpiarla
for (int i = 0; i < list->datasize; i++){ // O(1) cada iteración
new_data[i] = list->data[i]; // O(1) acceder a un valor y asignarlo al array de ints
}
free(list->data); // O(1) liberar un puntero
list->data = new_data; // O(1) asignar un puntero
}Lo más relevante es el for. Sea n= list-> datasize, como son n iteraciones, el costo de esto es O(n), ya que el resto de las operaciones son O(1)
void arraylist_append(ArrayList* list, int element){
if (list->datasize >= list->size){ // O(1), una comparación
double_size(list); // O(n)
}
list->data[list->datasize] = element; // O(1) asignar un valor
list->datasize++; O(1) asignar un valor +1
}Costo total:
- O(n) si se necesita agrandar
- O(1) si no se necesita agrandar
void arraylist_insert(ArrayList* list, int element, int position)
{
if (list->datasize >= list->size){ // O(1) una comparacion
double_size(list); // O(n)
}
int aux; // O(1)
for (int i = position; i <= list->datasize; i++){ // O(1) cada iteracion
if (position < list->size){ // O(1) comparacion
aux = list->data[i]; // O(1) asignar valor
}
list->data[i] = element; // O(1) asignar valor
if (position < list->size){ // O(1) comparacion
element = aux; // O(1) asignar valor
}
}
list->datasize++; // O(1) asignar valor +1
}Sea n= list->datasize, en el for se itera n veces y es lo más costoso, aparte del O(n) en caso de necesitar agrandar la lista.
Por el for, se tiene O(n) siempre y un posible O(n) para agrandar. En cualquier caso es O(n).
int arraylist_delete(ArrayList* list, int position)
{
int deleted = list-> data[position]; // O(1)
for (int i=position+1; i< list->datasize; i++) { // O(1) cada comparacion
list->data[i-1] = list->data[i]; // O(1) asignar valor
}
list->datasize--; // O(1) asignar valor
return deleted; // O(1) retornar
}Sea n la cantidad de elementos que se compararán en el for. Como se hacen n iteraciones, el costo de esta operación es O(n).
int arraylist_get(ArrayList* list, int position)
{
if (position < list->datasize){ // O(1) comparacion
return list->data[position]; // O(1) return
}
printf("No existe un elemento en la posicion %d.\n", position); // O(1) printf
return -1; // O(1) printf
}Cada linea es O(1), por lo que la operación es O(1).
void arraylist_destroy(ArrayList* list){
free(list->data); // O(1) free
list->data = NULL; // O(1) asignar
free(list); // O(1) free
list = NULL; // O(1) asignar
}Cada linea es O(1), por lo que la operación es O(1).
void arraylist_concatenate(ArrayList* list1, ArrayList* list2)
{
while (list1->size <= list2->size){ // O(1) cada iteracion
list1->size * =2; // O(1) asginacion
}
if (list1->size - list1->datasize < list2->datasize){ // O(1) comparacion
list1->size * =2; // O(1) asginacion
}
int* new_data = malloc(list1->size * sizeof(int)); // O(1) malloc
for (int i = 0; i < list1->datasize; i++){ // O(1) cada comparacion
new_data[i] = list1->data[i]; // O(1) asginacion
}
free(list1->data); // O(1) free
list1->data = new_data; // O(1) asginacion
for (int i = 0; i < list2->datasize; i++){ // O(1) cada iteracion
arraylist_append(list1, list2->data[i]); // O(1) porque no se necesita agrandar
}
arraylist_destroy(list2); // O(1)
}La cantidad de veces que se repite el while, o sea la cantidad de veces que se ejecuta double_size es en el peor de los casos log_2(n), ya que al hacer size * =2 se duplica la cantidad de elementos que hay en list1, entonces ese while es O(log(n)).
El for tiene un costo de O(n).
Las operaciones más costosas son O(log(n)) y O(n), pero se suman, por lo que solo se queda la más grande. La función es O(n).
Se asumirá que crear un Node es de O(1), ya que es un malloc y 2 dos asignaciones de variables.
LinkedList* linkedlist_init() {
LinkedList* list = malloc(sizeof(LinkedList)); // O(1) malloc
list->head = NULL; // O(1) asignacion
list->tail = NULL; // O(1) asignacion
list->datasize = 0; // O(1) asignacion
return list; // O(1) return
}Cada linea es O(1) y no hay iteraciones. La operación es O(1).
void linkedlist_append(LinkedList* list, int element) {
Node* node = node_init(element); // O(1)
if (list->datasize == 0) { // O(1)
list->head = node; // O(1)
list->tail = node; // O(1)
}
else {
list->tail->next = node; // O(1)
list->tail = node; // O(1)
}
list->datasize++; // O(1)
}Como cada operación es O(1) y no tiene iteraciones, la operación tiene un costo total de O(1).
void linkedlist_insert(LinkedList* list, int element, int position) {
if (position > list->datasize) { // O(1) comparacion
printf("No existe la posicion %d\n", position); // O(1) printf
}
else {
Node* aux = list->head; // O(1) asignacion
Node* node = node_init(element); // O(1) asignacion
for (int i=1; i<position; i++) { // O(1) cada iteracion
aux = aux->next; // O(1) asignacion
}
Node* aux2= aux->next; // O(1) asignacion
aux->next = node; // O(1) asignacion
node->next = aux2; // O(1) asignacion
list->datasize++; // O(1) asignacion ++
}
}Cada operación es O(1) y el for se repite a lo más ~n veces. La función es O(n).
int linkedlist_delete(LinkedList* list, int position) {
Node* aux = list->head; // O(1) asignacion ++
for (int i=1; i<position; i++) { // O(1) cada iteracion
aux = aux->next; // O(1) asignacion
}
Node* node = aux->next; // O(1) asignacion
Node* aux2 = node->next; // O(1) asignacion
aux->next = aux2; // O(1) asignacion
int element = node->value; // O(1) asignacion
free(node); // O(1) free
list->datasize--; // O(1) asignacion --
return element; // O(1) return
}Todo es O(1) excepto el for, que se repite a lo mas ~n veces, siendo n la cantidad de elementos de la lista. Por esto, la funcion es O(n).
int linkedlist_get(LinkedList* list, int position) {
if (position >= list->datasize) { // O(1) comparacion
printf("No existe la posicion %d", position); // O(1) printf
return -1; // O(1) return
}
Node* node = list->head; // O(1) asignacion
for (int i=0; i<position; i++) { // O(1) cada iteracion
node = node->next; // O(1) asignacion
}
return node->value; // O(1) return
}En el peor de los casos se recorre la lista entera, pasando de nodo a nodo, por lo que el for se repite ~n veces. La función es O(n).
void linkedlist_destroy(LinkedList* list) {
Node* node = list->head; // O(1) asignacion
Node* next = node->next; // O(1) asignacion
for (int i=2; i<list->datasize; i++) { // O(1) cada iteracion
free(node->next); // O(1) free
free(node); // O(1) free
node = next; // O(1) asignacion
next = next->next; // O(1) asignacion
}
free(next); // O(1) free
free(list->head); // O(1) free
free(list->tail); // O(1) free
free(list); // O(1) free
list = NULL; // O(1) asignacion
}Todo es O(1), pero el for son ~n iteraciones, siendo n = datasize. Por lo tanto, la función es O(n).
void linkedlist_concatenate(LinkedList* list, LinkedList* list2) {
list->tail->next = list2->head; // O(1) asignacion
list->tail = list2->tail; // O(1) asignacion
list->datasize += list2->datasize; // O(1) asignacion suma
free(list2); // O(1) free
}La función claramente es O(1).
| Nombre operación | ArrayList | LinkedList |
|---|---|---|
| init | O(1) | O(1) |
| append | O(n)/O(1) | O(1) |
| get | O(1) | O(n) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
| concatenate | O(n) | O(1) |
| destroy | O(1) | O(n) |
En cada gráfico, el eje x representa la cantidad de datos que habían en la estructura. El eje y representa el tiempo que se demoró en realizar la operación de dicho gráfico.
Ambas estructuras tienen sus ventajas si se comparan. Por ejemplo, si se va a estar haciendo get constantemente, probablemente es mejor utilizar un ArrayList. En cambio, si se quiere concatenar datos de listas varias veces, va a ser mejor usar LinkedList. También, si se va a estar usando destroy seguido, conviene usar ArrayList.
Lo anterior son simplemente conclusiones por la teoría, dado el costo analítico que tienen las operaciones.
Se utilizó valgrind para probar que no hubieran leaks. La manera de hacer esto era crear una estructura con unos cuantos datos dentro de ella (no más de 10, ya que no era necesario) y utilizar cada operación creada, en los distintos escenarios posibles.
En un principio había un problema con las linkedlists, pero se solucionó, ya que gracias a valgrind me di cuenta que no estaba haciéndole free al penúltimo nodo, en ningún caso. Se arregló simplemente haciendo free(node) justo después de que se acabara el for que liberaba todos los nodos excepto ese. Yo antes de usar valgrind pensaba que estaban funcionando perfectamente mis estructuras, ya que todo se veía bien y el leak no se podía observar. Después de hacer ese arreglo a linkedlist_destroy, creo que sí está funcionando 100% como debería.