0

Estoy intentando crear una función en Python en la que implemente el método de ordenación MergeSort y además muestre en pantalla el tiempo de ejecución. Lo intenté así:

    def algMergeSort(vector):
    print("Aquí inicia el algoritmo de MergeSort")
    mitad = int(len(vector) / 2)
    tiempo_inicial = time()

    if len(vector) > 1:
        l = vector[mitad:]
        r = vector[:mitad]

        vector.clear()

        algMergeSort(l)
        algMergeSort(r)

        while len(l) > 0 and len(r) > 0:
            if l[0] < r[0]:
                vector.append(l.pop(0))
            else:
                vector.append(r.pop(0))

        while len(l) > 0:
            vector.append(l.pop(0))

        while len(r) > 0:
            vector.append(r.pop(0))
    tiempo_final = time()
    tiempo_ejecucion = tiempo_final - tiempo_inicial
    print("Tiempo de ejecución: ", tiempo_ejecucion)

    print("Aquí termina el algoritmo de MergeSort")

El punto es que al llamarla, pasarle como parámetro un vector ya establecido e imprimir en pantalla el vector efectivamente se ordena, pero la función se ejecuta de forma recursiva con todo y time(), lo que me da un resultado como este:

introducir la descripción de la imagen aquí

Habrá alguna forma de medir el tiempo de ejecución dentro de la función cuando ésta es recursiva sin que entre directamente en la recursión?

Gracias de antemano.

1 respuesta 1

2

Usa una función que sea la encargada de medir el tiempo. Puedes hacer que sea una función que reciba los siguientes parámetros:

  1. La función que quieres medir (func).
  2. Los argumentos posicionales de func (*args).
  3. Los argumentos keywords de func (*kwargs).

También te aconsejo que uses el módulo timeit, el cual hace que puedas desacoplar la lógica de la medida del tiempo de la lógica de tu función como tal. Además arroja datos bastante precisos y es muy customizable, lo que te permite hacer benchmarkings.

Tu función

def algMergeSort(vector):
    mitad = int(len(vector) / 2)

    if len(vector) > 1:
        l = vector[mitad:]
        r = vector[:mitad]

        vector.clear()

        algMergeSort(l)
        algMergeSort(r)

        while len(l) > 0 and len(r) > 0:
            if l[0] < r[0]:
                vector.append(l.pop(0))
            else:
                vector.append(r.pop(0))

        while len(l) > 0:
            vector.append(l.pop(0))

        while len(r) > 0:
            vector.append(r.pop(0))

Función para medir el tiempo

def measure_time(func, *args, **kwargs):
    globals_ = {'func': func, 'args': args, 'kwargs': kwargs}
    time = timeit('func(*args, **kwargs)',
                  number=1,
                  globals=globals_)
    return f"{time} seconds"

Uso

measure_time(algMergeSort, [4, 2, 5, 1])

output

'7.719616393073942e-05 seconds'

PD: No te olvides de importar timeit. (from timeit import timeit)

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.