El desafío es escribir el código más rápido posible para calcular el permanente de una matriz .
El permanente de una matriz n
-by- = ( ) se define comon
A
a
i,j
Aquí S_n
representa el conjunto de todas las permutaciones de [1, n]
.
Como ejemplo (de la wiki):
En esta pregunta, todas las matrices son cuadradas y solo tendrán los valores -1
y 1
en ellas.
Ejemplos
Entrada:
[[ 1 -1 -1 1]
[-1 -1 -1 1]
[-1 1 -1 1]
[ 1 -1 -1 1]]
Permanente:
-4
Entrada:
[[-1 -1 -1 -1]
[-1 1 -1 -1]
[ 1 -1 -1 -1]
[ 1 -1 1 -1]]
Permanente:
0
Entrada:
[[ 1 -1 1 -1 -1 -1 -1 -1]
[-1 -1 1 1 -1 1 1 -1]
[ 1 -1 -1 -1 -1 1 1 1]
[-1 -1 -1 1 -1 1 1 1]
[ 1 -1 -1 1 1 1 1 -1]
[-1 1 -1 1 -1 1 1 -1]
[ 1 -1 1 -1 1 -1 1 -1]
[-1 -1 1 -1 1 1 1 1]]
Permanente:
192
Entrada:
[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
[-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
[-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
[-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
[1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
[1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
[1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
[-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
[-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
[1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
[-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
[1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
[-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
[1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
[-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]
Permanente:
1021509632
La tarea
Debería escribir un código que, dado n
por una n
matriz, produzca su permanente.
Como tendré que probar su código, sería útil si pudiera darme una forma simple de dar una matriz como entrada a su código, por ejemplo, leyendo el estándar en.
Tenga en cuenta que el permanente puede ser grande (la matriz de todo 1 es el caso extremo).
Puntuaciones y lazos
Probaré su código en matrices aleatorias + -1 de tamaño creciente y me detendré la primera vez que su código tarde más de 1 minuto en mi computadora. Las matrices de puntuación serán consistentes para todas las presentaciones a fin de garantizar la equidad.
Si dos personas obtienen el mismo puntaje, entonces el ganador es el que tiene el valor más rápido n
. Si están dentro de 1 segundo el uno del otro, entonces es el publicado primero.
Idiomas y bibliotecas
Puede usar cualquier idioma y bibliotecas disponibles que desee, pero ninguna función preexistente para calcular el permanente. Siempre que sea posible, sería bueno poder ejecutar su código, así que incluya una explicación completa de cómo ejecutar / compilar su código en Linux si es posible.
Implementaciones de referencia
Ya hay una pregunta de codegolf con mucho código en diferentes idiomas para calcular el permanente para matrices pequeñas. Mathematica y Maple también tienen implementaciones permanentes si puedes acceder a ellas.
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.
Información de bajo nivel sobre mi máquina
cat /proc/cpuinfo/|grep flags
da
. frág.
Haré una pregunta multilingüe de seguimiento estrechamente relacionada que no sufre el gran problema Int para que los amantes de Scala , Nim , Julia , Rust , Bash puedan mostrar sus idiomas también.
Tabla de líderes
- n = 33 (45 segundos. 64 segundos para n = 34). Ton Hospel en C ++ con g ++ 5.4.0.
- n = 32 (32 segundos). Dennis en C con gcc 5.4.0 usando las banderas gcc de Ton Hospel.
- n = 31 (54 segundos). Christian Sievers en Haskell
- n = 31 (60 segundos). primo en rpython
- n = 30 (26 segundos). ezrast en Rust
- n = 28 (49 segundos). xnor con Python + pypy 5.4.1
- n = 22 (25 segundos). Shebang con Python + pypy 5.4.1
Nota . En la práctica, los horarios de Dennis y Ton Hospel varían mucho por razones misteriosas. ¡Por ejemplo, parecen ser más rápidos después de cargar un navegador web! Los tiempos citados son los más rápidos en todas las pruebas que he realizado.
fuente
Respuestas:
gcc C ++ n ≈ 36 (57 segundos en mi sistema)
Utiliza la fórmula de Glynn con un código gris para las actualizaciones si todas las sumas de la columna son pares, de lo contrario utiliza el método de Ryser. Roscado y vectorizado. Optimizado para AVX, así que no esperes mucho en procesadores más antiguos. No se preocupe
n>=35
por una matriz con solo + 1, incluso si su sistema es lo suficientemente rápido, ya que el acumulador de 128 bits firmado se desbordará. Para matrices aleatorias, probablemente no alcanzará el desbordamiento. Paran>=37
los multiplicadores internos comenzará a desbordarse para una1/-1
matriz completa. Así que solo use este programa paran<=36
.Simplemente proporcione los elementos de la matriz en STDIN separados por cualquier tipo de espacio en blanco
permanent.cpp
:fuente
2 << (n-1)
al final, lo que significa que mi acumulador int128 se desbordó mucho antes de ese punto.C99, n ≈ 33 (35 segundos)
La entrada es actualmente un poco engorrosa; se toma con filas como argumentos de línea de comando, donde cada entrada está representada por su signo, es decir, + indica un 1 y - indica un -1 .
Prueba de funcionamiento
fuente
popcnt
). Si eso ahorra tiempo, el próximo gran obstáculo es el tipo entero. Para matrices generadas aleatoriamente, el permanente es comparativamente pequeño. Si puedo encontrar una manera fácil de calcular un límite antes de hacer el cálculo real, podría envolver todo en un gran condicional.Python 2, n ≈ 28
Utiliza la fórmula de Glynn con un código gris para las actualizaciones. Se ejecuta
n=23
en un minuto en mi máquina. Seguramente se puede mejorar implementando esto en un lenguaje más rápido y con mejores estructuras de datos. Esto no usa que la matriz tenga un valor de ± 1.La implementación de una fórmula de Ryser es muy similar, sumando todos los vectores de coeficientes 0/1 en lugar de ± 1-vectores. Lleva aproximadamente el doble de tiempo que la fórmula de Glynn porque agrega todos los 2 ^ n de tales vectores, mientras que las mitades de Glynn usan la simetría solo para aquellos que comienzan
+1
.fuente
pypy
esto pude calcular fácilmenten=28
en 44,6 segundos. El sistema de Lembik parece ser bastante comparable al mío en velocidad, si no un poco más rápido.Haskell, n = 31 (54 s)
Con muchas contribuciones invaluables de @Angs: use
Vector
, use productos de cortocircuito, mire n impares.Mis primeros intentos de paralelismo en Haskell. Puede ver muchos pasos de optimización a través del historial de revisiones. Sorprendentemente, en su mayoría fueron cambios muy pequeños. El código se basa en la fórmula en la sección "Fórmula Balasubramanian-Bax / Franklin-Glynn" en el artículo de Wikipedia sobre computación permanente .
p
calcula el permanente. Se llama a través dept
que transforma la matriz de una manera que siempre es válida, pero especialmente útil para las matrices que obtenemos aquí.Compilar con
ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs
. Para ejecutar con la paralelización, darle runtime parámetros como esto:./<name> +RTS -N
. La entrada es de stdin con listas anidadas separadas por comas entre paréntesis,[[1,2],[3,4]]
como en el último ejemplo (se permiten nuevas líneas en todas partes).fuente
Data.Vector
. Los cambios excluyendo cambiaron los tipos de función:import qualified Data.Vector as V
,x (V.zipWith(-) p v) vs (-m) c' )
,p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11
,main = getContents >>= print . p . map V.fromList . read
V.product
). Eso solo me dio ~ 10%. Cambió el código para que los vectores solo contenganInt
s. Eso está bien porque solo se suman, los números grandes provienen de la multiplicación. Entonces fue ~ 20%. Había intentado el mismo cambio con el código anterior, pero en ese momento lo ralentizó. Lo intenté nuevamente porque permite usar vectores sin caja , ¡lo que ayudó mucho!x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p)
- producto como un pliegue monádico donde 0 es un caso especial. Parece ser beneficioso la mayoría de las veces.Transversable
(veo que noproduct
cambiaste de comelier no fue un error ...) para ghc de, por ejemplo, Debian estable. Está utilizando la forma de la entrada, pero parece estar bien: no confiamos en ella, solo la optimizamos. Hace que el tiempo sea mucho más emocionante: mi matriz aleatoria de 30x30 es ligeramente más rápida que 29x29, pero luego 31x31 toma 4 veces más tiempo. - Ese INLINE no parece funcionar para mí. AFAIK se ignora para las funciones recursivas.product
pero lo olvidé. Parece que solo las longitudes pares tienen cerosp
, por lo que para longitudes impares deberíamos usar el producto regular en lugar del cortocircuito para obtener lo mejor de ambos mundos.Rust + extprim
Este sencillo Ryser con implementación de código Gray tarda aproximadamente
6590 segundos en ejecutar n = 31 en mi computadora portátil.Me imagino que su máquina llegará en menos de 60 años.Estoy usando extprim 1.1.1 parai128
.Nunca he usado Rust y no tengo idea de lo que estoy haciendo. No hay opciones de compilación aparte de lo que sea que
cargo build --release
haga. Comentarios / sugerencias / optimizaciones son apreciados.La invocación es idéntica al programa de Dennis.
fuente
git clone https://gitlab.com/ezrast/permanent.git; cd permanent; cargo build --release
si quieres estar seguro de tener la misma configuración que yo. La carga manejará las dependencias. Binario entratarget/release
.Mathematica, n ≈ 20
Usando el
Timing
comando, una matriz de 20x20 requiere aproximadamente 48 segundos en mi sistema. Esto no es exactamente tan eficiente como el otro, ya que se basa en el hecho de que el permanente se puede encontrar como el coeficiente del producto de los polimomios de cada fila de la matriz. La multiplicación polinómica eficiente se realiza creando listas de coeficientes y realizando convolución usandoListConvolve
. Esto requiere aproximadamente O (2 n n 2 ) tiempo, suponiendo que la convolución se realice utilizando una transformada rápida de Fourier o similar que requiere tiempo O ( n log n ).fuente
Python 2, n = 22 [Referencia]
Esta es la implementación de 'referencia' que compartí con Lembik ayer, se pierde
n=23
por unos segundos en su máquina, en mi máquina lo hace en unos 52 segundos. Para lograr estas velocidades, debe ejecutar esto a través de PyPy.La primera función calcula el permanente de forma similar a cómo se podría calcular el determinante, revisando cada submatriz hasta que quede con un 2x2 al que puede aplicar la regla básica. Es increiblemente lento .
La segunda función es la que implementa la función Ryser (la segunda ecuación listada en Wikipedia). El conjunto
S
es esencialmente el conjunto de potencia de los números{1,...,n}
(variables_list
en el código).fuente
RPython 5.4.1, n ≈ 32 (37 segundos)
Compilar, descargue la fuente PyPy más reciente y ejecute lo siguiente:
El ejecutable resultante será nombrado
matrix-permanent-c
o similar en el directorio de trabajo actual.A partir de PyPy 5.0, las primitivas de subprocesos de RPython son mucho menos primitivas de lo que solían ser. Los subprocesos recién generados requieren el GIL, que es más o menos inútil para cálculos paralelos. Lo he usado en su
fork
lugar, por lo que puede que no funcione como se esperaba en Windows,aunque no lo he probadono se puede compilar (unresolved external symbol _fork
).El ejecutable acepta hasta dos parámetros de línea de comando. El primero es el número de hilos, el segundo parámetro opcional es
n
. Si se proporciona, se generará una matriz aleatoria, de lo contrario, se leerá desde stdin. Cada fila debe estar separada por una nueva línea (sin una nueva línea final), y cada espacio de valores debe estar separado. El tercer ejemplo de entrada se daría como:Uso de muestra
Método
He usado la fórmula Balasubramanian-Bax / Franklin-Glynn , con una complejidad de tiempo de ejecución de O (2 n n) . Sin embargo, en lugar de iterar el δ en orden de código gris, he reemplazado la multiplicación de fila de vectores con una sola operación xor (mapeo (1, -1) → (0, 1)). La suma del vector también se puede encontrar en una sola operación, tomando n menos dos veces el popcount.
fuente
Raqueta 84 bytes
La siguiente función simple funciona para matrices más pequeñas, pero se bloquea en mi máquina para matrices más grandes:
Sin golf:
El código se puede modificar fácilmente para un número desigual de filas y columnas.
Pruebas:
Salida:
Como mencioné anteriormente, depende de las siguientes pruebas:
fuente