En este desafío de optimización, escribirá un programa que clasifica una sola matriz al comparar solo elementos al pedirle al usuario en stdout que ingrese los resultados de comparación en stdin.
El siguiente protocolo está basado en líneas, por lo que cada vez que imprime en stdout o lee desde stdin se supone que sigue una nueva línea. A lo largo de la siguiente pregunta, se supone que el usuario (léase: el programa de puntuación) tiene una matriz que desea ordenar en una matriz indexada basada en 0 llamada array
. Por razones técnicas, sugiero enjuagar después de cada impresión para que sea robusto.
- Como primer paso, su programa debe leer el tamaño
n
de la matriz de stdin. - Luego, con la frecuencia que desee, puede imprimir
a < b
en stdout, con dos enteros0 <= a, b < n
. Entonces el usuario ingresará1
en stdin siarray[a] < array[b]
, y de lo0
contrario. Finalmente, una vez que su programa está convencido de que ha deducido correctamente el orden de la matriz, debe imprimir
a ...
en stdout, donde...
hay una lista de enteros separados por espacios que indican el orden. Entonces, si su programa generaa 3 0 1 4 2
, significa que su programa ha deducidoarray[3] <= array[0] <= array[1] <= array[4] <= array[2]
Tenga en cuenta que su programa nunca supo el contenido de
array
, y nunca lo sabrá.
Solo puede pedir <
en stdin para ordenar la matriz. Puede obtener otras operaciones de comparación mediante estas equivalencias:
a > b b < a
a <= b !(b < a)
a >= b !(a < b)
a != b (a < b) || (b < a)
a == b !(a < b) && !(b < a)
Finalmente, dado que su programa interactúa con el programa de puntuación en stdout, imprima la información de depuración en stderr.
Su programa se puntuará utilizando el siguiente programa de Python:
from __future__ import print_function
from subprocess import Popen, PIPE
import sys, random
def sort_test(size):
array = [random.randrange(0, size) for _ in range(size)]
pipe = Popen(sys.argv[1:], stdin=PIPE, stdout=PIPE, bufsize=0, universal_newlines=True)
print(str(size), file=pipe.stdin); pipe.stdin.flush()
num_comparisons = 0
while True:
args = pipe.stdout.readline().strip().split()
if args and args[0] == "a":
answer_array = [array[int(n)] for n in args[1:]]
if list(sorted(array)) != answer_array:
raise RuntimeError("incorrect sort for size {}, array was {}".format(size, array))
return num_comparisons
elif len(args) == 3 and args[1] == "<":
a, b = int(args[0]), int(args[2])
print(int(array[a] < array[b]), file=pipe.stdin); pipe.stdin.flush()
num_comparisons += 1
else:
raise RuntimeError("unknown command")
random.seed(0)
total = 0
for i in range(101):
num_comparisons = sort_test(i)
print(i, num_comparisons)
total += num_comparisons
print("total", total)
Usted puntúa su programa escribiendo python score.py yourprogram
. La puntuación se realiza haciendo que su programa clasifique una matriz aleatoria de cada tamaño de 0 a 100 y contando la cantidad de comparaciones que solicita su programa. Estas matrices aleatorias pueden tener duplicados , su algoritmo debe ser capaz de manejar elementos iguales. En el caso de que haya duplicados, no hay requisitos en el orden de los elementos iguales. Entonces, si la matriz es [0, 0]
, no importa si la salida a 0 1
o a 1 0
.
No puede optimizar específicamente para las matrices particulares que genera el programa de puntuación. Puedo cambiar la semilla de RNG en cualquier momento. Las respuestas que utilizan algoritmos de clasificación incorporados pueden publicarse por interés, pero no son competitivas.
Programa con menor puntaje gana.
Respuestas:
Python, puntaje 23069
Esto utiliza el algoritmo de clasificación de inserción de combinación Ford – Johnson.
fuente
Python 3, 28462 puntaje
Ordenación rápida. El pivote es el elemento más a la izquierda.
El puntaje se espera porque:
Puntuaciones para cada tamaño probado:
fuente
Python 2 (no competidor), puntaje 23471
Puntuaciones para cada tamaño probado:
fuente
Python, 333300 puntaje
Este es un programa de ejemplo, implementando la forma más simple de bubbleort, siempre haciendo
n*(n-1)
comparaciones por arreglo.Marqué este programa guardándolo como
sort.py
y escribiendopython score.py python sort.py
.fuente
print
pareciendo una función.