{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": []
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"source": [
"# CC3001 Algoritmos y Estructuras de Datos\n",
"\n",
"**Auxiliares: Alonso Almendras, Albani Olivieri, Vicente Olivares, Ricardo Valdivia, Sebastián Acuña, Martín Paredes
\n",
"Profesores: Iván Sipirán, Nelson Baloian, Patricio Poblete **"
],
"metadata": {
"id": "ugyuRNpvHX-m"
}
},
{
"cell_type": "markdown",
"source": [
"##P1: Quicksort de Yaroslavskiy"
],
"metadata": {
"id": "t43IQcUl_XAe"
}
},
{
"cell_type": "markdown",
"source": [
"Se recomienda ver antes esta visualización de cómo funciona el quicksort Yaroslavskiy, pueden ir jugando y probando diferentes tipos de arreglos y ver que pasa en cada caso: https://learnforeverlearn.com/yaro_web/"
],
"metadata": {
"id": "iW1JwoBpifuN"
}
},
{
"cell_type": "code",
"source": [
"import numpy as np\n",
"\n",
"def quicksortYaro(arreglo, izq, der):\n",
" #Caso base, si el arreglo es de largo 1 o 0.\n",
"\t#En este caso no hacemos nada porque no queremos seguir la recursión\n",
"\tif izq >= der:\n",
"\t\tpass\n",
"\telse: #Caso en el que izq < der\n",
"\t\t#llamamos a una función auxiliar que nos realice una iteración del Quicksort\n",
" \t#Esta función auxiliar nos entrega la nueva posición del pivote izquierdo y del pivote derecho\n",
"\t\tpiv_izq, piv_der = particionYaro(arreglo, izq, der)\n",
"\t\t#Parte recursiva\n",
" #Primer segmento: valores menores a mi pivote izquierdo\n",
"\t\tquicksortYaro(arreglo, izq, piv_izq - 1)\n",
"\n",
" #Segundo segmento: valores entre medio de los dos pivotes\n",
"\t\tquicksortYaro(arreglo, piv_izq + 1, piv_der - 1)\n",
"\n",
" \t#Tercer segmento: valores mayores a mi pivote derecho\n",
"\t\tquicksortYaro(arreglo, piv_der + 1, der)\n",
"\n",
"\n",
"#Función auxiliar que realiza el la iteración de ordenar los valores\t\t\n",
"def particionYaro(arreglo, izq, der):\n",
"\t#Si el pivote de la izquierda es menor que el de la derecha los intercambiamos, pues queremos el menor pivote a la izquierda\n",
"\tif arreglo[izq] > arreglo[der]:\n",
"\t\tarreglo[izq], arreglo[der] = arreglo[der], arreglo[izq]\n",
"\t\t\n",
" #Tendremos 3 índices, los cuales dividirán las secciones del arreglo\n",
" # L: será el índice izquierdo\n",
" # C: será el índice central\n",
" # R: será el índice derecho\n",
"\n",
" #Entonces el invariante del arreglo sería de la siguiente forma, (sea P1 el pivote menor y P2 el pivote mayor)\n",
" # [ P2 ]\n",
" # L C R\n",
" #Condiciones iniciales\n",
"\tL = C = izq + 1\n",
"\tR = der - 1\n",
"\n",
" #Definimos los pivotes\n",
"\tpiv_izq, piv_der = arreglo[izq], arreglo[der]\n",
"\n",
" #Ponemos la condición de término, cuando el índice central \"alcanza\" el índice derecho,\n",
" #es decir, cuando el segmento incógnito queda vacío\n",
"\twhile C <= R:\n",
"\t\t# Caso en el que el elemento es menor que el pivote izquierdo\n",
"\t\tif arreglo[C] < piv_izq:\n",
"\t\t\tarreglo[C], arreglo[L] = arreglo[L], arreglo[C]\n",
"\t\t\tL += 1\n",
"\t\t# Caso en el que el elemento es mayor al pivote derecho\n",
"\t\telif arreglo[C] > piv_der:\n",
"\t\t\twhile arreglo[R] > piv_der and C < R:\n",
"\t\t\t\tR -= 1\n",
"\t\t\tarreglo[C], arreglo[R] = arreglo[R], arreglo[C]\n",
"\t\t\tR -= 1\n",
"\t\t\tif arreglo[C] < piv_izq:\n",
"\t\t\t\tarreglo[C], arreglo[L] = arreglo[L], arreglo[C]\n",
"\t\t\t\tL += 1\n",
" # En el caso en el que el elemento está entremedio de los 2 pivotes, no hacemos nuevos cambios\n",
" \t# Aumentamos el indice central para revisar el elemento siguiente\n",
"\t\tC += 1\n",
"\t\n",
" # Una vez terminada la iteración nos devolvemos una posición en el índice izquierdo y avanzamos una en el derecho\n",
"\tL -= 1\n",
"\tR += 1\n",
"\t\n",
"\t#Colocamos los pivotes en sus posiciones respectivas\n",
"\tarreglo[izq], arreglo[L] = arreglo[L], arreglo[izq]\n",
"\tarreglo[der], arreglo[R] = arreglo[R], arreglo[der]\n",
"\t\n",
"\t# Retornamos los índices de los pivotes\n",
"\treturn L, R"
],
"metadata": {
"id": "_oo6j9DBhP4T"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"Probamos el código (notar que el algoritmo funciona tanto para listas como para arreglos)"
],
"metadata": {
"id": "yZ2k2liArNCd"
}
},
{
"cell_type": "code",
"source": [
"a = [8,5,3,6,12,7,34,1]\n",
"quicksortYaro(a,0,7)\n",
"a"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "8Lj7GSqAfzJz",
"outputId": "0150a322-8dad-4348-e47e-bf53b661265a"
},
"execution_count": null,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"[1, 3, 5, 6, 7, 8, 12, 34]"
]
},
"metadata": {},
"execution_count": 2
}
]
},
{
"cell_type": "markdown",
"source": [
"Queremos ver ahora cómo se compara en rapidez el algoritmo recién creado versus el algoritmo de Quicksort tradicional. Para ello ocuparemos la librería `time`. "
],
"metadata": {
"id": "tR9kIeBlmM-_"
}
},
{
"cell_type": "code",
"source": [
"def quicksort(a):\n",
" qsort(a,0,len(a)-1)\n",
"\n",
"def qsort(a,i,j): # ordena a[i],...,a[j]\n",
" if ia[i]\n",
" for t in range(s,j):\n",
" if a[t+1]<=a[i]:\n",
" (a[s+1],a[t+1])=(a[t+1],a[s+1])\n",
" s=s+1\n",
" # mover pivote al centro\n",
" (a[i],a[s])=(a[s],a[i])\n",
" return s"
],
"metadata": {
"id": "nCkiwik-kX7q"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"import time\n",
"np.random.seed(8) # Se ocupa para fijar una semilla y replicar un proceso aleatorio\n",
"a = np.random.randint(0,100000,1000) #Extrae 50 números aleatorios entre 0 y 9999\n",
"t1 = time.clock_gettime_ns(0)\n",
"quicksortYaro(a, 0, 49)\n",
"t2 = time.clock_gettime_ns(0)\n",
"print(\"Quicksort de Yaroslavskiy: el tiempo que demoró el proceso fue de \",(t2-t1),\"nanosegundos\")"
],
"metadata": {
"id": "H15J45tKi5pM",
"outputId": "b273ae92-6b6d-4e94-a794-2555bd29c8f0",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Quicksort de Yaroslavskiy: el tiempo que demoró el proceso fue de 314625 nanosegundos\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"np.random.seed(8) # Reiniciamos la semilla para extraer los mismos 50 elementos\n",
"a = np.random.randint(0,100000,1000)\n",
"t1 = time.clock_gettime_ns(0)\n",
"quicksort(a)\n",
"t2 = time.clock_gettime_ns(0)\n",
"print(\"Quicksort normal: el tiempo que demoró el proceso fue de \",(t2-t1),\"nanosegundos\")"
],
"metadata": {
"id": "ywPFxs4QkiWF",
"outputId": "1ecf096a-1145-4bce-8e22-1b749f65bd13",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Quicksort normal: el tiempo que demoró el proceso fue de 11358913 nanosegundos\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"Se puede observar que con un arreglo de 1000 elementos, el algoritmo de Yaroslavskiy ya supera a la versión original por una cantidad considerable de tiempo.\n",
"\n",
"**Ejercicio:** probar con tamaños más grandes y graficar resultados."
],
"metadata": {
"id": "Bw-l8srJmjXd"
}
},
{
"cell_type": "markdown",
"source": [
"## P2: Hashing\n",
"\n"
],
"metadata": {
"id": "hWBX7kgqtj4A"
}
},
{
"cell_type": "code",
"source": [
"!pip install aed_utilities\n",
"import aed_utilities as aed\n",
"import numpy as np"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "hfRPW3YnO04k",
"outputId": "14a86dba-2bf0-4aa6-d9fd-64a3fc654689"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
"Collecting aed_utilities\n",
" Downloading aed_utilities-0.5.6.tar.gz (4.3 kB)\n",
" Preparing metadata (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
"Collecting validators (from aed_utilities)\n",
" Downloading validators-0.20.0.tar.gz (30 kB)\n",
" Preparing metadata (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
"Requirement already satisfied: beautifulsoup4 in /usr/local/lib/python3.10/dist-packages (from aed_utilities) (4.11.2)\n",
"Requirement already satisfied: soupsieve>1.2 in /usr/local/lib/python3.10/dist-packages (from beautifulsoup4->aed_utilities) (2.4.1)\n",
"Requirement already satisfied: decorator>=3.4.0 in /usr/local/lib/python3.10/dist-packages (from validators->aed_utilities) (4.4.2)\n",
"Building wheels for collected packages: aed_utilities, validators\n",
" Building wheel for aed_utilities (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
" Created wheel for aed_utilities: filename=aed_utilities-0.5.6-py3-none-any.whl size=4542 sha256=e06ab2c86b85ce039f33e5e2080c2be3950f13d28d35affbc314e3fa49a3e7ce\n",
" Stored in directory: /root/.cache/pip/wheels/db/6d/39/cc766f956b1e504722228ad30c8154cd48f4470e7e24dcfd0e\n",
" Building wheel for validators (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
" Created wheel for validators: filename=validators-0.20.0-py3-none-any.whl size=19579 sha256=5a48df56f376dfd87169043cf90960ac1f939e0a1753fb9fd4acf9757dc0b3d8\n",
" Stored in directory: /root/.cache/pip/wheels/f2/ed/dd/d3a556ad245ef9dc570c6bcd2f22886d17b0b408dd3bbb9ac3\n",
"Successfully built aed_utilities validators\n",
"Installing collected packages: validators, aed_utilities\n",
"Successfully installed aed_utilities-0.5.6 validators-0.20.0\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"class Nodo:\n",
" def __init__(self, x, sgte):\n",
" self.x = x\n",
" self.sgte = sgte\n",
" def __repr__(self):\n",
" return str(self.x)\n",
"\n",
"# Lista enlazada, inserción al inicio\n",
"class Lista:\n",
" def __init__(self):\n",
" self.primero = None\n",
" # \n",
" def dibujar(self):\n",
" lld = aed.LinkedListDrawer(fieldHeader=\"primero\", fieldData=\"x\",\n",
" fieldLink=\"sgte\")\n",
" lld.draw_linked_list(self)\n",
" def __repr__(self):\n",
" rep = f'{self.primero}'\n",
" if self.primero is not None and self.primero.sgte is not None:\n",
" rep += ' (+L)'\n",
" return rep\n",
" # \n",
" def insertar(self, val):\n",
" # haremos que la inserción sea al principio\n",
" self.primero = Nodo(val, self.primero)\n",
" def buscar(self, val):\n",
" lista = self.primero\n",
" while lista is not None:\n",
" if lista.x == val:\n",
" return lista.x\n",
" lista = lista.sgte\n",
" return None\n",
" def eliminar(self, val):\n",
" lista = self.primero\n",
" prev_lista = None\n",
" while lista is not None:\n",
" if lista.x == val:\n",
" if prev_lista is not None:\n",
" prev_lista.sgte = lista.sgte\n",
" else:\n",
" self.primero = self.primero.sgte\n",
" return\n",
" prev_lista = lista\n",
" lista = lista.sgte\n",
" raise ValueError(f'Valor a eliminar ({val}) no se encontraba en la celda')"
],
"metadata": {
"id": "TexF8MsK2tz3"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"class LinkedHashTable:\n",
" def __init__(self, m):\n",
" self.tabla = np.array([Lista() for _ in range(m)])\n",
" self.m = m\n",
" # \n",
" def dibujar(self):\n",
" dr = aed.NumpyArrayDrawer()\n",
" dr.drawNumpy1DArray(self.tabla, showIndex=True)\n",
" def dibujar_celda(self, i):\n",
" self.tabla[i].dibujar()\n",
" # \n",
" def hash(self, val):\n",
" return val % self.m\n",
" def buscar(self, val):\n",
" pos = self.hash(val)\n",
" celda = self.tabla[pos]\n",
" return celda.buscar(val)\n",
" def insertar(self, val):\n",
" pos = self.hash(val)\n",
" celda = self.tabla[pos]\n",
" if celda.buscar(val) is not None:\n",
" raise ValueError(f'El valor {val} ya está en la tabla')\n",
" celda.insertar(val)\n",
" def eliminar(self, val):\n",
" pos = self.hash(val)\n",
" celda = self.tabla[pos]\n",
" celda.eliminar(val)"
],
"metadata": {
"id": "7uFzOQ8XzEhx"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"valores = [47, 7, 24, 13, 17, 37, 54]\n",
"\n",
"hta = LinkedHashTable(10)\n",
"for x in valores:\n",
" print('Insertando el', x)\n",
" hta.insertar(x)\n",
" hta.dibujar()\n",
" pos = hta.hash(x)\n",
" if hta.tabla[pos].primero.sgte is not None: # Hay más valores en la celda\n",
" print('Lista enlazada de la celda', pos)\n",
" hta.dibujar_celda(pos)\n",
" print('-'*30)"
],
"metadata": {
"id": "MDelXYYhzHIs",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"outputId": "72e543b9-abda-44c7-a66a-3a2664eabfec"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Insertando el 47\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 7\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"Lista enlazada de la celda 7\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 24\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 13\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 17\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"Lista enlazada de la celda 7\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 37\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"Lista enlazada de la celda 7\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 54\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"Lista enlazada de la celda 4\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"def hash_b(self, val):\n",
" return (3*val % 19) % self.m\n",
"LinkedHashTable.hash = hash_b # cambiando el método a la mala\n",
"htb = LinkedHashTable(10)\n",
"\n",
"for x in valores:\n",
" print('Insertando el', x)\n",
" htb.insertar(x)\n",
" htb.dibujar()\n",
" pos = htb.hash(x)\n",
" if htb.tabla[pos].primero.sgte is not None: # Hay más valores en la celda\n",
" print('Lista enlazada de la celda', pos)\n",
" htb.dibujar_celda(pos)\n",
" print('-'*30)"
],
"metadata": {
"id": "Wy6VpQD8zJ6X",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"outputId": "37da551d-35e5-4cf6-c747-7e544316c5d6"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Insertando el 47\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 7\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 24\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 13\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 17\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 37\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 54\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"class DoubleHashTable:\n",
" def __init__(self, m):\n",
" self.tabla = ''*np.ones(m, dtype=object)\n",
" self.m = m\n",
" def hash_base(self, x):\n",
" return x \n",
" def step(self, x):\n",
" return 2\n",
" def hash(self, x, i):\n",
" return (self.hash_base(x) + self.step(x)*i) % self.m\n",
" def dibujar(self):\n",
" dr = aed.NumpyArrayDrawer()\n",
" dr.drawNumpy1DArray(self.tabla, showIndex=True)\n",
" def buscar(self, x):\n",
" for i in range(self.m):\n",
" idx = self.hash(x, i)\n",
" en_tabla = self.tabla[idx]\n",
" if en_tabla == x:\n",
" print('Encontrado')\n",
" return x\n",
" elif en_tabla == '':\n",
" print('No estaba')\n",
" return False\n",
" print(f'[h_{i} = {idx} colisionó]')\n",
" def insertar(self, x):\n",
" for i in range(self.m):\n",
" idx = self.hash(x, i)\n",
" print(f'[Probando con h_{i} = {idx}]')\n",
" if self.tabla[idx] == '':\n",
" self.tabla[idx] = x\n",
" print('[Insertado]')\n",
" return\n",
" print('[No quedan espacios (o `step` no es exhaustivo)!]')"
],
"metadata": {
"id": "djXjdNhR1LSn"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"htc = DoubleHashTable(11)\n",
"\n",
"for x in valores:\n",
" print('Insertando el', x)\n",
" htc.insertar(x)\n",
" htc.dibujar()\n",
" print('-'*30)"
],
"metadata": {
"id": "ei7opCu61NtY",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"outputId": "faa89fb0-697f-454c-9f62-a59e6f8eae0a"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Insertando el 47\n",
"[Probando con h_0 = 3]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 7\n",
"[Probando con h_0 = 7]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 24\n",
"[Probando con h_0 = 2]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 13\n",
"[Probando con h_0 = 2]\n",
"[Probando con h_1 = 4]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 17\n",
"[Probando con h_0 = 6]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 37\n",
"[Probando con h_0 = 4]\n",
"[Probando con h_1 = 6]\n",
"[Probando con h_2 = 8]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n",
"Insertando el 54\n",
"[Probando con h_0 = 10]\n",
"[Insertado]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
""
],
"image/svg+xml": ""
},
"metadata": {}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"------------------------------\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## P3: Cuckoo hashing\n",
"\n",
"Implementamos la clase CuckooHashing con los métodos para realizar búsqueda, inserción y eliminación de llaves."
],
"metadata": {
"id": "RMGGMxj6qCHa"
}
},
{
"cell_type": "code",
"source": [
"import random as rd\n",
"\n",
"class Node():\n",
" def __init__(self, key, info):\n",
" self.key = key\n",
" self.info = info\n",
"\n",
" def __str__(self):\n",
" return \"(\" + str(self.key) + \", \" + str(self.info) + \")\"\n",
"\n",
"class CuckooHashing():\n",
"\n",
" def __init__(self, size):\n",
" # Creamos 2 arreglos con la mitad del tamaño cada 1\n",
" self.array1 = [None] * (size // 2)\n",
" self.array2 = [None] * (size // 2)\n",
" # Guardamos el total de nodos\n",
" self.nodos = 0\n",
" self.size = size\n",
"\n",
" def lenHash(self):\n",
" return self.nodos\n",
"\n",
" def reHash(self, size):\n",
" # Creamos un nuevo cuckoo hashing\n",
" temp = CuckooHashing(size)\n",
"\n",
" # Recorremos las dos tablas del hash original\n",
" for i in range(self.size // 2):\n",
" x = self.array1[i]\n",
" y = self.array2[i]\n",
" # insertamos los objetos en el nuevo en cada caso \n",
" if x != None:\n",
" temp.insert(x.key, x.info)\n",
" if y != None:\n",
" temp.insert(y.key, y.info)\n",
"\n",
" # Redefinimos nuestro hash con el nuevo que creamos\n",
" self.array1 = temp.array1\n",
" self.array2 = temp.array2\n",
" self.nodos = temp.nodos\n",
" self.size = temp.size\n",
"\n",
" # Aumentamos al doble el tamaño de nuestro hash\n",
" def aumentarTamanno(self):\n",
" newSize = self.size * 2\n",
" # realizamos nuevamente el hashing en la tabla\n",
" # con el nuevo tamaño\n",
" self.reHash(newSize)\n",
" \n",
" # Retornamos la info si es que esta\n",
" def find(self, k):\n",
" pos1, pos2 = self.hashFunc(k) \n",
" x = self.array1[pos1] \n",
" y = self.array2[pos2] \n",
" if x != None and x.key == k:\n",
" return x.info\n",
" if y != None and y.key == k:\n",
" return y.info\n",
" # Retornamos None si es que no se encontraba \n",
" return None\n",
"\n",
" def hashFunc(self, s):\n",
" x = hash(s) \n",
" y = hash(x)\n",
"\n",
" size = self.size // 2\n",
" return x % size, y % size\n",
" \n",
" # Eliminamos el nodo asociado a la llave k\n",
" def delete(self, k):\n",
" pos1, pos2 = self.hashFunc(k) \n",
" x = self.array1[pos1]\n",
" y = self.array2[pos2]\n",
" if x != None and x.key == k:\n",
" self.array1[pos1] = None\n",
" elif y != None and y.key == k:\n",
" self.array2[pos2] = None\n",
" else:\n",
" return False # No se encontro esa key para eliminar\n",
" self.nodos -= 1 \n",
" return True # se logro exitosamente la eliminación\n",
"\n",
" # inserta y retorna true si logra realizar la inserción\n",
" # Falso si es que la llave ya esta, aumenta el tamaño de la tabla de ser\n",
" # necesario\n",
" def insert(self, key, info):\n",
" # Si ya se encuentra, retornamos Falso, no tendremos duplicados\n",
" if self.find(key) != None:\n",
" return False \n",
" \n",
" # Creamos un nodo con lo que queremos insertar\n",
" n = Node(key, info)\n",
"\n",
" if self.nodos >= (self.size // 2):\n",
" self.aumentarTamanno() \n",
"\n",
" pos1, pos2 = self.hashFunc(n.key) # hash\n",
"\n",
" pos = pos1\n",
" table = self.array1\n",
"\n",
" for i in range(5):\n",
" if table[pos] == None: # Esta vacio, insertamos\n",
" table[pos] = n\n",
" self.nodos += 1\n",
" return True\n",
" \n",
" # intercambiamos los nodos, entre el que ya esta\n",
" # por el que queremos poner\n",
" n, table[pos] = table[pos], n\n",
"\n",
" # Para la siguiente iteración tratamos de poner el nodo\n",
" # en el array que no se ha considerado\n",
" if pos == pos1:\n",
" pos1, pos2 = self.hashFunc(n.key)\n",
" pos = pos2\n",
" table = self.array2\n",
" else:\n",
" pos1, pos2 = self.hashFunc(n.key)\n",
" pos = pos1\n",
" table = self.array1\n",
" \n",
" # Si terminado el ciclo no se logro insertar\n",
" # aumentamos el tamaño, rehasheamos\n",
" # y volvemos a realizar el proceso de inserción\n",
" self.aumentarTamanno()\n",
" self.reHash(self.size)\n",
" self.insert(n.key, n.info)\n",
" return True\n",
" \n"
],
"metadata": {
"id": "b6emzscjv-11"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"Ahora testeamos nuestra clase en conjunto con sus métodos"
],
"metadata": {
"id": "41YjOammVCPj"
}
},
{
"cell_type": "code",
"source": [
"# test para probar nuestra implementación \n",
"\n",
"def test():\n",
" size = 100\n",
" missing = 0\n",
" found = 0 \n",
" \n",
" # creamos una tabla hash con un número inicialmente pequeño de espacios\n",
" c = CuckooHashing(100)\n",
" \n",
" # Ahora insertamos n pares de clave/info (n=size) \n",
" inserted = 0\n",
" for i in range(size): \n",
" if c.insert(i, i):\n",
" inserted += 1\n",
" print(inserted, \"nodos fueron insertados exitosamente\")\n",
" \n",
" \n",
" # Nos aseguramos de que todos los pares clave/info que hemos insertado se\n",
" # pueden encontrar en la tabla hash. Esto nos confirma que al redimensionar \n",
" # el número de cubos no se perdieron algunos pares clave/datos.\n",
" for i in range(size):\n",
" ans = c.find(i)\n",
" if ans == None or ans != i:\n",
" print(\"No se encontró la llave\", str(i))\n",
" missing += 1\n",
" \n",
" print(missing, \"llaves no se encontraron en el hash Cuckoo\")\n",
" \n",
" # Ahora eliminamos todas las llaves \n",
" for i in range(size): \n",
" c.delete(i)\n",
" \n",
" for i in range(size): \n",
" ans = c.find(i) \n",
" if ans != None or ans == i: \n",
" print(\"No se pudo eliminar la llave\", str(i)) \n",
" found += 1\n",
" print(found, \"llaves no se borraron en el hash Cuckoo\") \n",
"\n",
"def __main():\n",
" test()\n",
" \n",
"if __name__ == '__main__':\n",
" __main() \n"
],
"metadata": {
"id": "6AoWLbkJjanu",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "3c7b90d1-5d3f-4040-ba73-5d13f169c7da"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"100 nodos fueron insertados exitosamente\n",
"0 llaves no se encontraron en el hash Cuckoo\n",
"0 llaves no se borraron en el hash Cuckoo\n"
]
}
]
}
]
}