¿Cómo puedo vectorizar este orden de conteo de python para que sea absolutamente tan rápido como puede ser?

Estoy tratando de escribir un orden de conteo en python para vencer al timsort incorporado en ciertas situaciones. En este momento supera la función ordenada incorporada, pero solo para arreglos muy grandes (1 millón de enteros de longitud y más, no he probado más de 10 millones) y solo para un rango no mayor a 10,000. Además, la victoria es estrecha, con la clasificación por conteo solo ganando por un margen significativo en listas aleatorias específicamente diseñadas para ello.

He leído acerca de las asombrosas mejoras en el rendimiento que se pueden obtener al vectorizar el código Python, pero no entiendo particularmente cómo hacerlo o cómo podría usarse aquí. Me gustaría saber cómo puedo vectorizar este código para acelerarlo, y cualquier otra sugerencia de desempeño es bienvenida.

Versión más rápida actual solo para python y stdlibs:

from itertools import chain, repeat def untimed_countsort(unsorted_list): counts = {} for num in unsorted_list: try: counts[num] += 1 except KeyError: counts[num] = 1 sorted_list = list( chain.from_iterable( repeat(num, counts[num]) for num in xrange(min(counts), max(counts) + 1))) return sorted_list 

La manera más rápida de hacer esto por medio de un tiro LARGO es usar esta línea de una sola línea con números:

 def np_sort(unsorted_np_array): return numpy.repeat(numpy.arange(1+unsorted_np_array.max()), numpy.bincount(unsorted_np_array)) 

Esto se ejecuta entre 10 y 15 veces más rápido que la versión de python puro, y unas 40 veces más rápido que Timsort. Toma una matriz numpy y produce una matriz numpy.

Con numpy, esta función se reduce a lo siguiente:

 def countsort(unsorted): unsorted = numpy.asarray(unsorted) return numpy.repeat(numpy.arange(1+unsorted.max()), numpy.bincount(unsorted)) 

Esto se ejecutó unas 40 veces más rápido cuando lo probé en 100000 entradas aleatorias desde el intervalo [0, 10000). bincount realiza el conteo, y repeat bincount de conteos a un arreglo ordenado.

Sin pensar en tu algoritmo, esto te ayudará a deshacerte de la mayoría de tus bucles de python puros (que son bastante lentos) y a convertirlos en comprensiones o generadores (siempre más rápidos que los bloques normales). Además, si tiene que hacer una lista con todos los mismos elementos, la syntax de [x]*n es probablemente la forma más rápida de hacerlo. La sum se utiliza para aplanar la lista de listas.

 from collections import defaultdict def countsort(unsorted_list): lmin, lmax = min(unsorted_list), max(unsorted_list) + 1 counts = defaultdict(int) for j in unsorted_list: counts[j] += 1 return sum([[num]*counts[num] for num in xrange(lmin, lmax) if num in counts]) 

Tenga en cuenta que esto no está vectorizado, ni utiliza numpy.