[ Última actualización: programa de referencia y resultados preliminares disponibles, ver más abajo]
Por lo tanto, quiero probar la compensación de velocidad / complejidad con una aplicación clásica: la clasificación.
Escriba una función ANSI C que clasifique una matriz de números de coma flotante en orden creciente .
No se puede utilizar cualquier bibliotecas, llamadas al sistema, multithreading o ASM en línea.
Entradas juzgadas en dos componentes: longitud del código y rendimiento. Puntuación de la siguiente manera: las entradas se ordenarán por longitud (registro de # caracteres sin espacios en blanco, para que pueda mantener algo de formato) y por rendimiento (registro de # segundos sobre un punto de referencia), y cada intervalo [mejor, peor] se normaliza linealmente a [ 0,1]. El puntaje total de un programa será el promedio de los dos puntajes normalizados. La puntuación más baja gana. Una entrada por usuario.
La clasificación tendrá que (eventualmente) estar en su lugar (es decir, la matriz de entrada tendrá que contener los valores ordenados en el momento de la devolución), y debe usar la siguiente firma, incluidos los nombres:
void sort(float* v, int n) {
}
Caracteres a contar: aquellos en la sort
función, firma incluida, más funciones adicionales llamadas por él (pero sin incluir el código de prueba).
El programa debe manejar cualquier valor numérico float
y matrices de longitud> = 0, hasta 2 ^ 20.
Conectaré sort
y sus dependencias en un programa de prueba y compilaré en GCC (sin opciones sofisticadas). Alimentaré un montón de matrices en él, verificaré la exactitud de los resultados y el tiempo total de ejecución. Las pruebas se ejecutarán en un Intel Core i7 740QM (Clarksfield) en Ubuntu 13. Las
longitudes de matriz abarcarán todo el rango permitido, con una mayor densidad de matrices cortas. Los valores serán aleatorios, con una distribución de cola gorda (tanto en el rango positivo como en el negativo). Los elementos duplicados se incluirán en algunas pruebas.
El programa de prueba está disponible aquí: https://gist.github.com/anonymous/82386fa028f6534af263
Importa el envío como user.c
. El número de casos de prueba ( TEST_COUNT
) en el punto de referencia real será 3000. Proporcione cualquier comentario en los comentarios de las preguntas.
Plazo: 3 semanas (7 de abril de 2014, 16:00 GMT). Publicaré el punto de referencia en 2 semanas.
Puede ser aconsejable publicar cerca de la fecha límite para evitar regalar su código a los competidores.
Resultados preliminares, a partir de la publicación de referencia:
Estos son algunos resultados. La última columna muestra el puntaje como un porcentaje, cuanto más alto mejor, colocando a Johnny Cage en primer lugar. Los algoritmos que eran de órdenes de magnitud más lentos que el resto se ejecutaron en un subconjunto de pruebas y se extrapolaron en el tiempo. El propio C qsort
está incluido para comparación (¡Johnny's es más rápido!). Realizaré una comparación final a la hora de cierre.
fuente
Respuestas:
150 caracteres
Ordenación rápida.
Comprimido.
fuente
150 caracteres (sin espacios en blanco)
fuente
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }
puede serif(*w<*v) t=v[++l], v[l]=*w, *w=t;
67 7069 caracteresNo es nada rápido, pero increíblemente pequeño. Supongo que es un híbrido entre un algoritmo de selección y de clasificación de burbujas. Si realmente está intentando leer esto, entonces debe saber que
++i-v-n
es lo mismo que++i != v+n
.fuente
if(a)b
->a?b:0
guarda un personaje.++i-v-n
es lo mismo que++i != v+n
solo en un condicional, por supuesto.if(*i>v[n])...
->*i>v[n]?...:0
123 caracteres (+3 líneas nuevas)
Un tipo estándar de Shell, comprimido.
PD: descubrí que todavía es 10 veces más lento que Quicksort. También podría ignorar esta entrada.
fuente
395 caracteres
Mergesort.
Formateado
fuente
331326327312 caracteres¿La raíz clasifica 8 bits a la vez? Utiliza un bithack elegante para que los flotadores negativos se ordenen correctamente (robado de http://stereopsis.com/radix.html ). No es tan compacto, pero es realmente rápido (~ 8 veces más rápido que la entrada preliminar más rápida). Espero el tamaño del código de velocidad de triunfo ...
fuente
511424 caracteresRadixsort en el lugar
Actualización: Cambia al orden de inserción para tamaños de matriz más pequeños (aumenta el rendimiento de referencia en un factor de 4.0).
Formateado
fuente
void*
enqsort
(línea 88) está arrojando la aritmética del puntero.121114111 caracteresSolo una burbuja rápida y sucia, con recursión. Probablemente no muy eficiente.
O la versión larga
fuente
221193172 caracteresHeapsort: no es el más pequeño, pero está en su lugar y garantiza el comportamiento O (n * log (n)).
Comprimido.
fuente
TEST_COUNT
= 3000, parece fallar al menos una prueba.154166 caracteresOK, aquí hay un resumen rápido más largo pero más rápido.
Aquí hay una corrección para sobrevivir a las entradas ordenadas. Y formateado ya que el espacio en blanco no cuenta.
fuente
150 caracteres
Shellsort (w / Knuth gap).
Formateado
fuente
C 270 (golfizado)
Explicación: Se utiliza una matriz en blanco para almacenar cada número mínimo sucesivo. Una matriz int es una máscara con 0 que indica que el número aún no se ha copiado. Después de obtener el valor mínimo, una máscara = 1 omite los números ya utilizados. Luego, la matriz se copia nuevamente al original.
Cambié el código para eliminar el uso de las funciones de la biblioteca.
fuente
144
Descaradamente tomé el código de Johnny, agregué una pequeña optimización y comprimí el código de una manera muy sucia. Debería ser más corto y más rápido.
Tenga en cuenta que dependiendo de su compilador, sort (q, v + n- ++ q) debe reemplazarse por sort (++ q, v + nq).
Bueno, en realidad, comencé a formar mi código y lo optimicé, pero parece que Johnny ya tomó todas las decisiones correctas. Así que terminé con casi su código. No pensé en el truco del goto, pero podría prescindir.
fuente
228 caracteres
Radixsort.
fuente