Algoritmo para ordenar enteros

Una de las tareas más frecuentes cuando trabajas con datos es «ordenar» una serie o varias de datos. Así que como primer reto vas a intentar programar tu propia función para ordenar en este caso una serie de números enteros. Seguramente nunca más intentarás diseñar tu propio algoritmo para ordenar datos, encontrarás múltiples funciones en las librerías de Python que uses capaces de resolver esta tarea. Pero intentarlo tu desde cero te hará comprender el valor y el esfuerzo que hay detrás de herramientas tan comunes usadas de manera tan «alegre».

Tarea

Haz una función de Python llamada sort con un único argumento de entrada llamado numbers. La función deberá regresar la lista de números enteros que recibió como entrada (numbers) en orden de menor a mayor. Debes de tener en cuenta las siguientes condiciones:

• la lista contendrá \(10^7\) números enteros positivos en el rango \([0, 10^8)\).

• no tienes límite de recursos (memoria, número de cpus, etc.) a usar para conseguir que tu algoritmo sea eficiente.

• el algoritmo lo debes implementar haciendo uso de la sintaxis básica de Python -NO vale hacer uso de funciones ya programadas para ordenar que puedes encontrar en Numpy, Pandas, Scipy, etc-.

Esta es la lista de números que debes ordenar:

import numpy as np

rng = np.random.default_rng(333)
input_random_numbers = rng.integers(low=0, high=10**8, size=10**7)

print(input_random_numbers)

[30054056 91900182 41637891 ...  5150345 25101977 61734715]

Ahora es tu turno escribir tu función para ordenar esa lista:

### Propuesta de los tutores del taller ###

def sort(numbers):

    sorted_numbers = []
    
    frequency = np.zeros((10**8), dtype=np.int64)

    for ii in numbers:
        frequency[ii]+=1

    ii=0
    for ff in frequency:
        if ff>0:
            for jj in range(ff):
                sorted_numbers.append(ii)
        ii+=1

    return sorted_numbers

¿Ya tienes una propuesta que funciona? Genial! ¿Puedes calcular cuanto espacio en memoria ocupa el numpy.array input_random_numbers? O dicho de otra manera… ¿Cuanta memoria consumen \(10^7\) enteros?

### Propuesta de los tutores del taller ###

print(f"{round(input_random_numbers.nbytes/1024/1024, 2)} megabytes")

76.29 megabytes

¿Y puedes calcular cuanto tiempo le cuesta a tu función ordenar los \(10^7\) enteros de input_random_numbers?

%%time
### Propuesta de los tutores del taller ###
sorted_numbers = sort(input_random_numbers)

CPU times: user 22.2 s, sys: 919 ms, total: 23.1 s
Wall time: 23.1 s

Ahora si, prueba por ejemplo la función sort de la librería Numpy y calcula cuanto tiempo menos le cuesta a ella que a tu función:

%%time
sorted_numbers = np.sort(input_random_numbers)

CPU times: user 1.2 s, sys: 40 ms, total: 1.24 s
Wall time: 1.24 s

¿Por qué crees que es más rápida?

La función sort de Numpy es un algoritmo más eficiente en el consumo de recursos. Pero el motivo por el cual es más rápido es principalmente que la función no está escrita en Python sino en un lenguaje que permite tener una versión compilada del algoritmo y hacer uso de ella (probablemente C o Fortran).

Veamos a continuación cómo podemos acercarnos a esos tiempos sin necesidad de cambiar de lenguaje ni de algoritmo.

import numba as nb

@nb.njit(nb.int64[:](nb.int64[:]))
def sort(numbers):

    sorted_numbers = []
    
    frequency = np.zeros((10**8), dtype=np.int64)

    for ii in numbers:
        frequency[ii]+=1

    ii=0
    for ff in frequency:
        if ff>0:
            for jj in range(ff):
                sorted_numbers.append(ii)
        ii+=1

    return np.array(sorted_numbers, dtype=np.int64)

%%time
### Propuesta de los tutores del taller ###
sorted_numbers = sort(input_random_numbers)

CPU times: user 442 ms, sys: 256 ms, total: 698 ms
Wall time: 694 ms

Nota

Échale un ojo a herramientas como Numba o Cython si quieres acelerar tu código programado en Python. Si tienes nociones de programación en C, puede ser buena idea que veas las herramientas disponibles para invocar código compilado en C desde Python.