La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes.
Dejado P
ser una cadena binaria de longitud n
y T
ser una cadena binaria de longitud 2n-1
. Podemos calcular las n
distancias de Hamming entre P
y cada n
subcadena de longitud T
en orden de izquierda a derecha y ponerlas en una matriz (o lista).
Ejemplo de secuencia de distancia de Hamming
Deje P = 101
y T = 01100
. La secuencia de distancias de Hamming que obtienes de este par es 2,2,1
.
Tarea
Para aumentar a n
partir de n=1
, considere todos los pares posibles de cadenas binarias P
de longitud n
y T
longitud 2n-1
. Hay 2**(n+2n-1)
tales pares y, por lo tanto, muchas secuencias de distancias de Hamming. Sin embargo, muchas de esas secuencias serán idénticas. La tarea es encontrar cuántos son distintos para cada uno n
.
Su código debe generar un número por valor de n
.
Puntuación
Su puntaje es el más alto n
que alcanza su código en mi máquina en 5 minutos. El tiempo es para el tiempo total de funcionamiento, no el tiempo solo para eso n
.
Quién gana
La persona con el puntaje más alto gana. Si dos o más personas terminan con el mismo puntaje, entonces es la primera respuesta que gana.
Ejemplos de respuestas
Para n
de 1
a 8
las respuestas óptimas son 2, 9, 48, 297, 2040, 15425, 125232, 1070553
.
Idiomas y bibliotecas
Puede usar cualquier idioma y bibliotecas disponibles que desee. Siempre que sea posible, sería bueno poder ejecutar su código, por lo tanto, si es posible, incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux.
Mi máquina Los tiempos se ejecutarán en mi máquina de 64 bits. Esta es una instalación estándar de ubuntu con 8 GB de RAM, procesador AMD FX-8350 de ocho núcleos y Radeon HD 4250. Esto también significa que necesito poder ejecutar su código.
Respuestas principales
- 11 en C ++ por feersum. 25 segundos
- 11 en C ++ por Andrew Epstein. 176 segundos
- 10 en Javascript por Neil. 54 segundos
- 9 en Haskell por nimi. 4 minutos y 59 segundos.
- 8 en Javascript por fəˈnɛtɪk. 10 segundos.
fastest-code
deja más espacio para optimizaciones a través de optimizaciones de nivel de código y un buen algoritmo. Así que creo quefaster-code
es mejor quefaster-algorithm
.Respuestas:
C ++ 11 (debería llegar a 11 o 12)
Por el momento esto es de un solo subproceso.
Compilar:
fuente
feersum.cpp:111:61: warning: shifting a negative signed value is undefined [-Wshift-negative-value] int middle = int(s >> npre * MAX_N_BITS) & ~(~0 << MAX_N_BITS);
Haskell, puntaje 9
Compilar con
-O3
. Tarda 6min35s en el hardware de mi computadora portátil de 6 años para funcionarn=9
, por lo que tal vez sea menos de 5min en el hardware de referencia.fuente
JavaScript, puntaje 10
Explicación: Calcular
n=10
es difícil porque hay más de dos mil millones de pares y más de 26 mil millones de secuencias potenciales. Para acelerar las cosas, dividí el cálculo en 121 contenedores. Debido a que las secuencias son invariantes bajo el complemento bit a bit, puedo suponer sin pérdida de generalidad que el bit medio deT
es cero. Esto significa que puedo determinar el primer y el último elemento de la secuencia independientemente de los bits superiorn-1
e inferiorn-1
deT
. Cada contenedor corresponde a un par diferente de primer y último elemento; Luego recorro todos los conjuntos posibles de bits superiores e inferiores que corresponden a cada bin y calculo los elementos restantes de la secuencia, finalmente contando las secuencias únicas para cada bin. Luego queda totalizar los 121 contenedores. Originalmente tardaba 45 horas, esto ahora se completó en poco menos de tres minutos y medio en mi AMD FX-8120. Editar: Gracias a @ChristianSievers por una aceleración del 50%. Salida completa:fuente
n
como parámetro. (Perdón por la mala elección del nombre del parámetro allí.)n=1
(no sé por qué se cuelga).C ++, puntaje
1011Esta es una traducción de la respuesta de @ Neil a C ++, con una simple paralelización.
n=9
se completa en 0.4 segundos,n=10
en 4.5 segundos yn=11
en aproximadamente 1 minuto en mi Macbook Pro 2015. Además, gracias a @ChristianSievers. Debido a sus comentarios sobre la respuesta de @ Neil, noté algunas simetrías adicionales. Desde los 121 cubos originales (paran=10
), hasta 66 cubos cuando se tiene en cuenta la reversión, he llegado a solo 21 cubos.Use el siguiente script para ejecutar el código:
El resultado fue el siguiente: (El formato es
M: result, seconds
)n=12
Tardó 42 minutos en calcular en un solo hilo, y dio un resultado de 7368225813.fuente
sudo apt-get install libiomp-dev
.__builtin_popcount
.__builtin_popcount
en un contexto constexpr. Podría ir con la implementación ingenua y no afectaría el tiempo de ejecución.JavaScript 2,9,48,297,2040,15425,125232,1070553,9530752
Ejecutar en la consola:
Pruébalo en línea!
O como un fragmento de pila:
Mostrar fragmento de código
El código preinicializa la matriz para hacer que sumar 1s a la matriz sea mucho más rápido
El código encuentra todas las secuencias de distancia de hamming y las trata como una base de números (entrada + 1), las usa para colocar 1s en una matriz. Como resultado, esto genera una matriz con n 1s donde n es el número de secuencias únicas de distancia de hamming. Finalmente, el número de 1s se cuenta usando array.reduce () para sumar todos los valores de la matriz.
Este código no podrá ejecutarse para una entrada de 10 cuando alcance los límites de memoria
Este código se ejecuta en tiempo O (2 ^ 2n) porque esa es la cantidad de elementos que genera.
fuente
n = 9
Me lleva 5 minutos y 30 segundos usar node.js, por lo que es demasiado lento.n = 8
originalmente tardó 24 segundos en mi PC, pero pude optimizar el código, por lo quen = 8
tardó 6 segundos. Luego lo intentén = 9
y eso tomó 100 segundos.