O desafio é escrever o código mais rápido possível para calcular a permanente de uma matriz .
A permanente de uma matriz- n
by = ( ) é definida comon
A
a
i,j
Aqui S_n
representa o conjunto de todas as permutações de[1, n]
.
Como um exemplo (do wiki):
Nesta questão, as matrizes são todas quadradas e terão apenas os valores -1
e 1
nelas.
Exemplos
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
A tarefa
Você deve escrever um código que, dado n
porn
matriz, gera a permanente.
Como precisarei testar seu código, seria útil se você desse uma maneira simples de fornecer uma matriz como entrada para o seu código, por exemplo, lendo a partir do padrão em.
Esteja avisado de que a permanente pode ser grande (a matriz todos os 1s é o caso extremo).
Pontuações e laços
Testarei seu código em matrizes + -1 aleatórias de tamanho crescente e pararei na primeira vez em que o código demorar mais de 1 minuto no meu computador. As matrizes de pontuação serão consistentes para todos os envios, a fim de garantir justiça.
Se duas pessoas obtiverem a mesma pontuação, o vencedor será o mais rápido para esse valor de n
. Se estes estiverem a 1 segundo um do outro, será o primeiro publicado.
Línguas e bibliotecas
Você pode usar qualquer idioma e bibliotecas disponíveis que desejar, mas nenhuma função pré-existente para calcular a permanente. Onde for possível, seria bom poder executar seu código; portanto, inclua uma explicação completa de como executar / compilar seu código no Linux, se possível.
Implementações de referência
Já existe uma pergunta de codegolf com muitos códigos em diferentes idiomas para calcular a permanente para matrizes pequenas. O Mathematica e o Maple também possuem implementações permanentes, se você puder acessá-las.
Minha máquina Os tempos serão executados na minha máquina de 64 bits. Esta é uma instalação padrão do ubuntu com 8GB de RAM, processador de oito núcleos AMD FX-8350 e Radeon HD 4250. Isso também significa que eu preciso executar seu código.
Informações de baixo nível sobre minha máquina
cat /proc/cpuinfo/|grep flags
dá
flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_md pfmd f16c lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a desalinhamento 3dnowprefetch osvw ibs xop skinit wdt lwp fma4 tce nodeid_msr tbm topoext perfctr_core perfctr_nb cpb hw_pstate vmmc
Farei uma pergunta multilíngue de acompanhamento intimamente relacionada que não sofre com o grande problema de Int, para que os amantes de Scala , Nim , Julia , Rust , Bash também possam mostrar seus idiomas.
Entre os melhores
- n = 33 (45 segundos. 64 segundos para n = 34). Ton Hospel em C ++ com g ++ 5.4.0.
- n = 32 (32 segundos). Dennis em C com o gcc 5.4.0 usando as bandeiras do gcc de Ton Hospel.
- n = 31 (54 segundos). Peneiradores cristãos em Haskell
- n = 31 (60 segundos). primo em rpython
- n = 30 (26 segundos). ezrast em Rust
- n = 28 (49 segundos). xnor com Python + pypy 5.4.1
- n = 22 (25 segundos). Shebang com Python + pypy 5.4.1
Nota . Na prática, os horários de Dennis e Ton Hospel variam muito por razões misteriosas. Por exemplo, eles parecem ser mais rápidos depois que eu carrego um navegador da web! Os tempos citados são os mais rápidos em todos os testes que fiz.
fonte
Respostas:
gcc C ++ n ≈ 36 (57 segundos no meu sistema)
Usa a fórmula Glynn com um código Gray para atualizações, se todas as somas da coluna forem pares, caso contrário, usa o método de Ryser. Rosqueado e vetorizado. Otimizado para AVX, não espere muito em processadores mais antigos. Não se preocupe com
n>=35
uma matriz com apenas +1, mesmo se o seu sistema for rápido o suficiente, pois o acumulador de 128 bits assinado irá estourar. Para matrizes aleatórias, você provavelmente não atingirá o estouro. Paran>=37
os multiplicadores internos, começará a transbordar para uma1/-1
matriz all . Portanto, use este programa apenas paran<=36
.Basta fornecer os elementos da matriz em STDIN separados por qualquer tipo de espaço em branco
permanent.cpp
:fonte
2 << (n-1)
no final, o que significa que meu acumulador int128 transbordou muito antes desse ponto.C99, ≈ 33 (35 segundos)
Atualmente, a entrada é um pouco complicada; é tomado com linhas como argumentos de linha de comando, onde cada entrada é representada por seu sinal, ou seja, + indica 1 e - indica -1 .
Execução de teste
fonte
popcnt
). Se isso economizar algum tempo, o próximo grande obstáculo é o tipo inteiro. Para matrizes geradas aleatoriamente, a permanente é comparativamente pequena. Se eu puder encontrar uma maneira fácil de calcular um limite antes de fazer o cálculo real, talvez envolva tudo em uma grande condicional.Python 2, nº 28
Usa a fórmula Glynn com um código Gray para atualizações. Executa até
n=23
em um minuto na minha máquina. Pode-se certamente fazer melhor implementando isso em uma linguagem mais rápida e com melhores estruturas de dados. Isso não usa que a matriz tenha um valor de ± 1.Uma implementação da fórmula de Ryser é muito semelhante, somando todos os vetores 0/1 dos coeficientes, em vez de ± 1 vetores. Demora cerca do dobro da fórmula de Glynn porque adiciona todos os 2 ^ n desses vetores, enquanto a metade de Glynn usa a simetria apenas para aqueles que começam com
+1
.fonte
pypy
isso foi possível calcular facilmenten=28
em 44,6 segundos. O sistema de Lembik parece ser bastante comparável ao meu em velocidade, se não um pouco mais rápido.Haskell, n = 31 (54s)
Com muitas contribuições inestimáveis do @Angs: use
Vector
, use produtos de curto-circuito, veja o número n.Minhas primeiras tentativas de paralelismo em Haskell. Você pode ver várias etapas de otimização no histórico de revisões. Surpreendentemente, foram principalmente mudanças muito pequenas. O código é baseado na fórmula na seção "Fórmula de Balasubramanian-Bax / Franklin-Glynn" no artigo da Wikipedia sobre computação permanente .
p
calcula o permanente. É chamado viapt
qual transforma a matriz de uma maneira que é sempre válida, mas especialmente útil para as matrizes que chegamos aqui.Compile com
ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs
. Para executar com a paralelização, dar-lhe tempo de execução parâmetros como este:./<name> +RTS -N
. A entrada é do stdin com listas aninhadas separadas por vírgula entre colchetes, como[[1,2],[3,4]]
no exemplo anterior (novas linhas são permitidas em todos os lugares).fonte
Data.Vector
. As mudanças excluindo mudou tipos de função: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
). Isso me deu apenas 10%. O código foi alterado para que os vetores contenham apenasInt
s. Tudo bem, porque eles são adicionados apenas, os grandes números vêm da multiplicação. Então foi ~ 20%. Eu havia tentado a mesma alteração com o código antigo, mas naquele momento ele o abrandou. Tentei novamente porque permite usar vetores sem caixa , o que ajudou muito!x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p)
- produto como uma dobra monádica, em que 0 é um caso especial. Parece ser benéfico mais frequentemente do que não.Transversable
(vejo que você não está mudando deproduct
lugar não foi um erro ...) para ghc, por exemplo, Debian stable. Está usando a forma da entrada, mas isso parece bom: não estamos confiando nela, apenas otimizando. Torna o tempo muito mais emocionante: minha matriz aleatória 30x30 é um pouco mais rápida que 29x29, mas 31x31 leva 4x tempo. - Esse INLINE não parece funcionar para mim. AFAIK é ignorado para funções recursivas.product
mas esqueci. Parece que apenas comprimentos pares têm zerosp
, portanto, para comprimentos ímpares, devemos usar o produto comum em vez do curto-circuito para obter o melhor dos dois mundos.Ferrugem + extprim
Essa implementação simples do código Ryser com Gray leva cerca de
65 a90 segundos para executar n = 31 no meu laptop.Imagino que sua máquina chegue lá bem abaixo dos 60 anos.Estou usando o extprim 1.1.1 parai128
.Eu nunca usei Rust e não tenho ideia do que estou fazendo. Nenhuma opção do compilador além do que quer que seja
cargo build --release
. Comentários / sugestões / otimizações são apreciados.A invocação é idêntica ao programa de Dennis.
fonte
git clone https://gitlab.com/ezrast/permanent.git; cd permanent; cargo build --release
se quiser ter a mesma configuração que eu. A carga lidará com dependências. O binário entratarget/release
.Mathematica, nº 20
Usando o
Timing
comando, uma matriz 20x20 requer cerca de 48 segundos no meu sistema. Isso não é exatamente tão eficiente quanto o outro, uma vez que se baseia no fato de que a permanente pode ser encontrada como o coeficiente do produto dos polimômios de cada linha da matriz. A multiplicação polinomial eficiente é realizada criando as listas de coeficientes e realizando convolução usandoListConvolve
. Isso requer tempo O (2 n n 2 ), pressupondo que a convolução seja realizada usando uma transformação Fast Fourier ou similar, que requer tempo O ( n log n ).fonte
Python 2, n = 22 [Referência]
Esta é a implementação de 'referência' que compartilhei com o Lembik ontem, ela perde
n=23
por alguns segundos em sua máquina, na minha máquina em cerca de 52 segundos. Para atingir essas velocidades, você precisa executar isso no PyPy.A primeira função calcula a permanente semelhante à maneira como o determinante pode ser calculado, passando por cada submatriz até que você fique com 2x2 ao qual você pode aplicar a regra básica. É incrivelmente lento .
A segunda função é aquela que implementa a função Ryser (a segunda equação listada na Wikipedia). O conjunto
S
é essencialmente o conjunto de potências dos números{1,...,n}
(variávels_list
no código).fonte
RPython 5.4.1, nº 32 (37 segundos)
Para compilar, baixe a fonte PyPy mais recente e execute o seguinte:
O executável resultante será nomeado
matrix-permanent-c
ou semelhante no diretório de trabalho atual.No PyPy 5.0, as primitivas de encadeamento do RPython são muito menos primitivas do que costumavam ser. Os threads recém-gerados requerem o GIL, que é mais ou menos inútil para cálculos paralelos. Em
fork
vez disso, usei , portanto, pode não funcionar como esperado no Windows,embora não tenha testadofalhas ao compilar (unresolved external symbol _fork
).O executável aceita até dois parâmetros de linha de comando. O primeiro é o número de threads, o segundo parâmetro opcional é
n
. Se for fornecido, uma matriz aleatória será gerada, caso contrário, será lida a partir de stdin. Cada linha deve ser separada por nova linha (sem uma nova linha à direita) e cada espaço de valor separado. A terceira entrada de exemplo seria dada como:Uso da amostra
Método
Eu usei a fórmula Balasubramanian-Bax / Franklin-Glynn , com uma complexidade de tempo de execução de O (2 n n) . No entanto, em vez de iterar o δ na ordem do código cinza, substituí a multiplicação de linhas vetoriais por uma única operação xor (mapeamento (1, -1) → (0, 1)). A soma vetorial também pode ser encontrada em uma única operação, tomando n menos duas vezes a contagem de pop-ups.
fonte
Raquete 84 bytes
A função simples a seguir funciona para matrizes menores, mas trava na minha máquina para matrizes maiores:
Ungolfed:
O código pode ser facilmente modificado para obter um número desigual de linhas e colunas.
Teste:
Saída:
Como mencionei acima, ele trava nos seguintes testes:
fonte