No tienes acceso a esta clase

¬°Contin√ļa aprendiendo! √önete y comienza a potenciar tu carrera

Aprende todo un fin de semana sin pagar una suscripci√≥n ūüĒ•

Aprende todo un fin de semana sin pagar una suscripci√≥n ūüĒ•

Regístrate

Comienza en:

4D
0H
54M
58S

Calculando la complejidad de algoritmos

8/11
Recursos

Aportes 2

Preguntas 0

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad?

o inicia sesión.

Vaya, en un curso anterior no entendí como funcionaban esos algoritmo, pero ahora si lo s estoy entendiendo y son brillantes.

He realizado la implementación de la estructura de dato: Queue utilizando Python, la construí utilizando listas y una segunda versión utilizando arrays de la librería numpy para poder compararlos:
 
 

Codigo que implementa Queue utilizando listas de python:

(el archivo lo nombre como queue_with_lists.py)
 
 

from bokeh.plotting import figure, output_file, show
import random
import time

def de_queue(data, items):
    if(data['front'] == -1):
        print("Our queue is empty")
    else:
        print(f"The value {items[data['front']]} was removed")
        items.pop(data['front'])
        if len(items):
            data['rear'] -= 1
        else:
            data['front'] = data['rear'] = -1


def en_queue(value, data, items, SIZE):
    if data['rear'] == SIZE - 1:
        print("Our Queue is full")
    else:
        if data['front'] == -1:
            data['front'] = 0
        data['rear'] += 1
        items.append(value)


def run(SIZE):
    items = []
    data = {
        'front': -1,
        'rear': -1
    }
    numbers_to_insert = SIZE
    numbers = [random.randint(0, 100) for i in range(numbers_to_insert)]

    start = time.time()
    for number in numbers:
        en_queue(number, data, items, SIZE)
    end = time.time()
    elapsed_time = end - start
    return elapsed_time


if __name__ == '__main__':
    output_file('simple_graphic.html')
    fig = figure()
    SIZE = 5 # limite de elementos para la cola

    times = []
    init_number = 100000
    final_number = 1000000
    step = 100000
    data_sets = range(init_number, final_number, step) # this is my X axis

    for data_set in data_sets:
        times.append(run(data_set))

    fig.line(list(data_sets), times, line_width=2)
    show(fig)

    print(data_sets)
    print(times)

 
 

Código donde implemento Queue utilizando arrays de librería numpy

 
 

from bokeh.plotting import figure, output_file, show
from queue_with_lists import en_queue, run
import random
import numpy as np
import time

def de_queue(data, items):
    if(data['front'] == -1):
        print("Our queue is empty")
    else:
        print(f"The value {items[data['front']]} was removed")
        indices = list(range(0,items.size - 1))
        values = items[1:items.size]
        np.put(items, indices, values)

        if data['rear']:
            data['rear'] -= 1
        else:
            data['front'] = data['rear'] = -1

def en_queue_arr(number, data, items, SIZE):
    if data['rear'] == SIZE - 1:
        print("Our Queue is full")
    else:
        if data['front'] == -1:
            data['front'] = 0
        data['rear'] += 1
        items[data['rear']] = number


def np_arrays(SIZE):
    items = np.empty(SIZE)
    data = {
        'front': -1,
        'rear': -1
    }
    numbers_to_insert = SIZE
    numbers = [random.randint(0, 100) for i in range(numbers_to_insert)]

    start = time.time()
    for number in numbers:
        en_queue_arr(number, data, items, SIZE)
    end = time.time()
    elapsed_time = end - start
    return elapsed_time

if __name__ == '__main__':
    output_file('simple_graphic.html')
    fig = figure()
    SIZE = 5 # limite de elementos para la cola

    times = []
    times_list = []
    init_number = 100000
    final_number = 10000000
    step = 100000
    data_sets = range(init_number, final_number, step) # this is my X axis

    for data_set in data_sets:
        times.append(np_arrays(data_set))
        times_list.append(run(data_set))

    fig = figure(title="Array vs Linked List - Queue", x_axis_label='Cantidad de elementos en cola', y_axis_label='Tiempo')
    fig.line(list(data_sets), times, legend_label="Arrays", color="blue", line_width=2)
    fig.line(list(data_sets), times_list, legend_label="Linked Lists", color="orange", line_width=2)
    show(fig)

 
 

Gr√°fica con los resultados:

(la comparación es al insertar a la Queue hasta 10 millones de datos)