La tarea
Escriba un programa, en el idioma que elija, que lea líneas de entrada desde la entrada estándar hasta EOF, y luego las escriba en la salida estándar en orden ASCIIbetical, similar al sort
programa de línea de comandos. Un ejemplo corto y sin pretensiones en Python es:
import sys
for line in sorted(sys.stdin):
print(line.rstrip('\n'))
La parte oculta
Al igual que The OS War , su objetivo es demostrar que su plataforma favorita es "mejor", haciendo que su programa se ejecute deliberadamente mucho más lentamente en una plataforma competidora. En aras de este concurso, una "plataforma" consiste en cualquier combinación de:
- Procesador
- Arquitectura (x86, Alpha, ARM, MIPS, PowerPC, etc.)
- Bitness (64 bits frente a 32 bits frente a 16 bits)
- Big-versus little-endian
- Sistema operativo
- Windows vs. Linux vs. Mac OS, etc.
- Diferentes versiones del mismo sistema operativo.
- Implementación del lenguaje
- Diferentes proveedores de compiladores / intérpretes (por ejemplo, MSVC ++ vs. GCC)
- Diferentes versiones del mismo compilador / intérprete
Aunque podría cumplir los requisitos escribiendo código como:
#ifndef _WIN32
Sleep(1000);
#endif
Tal respuesta no debe ser votada. El objetivo es ser sutil. Idealmente, su código debería verse como si no dependiera de la plataforma en absoluto. Si no tiene ningún #ifdef
declaraciones (o condiciones sobre la base de os.name
o System.Environment.OSVersion
o lo que sea), deben tener una justificación plausible (basado en una mentira, por supuesto).
Incluir en tu respuesta
- El código
- Sus plataformas "favoritas" y "desfavorables".
- Una entrada con la que probar su programa.
- El tiempo de ejecución en cada plataforma, para la misma entrada.
- Una descripción de por qué el programa se ejecuta tan lentamente en la plataforma desfavorable.
Respuestas:
do
CleverSort
CleverSort es un algoritmo de clasificación de cadenas de dos pasos de última generación (es decir, sobredimensionado y subóptimo).
En el paso 1, comienza ordenando previamente las líneas de entrada usando la clasificación de radix y los primeros dos bytes de cada línea. La clasificación de radix no es comparativa y funciona muy bien para cadenas.
En el paso 2, utiliza el orden de inserción en la lista de cadenas ordenada previamente. Dado que la lista está casi ordenada después del paso 1, la ordenación por inserción es bastante eficiente para esta tarea.
Código
Plataformas
Todos sabemos que las máquinas big endian son mucho más eficientes que sus contrapartes little endian. Para la evaluación comparativa, compilaremos CleverSort con las optimizaciones activadas y crearemos aleatoriamente una lista enorme (un poco más de 100,000 cadenas) de líneas de 4 bytes:
Punto de referencia big endian
No está nada mal.
Bechmark little endian
Boo, pequeño Endian! ¡Abucheo!
Descripción
La ordenación por inserción es realmente bastante eficiente para listas casi ordenadas, pero es terriblemente ineficiente para las ordenadas aleatoriamente.
La parte oculta de CleverSort es la macro FIRSTSHORT :
En máquinas big-endian, ordenar una cadena de dos enteros de 8 bits lexicográficamente o convertirlos en enteros de 16 bits y ordenarlos luego produce los mismos resultados.
Naturalmente, esto también es posible en máquinas little endian, pero la macro debería haber sido
que funciona como se esperaba en todas las plataformas.
El "punto de referencia big-endian" anterior es en realidad el resultado del uso de la macro adecuada.
Con la macro incorrecta y una máquina little-endian, la lista se ordena previamente por el segundo carácter de cada línea, lo que resulta en un orden aleatorio desde el punto de vista lexicográfico. La ordenación por inserción se comporta muy mal en este caso.
fuente
Python 2 contra Python 3
Obviamente, Python 3 es varios órdenes de magnitud más rápido que Python 2. Tomemos como ejemplo esta implementación del algoritmo Shellsort :
Código
Punto de referencia
Prepare una entrada de prueba. Esto está tomado de la respuesta de Dennis pero con menos palabras: Python 2 es muuuy lento ...
Python 2
Python 3
¿Dónde está el código oculto?
Supongo que algunos lectores pueden querer cazar al embaucador ellos mismos, así que oculto la respuesta con una etiqueta de spoiler.
Bonus 1:
Bonus 2:
fuente
flag
parece de solo escritura, ¿no podrías eliminarlo? Además,r
parece superfluo si lo hacesif lst[i+h] < lst[i]: ...
. Por otro lado, si siguesr
¿por qué hacer el intercambio? ¿No podrías simplemente hacerlolst[i+h] = lst[i]
? ¿Es todo esto una distracción intencional?