El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

En aquest tema, explorarem com podem optimitzar l'ús de la memòria en els nostres algorismes per millorar el rendiment i l'eficiència del codi. L'ús eficient de la memòria és crucial en aplicacions on els recursos són limitats o quan es treballa amb grans volums de dades.

Conceptes Clau

Gestió de Memòria

Memòria Dinàmica vs. Memòria Estàtica: La memòria estàtica es reserva en temps de compilació, mentre que la memòria dinàmica es reserva en temps d'execució.
Heap i Stack: El stack s'utilitza per a l'assignació de memòria automàtica, mentre que el heap s'utilitza per a l'assignació dinàmica de memòria.

Estructura de Dades Eficients

Arrays vs. Llistes Enllaçades: Els arrays tenen un accés ràpid a elements, però les llistes enllaçades són més eficients per a insercions i eliminacions.
Hash Tables: Proporcionen un accés ràpid a elements, però poden requerir més memòria per evitar col·lisions.

Algorismes d'Assignació de Memòria

First Fit, Best Fit, Worst Fit: Estratègies per assignar blocs de memòria en el heap.
Garbage Collection: Mecanismes per recuperar memòria no utilitzada.

Estratègies per Optimitzar l'Ús de Memòria

Evitar la Duplicació de Dades

Referències en lloc de còpies: Utilitzar referències a objectes en lloc de copiar-los pot estalviar molta memòria.
Intercanvi de Memòria: Compartir memòria entre estructures de dades quan sigui possible.

Utilitzar Estructures de Dades Adequades

Estructures de Dades Compactes: Utilitzar estructures de dades que ocupin menys espai, com ara bitsets en lloc de arrays de booleans.
Estructures de Dades Dinàmiques: Utilitzar estructures que creixin o es redueixin segons sigui necessari, com ara vectors dinàmics.

Optimització de Codi

Inlining de Funcions: Evitar la sobrecàrrega de crides a funcions petites.
Reutilització de Memòria: Reutilitzar memòria ja assignada en lloc de fer noves assignacions.

Exemples Pràctics

Exemple 1: Ús de Bitsets

# Ús de bitsets per representar un conjunt de valors booleans
from bitarray import bitarray

# Crear un bitset de 10 elements
bitset = bitarray(10)
bitset.setall(False)

# Establir alguns valors a True
bitset[2] = True
bitset[5] = True

print(bitset)

Exemple 2: Reutilització de Memòria en Python

# Reutilització de memòria amb arrays
import numpy as np

# Crear un array de 1000 elements
array = np.zeros(1000)

# Reutilitzar l'array en lloc de crear-ne un de nou
for i in range(1000):
    array[i] = i

print(array)

Exercicis Pràctics

Exercici 1: Optimització de Memòria amb Llistes Enllaçades

Implementa una llista enllaçada en Python i compara el seu ús de memòria amb un array de la mateixa mida.

Exercici 2: Reducció de Memòria en Algorismes de Cerca

Implementa una taula de hash per a un algorisme de cerca i compara l'ús de memòria amb una cerca lineal en un array.

Solucions

Solució a l'Exercici 1

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

# Crear una llista enllaçada i un array
linked_list = LinkedList()
array = []

# Afegir 1000 elements a cada estructura
for i in range(1000):
    linked_list.append(i)
    array.append(i)

# Comparar l'ús de memòria
import sys
print(f"Memòria utilitzada per la llista enllaçada: {sys.getsizeof(linked_list)} bytes")
print(f"Memòria utilitzada per l'array: {sys.getsizeof(array)} bytes")

Solució a l'Exercici 2

# Implementació de la taula de hash
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index] = value

    def search(self, key):
        index = self.hash_function(key)
        return self.table[index]

# Crear una taula de hash i un array
hash_table = HashTable(1000)
array = [None] * 1000

# Inserir 1000 elements a cada estructura
for i in range(1000):
    hash_table.insert(i, i)
    array[i] = i

# Comparar l'ús de memòria
print(f"Memòria utilitzada per la taula de hash: {sys.getsizeof(hash_table.table)} bytes")
print(f"Memòria utilitzada per l'array: {sys.getsizeof(array)} bytes")

Conclusió

En aquesta secció, hem explorat diverses estratègies per optimitzar l'ús de memòria en els nostres algorismes. Hem après sobre la gestió de memòria, l'ús d'estructures de dades eficients i algorismes d'assignació de memòria. També hem vist exemples pràctics i exercicis per aplicar aquests conceptes. Amb aquestes tècniques, podem millorar significativament el rendiment i l'eficiència dels nostres programes.

Ús Eficient de Memòria