Esse desafio é parcialmente um desafio de algoritmos, envolve alguma matemática e é parcialmente simplesmente um desafio de código mais rápido.
Para algum número inteiro positivo n
, considere uma sequência uniformemente aleatória de 1
s e 0
s de comprimento n
e chame-a A
. Agora considere também uma segunda sequência de comprimento aleatória, escolhida uniformemente, n
cujos valores sejam -1
, 0,
ou 1
e chame-a B_pre
. Agora B
seja B_pre
+ B_pre
. Isso éB_pre
concatenado para si mesmo.
Agora considere o produto interno de A
e B[j,...,j+n-1]
e chamá-loZ_j
e índice de 1
.
Tarefa
A saída deve ser uma lista de n+1
frações. O i
termo th na saída deve ser a exata probabilidade de que todos dos primeiros i
termos Z_j
com j <= i
igual 0
.
Ponto
O maior n
para o qual o seu código fornece a saída correta em menos de 10 minutos na minha máquina.
Desempate
Se duas respostas tiverem a mesma pontuação, a primeira submetida vence.
No evento (muito, muito improvável) de alguém encontrar um método para obter pontuações ilimitadas, a primeira prova válida de tal solução será aceita.
Sugestão
Não tente resolver esse problema matematicamente, é muito difícil. A melhor maneira, na minha opinião, é voltar às definições básicas de probabilidade do ensino médio e encontrar maneiras inteligentes de obter o código para fazer uma enumeração exaustiva das possibilidades.
Línguas e bibliotecas
Você pode usar qualquer idioma que tenha um compilador / intérprete disponível gratuitamente / etc. para Linux e quaisquer bibliotecas que também estão disponíveis gratuitamente para Linux.
Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 Eight-Core. Isso também significa que eu preciso poder executar seu código. Como conseqüência, use apenas software livre facilmente disponível e inclua instruções completas sobre como compilar e executar seu código.
Algumas saídas de teste. Considere apenas a primeira saída para cada um n
. Isso é quando i=1
. Pois n
de 1 a 13 eles deveriam ser.
1: 4/6
2: 18/36
3: 88/216
4: 454/1296
5: 2424/7776
6: 13236/46656
7: 73392/279936
8: 411462/1679616
9: 2325976/10077696
10: 13233628/60466176
11: 75682512/362797056
12: 434662684/2176782336
13: 2505229744/13060694016
Você também pode encontrar uma fórmula geral para i=1
a http://oeis.org/A081671 .
Cabeçalho (dividido por idioma)
- n = 15. Python + python paralelo + pypy em 1min49s por Jakube
- n = 17. C ++ em 3min37s por Keith Randall
- n = 16. C ++ em 2min38s por kuroi neko
fonte
Respostas:
C ++, n = 18 em 9 min em 8 threads
(Deixe-me saber se ele leva menos de 10 minutos na sua máquina.)
Aproveito várias formas de simetria na matriz B. Esses são cíclicos (deslocamento por uma posição), reversão (inverta a ordem dos elementos) e sinal (aceite o negativo de cada elemento). Primeiro, eu calculo a lista de Bs que precisamos tentar e seu peso. Então cada B é executado através de uma rotina rápida (usando instruções de contagem de bits) para todos os 2 ^ n valores de A.
Aqui está o resultado para n == 18:
Compile o programa abaixo com
g++ --std=c++11 -O3 -mpopcnt dot.cc
fonte
-pthread
novamente. Eu chegon=17
na minha máquina.Python 2 usando pypy e pp: n = 15 em 3 minutos
Também apenas uma força bruta simples. Interessante ver que quase chego à mesma velocidade que o kuroi neko com C ++. Meu código pode alcançar
n = 12
em cerca de 5 minutos. E eu apenas o executo em um núcleo virtual.editar: reduz o espaço de pesquisa por um fator de
n
I notado, que um vector ciclado
A*
deA
produz os mesmos números como probabilidades (mesmos números), o vector inicialA
quando iterarB
. Por exemplo, o vector(1, 1, 0, 1, 0, 0)
tem as mesmas probabilidades de cada um dos vectores(1, 0, 1, 0, 0, 1)
,(0, 1, 0, 0, 1, 1)
,(1, 0, 0, 1, 1, 0)
,(0, 0, 1, 1, 0, 1)
e(0, 1, 1, 0, 1, 0)
quando se escolhe uma forma aleatóriaB
. Portanto, não tenho que iterar sobre cada um desses 6 vetores, mas apenas cerca de 1 e substituircount[i] += 1
porcount[i] += cycle_number
.Isso reduz a complexidade de
Theta(n) = 6^n
paraTheta(n) = 6^n / n
. Portanton = 13
, é cerca de 13 vezes mais rápido que a minha versão anterior. Calculan = 13
em cerca de 2 minutos e 20 segundos. Poisn = 14
ainda é um pouco lento demais. Demora cerca de 13 minutos.editar 2: Programação multi-core
Não estou muito feliz com a próxima melhoria. Decidi também tentar executar meu programa em vários núcleos. Nos meus núcleos 2 + 2, agora posso calcular
n = 14
em cerca de 7 minutos. Apenas um fator de 2 melhorias.O código está disponível neste repositório do github: Link . A programação de múltiplos núcleos é um pouco feia.
edit 3: Reduzindo o espaço de pesquisa para
A
vetores eB
vetoresNotei a mesma simetria de espelho para os vetores
A
que kuroi neko. Ainda não tenho certeza, por que isso funciona (e se funciona para cada umn
).A redução do espaço de pesquisa de
B
vetores é um pouco mais inteligente. Substituí a geração dos vetores (itertools.product
) por uma função própria. Basicamente, começo com uma lista vazia e a coloco em uma pilha. Até que a pilha esteja vazia, removo uma lista, se não tiver o mesmo comprimento quen
, gerei outras 3 listas (anexando -1, 0, 1) e empurrando-as para a pilha. Se uma lista tiver o mesmo comprimenton
, posso avaliar as somas.Agora que eu mesmo gero os vetores, posso filtrá-los, dependendo se consigo atingir a soma = 0 ou não. Por exemplo, se meu vetor
A
é(1, 1, 1, 0, 0)
, e meu vetorB
parece(1, 1, ?, ?, ?)
, eu sei, que não posso preencher os?
valores com, para queA*B = 0
. Portanto, não tenho que repetir todos esses 6 vetoresB
do formulário(1, 1, ?, ?, ?)
.Podemos melhorar isso, se ignorarmos os valores de 1. Conforme observado na pergunta, os valores de
i = 1
são a sequência A081671 . Existem muitas maneiras de calcular isso. Eu escolho a recorrência simples:a(n) = (4*(2*n-1)*a(n-1) - 12*(n-1)*a(n-2)) / n
. Como podemos calculari = 1
basicamente em pouco tempo, podemos filtrar mais vetores paraB
. Por exemplo,A = (0, 1, 0, 1, 1)
eB = (1, -1, ?, ?, ?)
. Podemos ignorar vetores, onde o primeiro? = 1
, porque oA * cycled(B) > 0
, para todos esses vetores. Espero que você possa acompanhar. Provavelmente não é o melhor exemplo.Com isso eu posso calcular
n = 15
em 6 minutos.editar 4:
Implementou rapidamente a grande ideia de kuroi neko, que diz isso
B
e-B
produz os mesmos resultados. Aceleração x2. A implementação é apenas um hack rápido, no entanto.n = 15
em 3 minutos.Código:
Para o código completo, visite Github . O código a seguir é apenas uma representação dos principais recursos. Deixei de fora as importações, a programação multicore, a impressão dos resultados, ...
Uso:
Você precisa instalar o pypy (para o Python 2 !!!). O módulo python paralelo não é portado para o Python 3. Então você deve instalar o módulo python paralelo pp-1.6.4.zip . Extraia-o
cd
na pasta e liguepypy setup.py install
.Então você pode ligar para o meu programa com
pypy you-do-the-math.py 15
Ele determinará automaticamente o número de CPUs. Pode haver algumas mensagens de erro após o término do programa, apenas as ignore.
n = 16
deve ser possível em sua máquina.Resultado:
Notas e idéias:
A & B
e contar os blocos 01 e 10. O ciclismo pode ser feito com a mudança do vetor e o uso de máscaras ... Na verdade, implementei tudo isso, você pode encontrá-lo em alguns dos meus commits mais antigos no Github. Mas acabou sendo mais lento que nas listas. Eu acho que o pypy realmente otimiza as operações da lista.fonte
valentão lanoso - C ++ - muito lento
Bem, desde que um programador melhor assumiu a implementação do C ++, estou encerrando esse processo.
Construindo o executável
É uma fonte C ++ 11 autônoma que compila sem avisos e roda sem problemas:
Se você compilar com o g ++, use: g ++ -O3 -pthread -std = c ++ 11 O
esquecimento
-pthread
produzirá um despejo de núcleo agradável e amigável.Otimizações
O último termo Z é igual ao primeiro (Bpre x A nos dois casos); portanto, os dois últimos resultados são sempre iguais, o que dispensa o cálculo do último valor Z.
O ganho é negligenciável, mas codificá-lo não custa nada, portanto você pode usá-lo.
Como Jakube descobriu, todos os valores cíclicos de um determinado vetor A produzem as mesmas probabilidades.
Você pode computá-los com uma única instância de A e multiplicar o resultado pelo número de possíveis rotações. Os grupos de rotação podem ser facilmente pré-calculados em um período de tempo desprezível, portanto, esse é um enorme ganho de velocidade líquida.
Como o número de permutações de um vetor de comprimento n é n-1, a complexidade cai de o (6 n ) para o (6 n / (n-1)), basicamente indo um passo além no mesmo tempo de computação.
Parece que pares de padrões simétricos também geram as mesmas probabilidades. Por exemplo, 100101 e 101001.
Não tenho prova matemática disso, mas, intuitivamente, quando apresentados com todos os padrões B possíveis, cada valor A simétrico será complicado com o valor B simétrico correspondente para o mesmo resultado global.
Isso permite reagrupar mais alguns vetores A, para uma redução aproximada de 30% do número de grupos A.
ERRADO
Por alguma razão semi-misteriosa, todos os padrões com apenas um ou dois bits definidos produzem o mesmo resultado. Isso não representa muitos grupos distintos, mas ainda assim eles podem ser mesclados praticamente sem nenhum custo.Os vetores B e -B (B com todos os componentes multiplicados por -1) produzem as mesmas probabilidades.
(por exemplo [1, 0, -1, 1] e [-1, 0, 1, -1]).
Exceto pelo vetor nulo (todos os componentes iguais a 0), B e -B formam um par de vetores distintos .
Isso permite reduzir o número de valores B pela metade considerando apenas um de cada par e multiplicando sua contribuição por 2, adicionando a contribuição global conhecida de B nulo a cada probabilidade apenas uma vez.
Como funciona
O número de valores B é enorme (3 n ); portanto, a pré-computação deles exigiria quantidades indecentes de memória, o que tornaria a computação mais lenta e eventualmente esgotaria a RAM disponível.
Infelizmente, não consegui encontrar uma maneira simples de enumerar o meio conjunto de valores B otimizados, por isso recorri à codificação de um gerador dedicado.
O poderoso gerador B foi muito divertido de codificar, embora as linguagens que suportam mecanismos de produção tivessem permitido programá-lo de uma maneira muito mais elegante.
Em resumo, o que ele faz é considerar o "esqueleto" de um vetor Bpre como um vetor binário em que 1s representa valores reais de -1 ou +1.
Entre todos esses valores potenciais + 1 / -1, o primeiro é fixo em +1 (selecionando um dos possíveis vetores B / -B) e todas as combinações possíveis possíveis + 1 / -1 são enumeradas.
Por fim, um sistema simples de calibração garante que cada rosca de trabalho processe uma faixa de valores aproximadamente do mesmo tamanho.
Os valores A são fortemente filtrados para reagrupar em pedaços equiprobáveis.
Isso é feito em uma fase de pré-computação que a força bruta examina todos os valores possíveis.
Esta parte tem um tempo de execução negligenciável de O (2 n ) e não precisa ser otimizada (o código já é ilegível o suficiente!).
Para avaliar o produto interno (que precisa ser testado apenas contra zero), os componentes -1 e 1 de B são reagrupados em vetores binários.
O produto interno é nulo se (e somente se) houver um número igual de + 1s e -1s entre os valores B correspondentes a valores A diferentes de zero.
Isso pode ser calculado com operações simples de mascaramento e contagem de bits, ajudadas por
std::bitset
isso produzirão um código de contagem de bits razoavelmente eficiente sem a necessidade de recorrer a instruções intrínsecas feias.O trabalho é igualmente dividido entre núcleos, com afinidade forçada da CPU (um pouquinho ajuda, ou é o que dizem).
Resultado de exemplo
Performances
O multithreading deve funcionar perfeitamente nisso, embora apenas os núcleos "verdadeiros" contribuam totalmente para a velocidade da computação. Minha CPU possui apenas 2 núcleos para 4 CPUs, e o ganho em uma versão de thread único é "apenas" cerca de 3,5.
Compiladores
Um problema inicial com o multithreading me levou a acreditar que os compiladores GNU estavam com desempenho pior que a Microsoft.
Após testes mais detalhados, parece que o g ++ vence o dia mais uma vez, produzindo código aproximadamente 30% mais rápido (a mesma proporção que eu notei em outros dois projetos pesados de computação).
Notavelmente, a
std::bitset
biblioteca é implementada com instruções dedicadas de contagem de bits pelo g ++ 4.8, enquanto o MSVC 2013 usa apenas loops de troca de bits convencional.Como se poderia esperar, compilar em 32 ou 64 bits não faz diferença.
Refinamentos adicionais
Notei alguns grupos A produzindo as mesmas probabilidades após todas as operações de redução, mas não consegui identificar um padrão que permitisse reagrupá-las.
Aqui estão os pares que eu notei para n = 11:
fonte
terminate called after throwing an instance of 'std::system_error' what(): Unknown error -1 Aborted (core dumped)