C ++ bit magic
0.84ms com RNG simples, 1.67ms com c ++ 11 std :: knuth
0.16ms com ligeira modificação algorítmica (veja editar abaixo)
A implementação do python é executada em 7,97 segundos no meu equipamento. Portanto, isso é 9488 a 4772 vezes mais rápido, dependendo do RNG que você escolher.
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <tuple>
#if 0
// C++11 random
std::random_device rd;
std::knuth_b gen(rd());
uint32_t genRandom()
{
return gen();
}
#else
// bad, fast, random.
uint32_t genRandom()
{
static uint32_t seed = std::random_device()();
auto oldSeed = seed;
seed = seed*1664525UL + 1013904223UL; // numerical recipes, 32 bit
return oldSeed;
}
#endif
#ifdef _MSC_VER
uint32_t popcnt( uint32_t x ){ return _mm_popcnt_u32(x); }
#else
uint32_t popcnt( uint32_t x ){ return __builtin_popcount(x); }
#endif
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
uint32_t s1 = S % ( 1 << n );
uint32_t s2 = (S >> 1) % ( 1 << n );
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
// calculate which bits in the expression S * F evaluate to +1
unsigned firstPosBits = ((s1 & posBits) | (~s1 & negBits));
// idem for -1
unsigned firstNegBits = ((~s1 & posBits) | (s1 & negBits));
if ( popcnt( firstPosBits ) == popcnt( firstNegBits ) )
{
firstZero++;
unsigned secondPosBits = ((s2 & posBits) | (~s2 & negBits));
unsigned secondNegBits = ((~s2 & posBits) | (s2 & negBits));
if ( popcnt( secondPosBits ) == popcnt( secondNegBits ) )
{
bothZero++;
}
}
}
}
return std::make_pair(firstZero, bothZero);
}
int main()
{
typedef std::chrono::high_resolution_clock clock;
int rounds = 1000;
std::vector< std::pair<unsigned, unsigned> > out(rounds);
// do 100 rounds to get the cpu up to speed..
for( int i = 0; i < 10000; i++ )
{
convolve();
}
auto start = clock::now();
for( int i = 0; i < rounds; i++ )
{
out[i] = convolve();
}
auto end = clock::now();
double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;
#if 0
for( auto pair : out )
std::cout << pair.first << ", " << pair.second << std::endl;
#endif
std::cout << seconds/rounds*1000 << " msec/round" << std::endl;
return 0;
}
Compile em 64 bits para registros extras. Ao usar o gerador aleatório simples, os loops em convolve () são executados sem nenhum acesso à memória, todas as variáveis são armazenadas nos registradores.
Como funciona: em vez de armazenar S
e F
como matrizes na memória, ele é armazenado como bits em um uint32_t.
Pois S
, os n
bits menos significativos são usados onde um bit definido indica um +1 e um bit não definido indica -1.
F
requer pelo menos 2 bits para criar uma distribuição de [-1, 0, 0, 1]. Isso é feito gerando bits aleatórios e examinando os 16 bits menos significativos (chamados r
) e os 16 bits mais significativos (chamados l
). Se l & ~r
assumirmos que F é +1, se ~l & r
assumirmos que F
é -1. Caso contrário, F
é 0. Isso gera a distribuição que estamos procurando.
Agora temos S
, posBits
com um bit definido em todos os locais onde F == 1 e negBits
com um bit definido em todos os locais onde F == -1.
Podemos provar que F * S
(onde * denota multiplicação) é avaliado como +1 sob a condição (S & posBits) | (~S & negBits)
. Também podemos gerar lógica semelhante para todos os casos em que é F * S
avaliado como -1. E, finalmente, sabemos quesum(F * S)
avalia como 0 se e somente se houver uma quantidade igual de -1 e + 1 no resultado. É muito fácil calcular isso simplesmente comparando o número de +1 e -1 bits.
Esta implementação usa 32 bits de ints, e o valor máximo n
aceito é 16. É possível escalar a implementação para 31 bits modificando o código de geração aleatória e para 63 bits usando uint64_t em vez de uint32_t.
editar
A seguinte função convolve:
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
uint32_t mask = posBits | negBits;
uint32_t totalBits = popcnt( mask );
// if the amount of -1 and +1's is uneven, sum(S*F) cannot possibly evaluate to 0
if ( totalBits & 1 )
continue;
uint32_t adjF = posBits & ~negBits;
uint32_t desiredBits = totalBits / 2;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
// calculate which bits in the expression S * F evaluate to +1
auto firstBits = (S & mask) ^ adjF;
auto secondBits = (S & ( mask << 1 ) ) ^ ( adjF << 1 );
bool a = desiredBits == popcnt( firstBits );
bool b = desiredBits == popcnt( secondBits );
firstZero += a;
bothZero += a & b;
}
}
return std::make_pair(firstZero, bothZero);
}
reduz o tempo de execução para 0,160-0,161ms. O desenrolar manual do loop (não na foto acima) faz com que 0,150. O caso menos trivial de n = 10, iter = 100000 é executado em 250ms. Tenho certeza de que posso obtê-lo abaixo de 50ms usando núcleos adicionais, mas isso é muito fácil.
Isso é feito liberando o ramo do loop interno e trocando o loop F e S.
Se bothZero
não for necessário, eu posso reduzir o tempo de execução para 0,02 ms, fazendo um loop esparso sobre todas as matrizes S possíveis.
-std=c++0x -mpopcnt -O2
e leva 1.01ms para executar no modo de 32 bits (não tenho uma versão do GCC de 64 bits em mãos).Python2.7 + Numpy 1.8.1: 10.242 s
Fortran 90+:
0,029 s0,003 s0,022 s0,010 sDroga, você perdeu sua aposta! Também não é uma gota de paralelismo, apenas o Fortran 90+ direto.
Edição Eu peguei o algoritmo de Guy Sirton para permutar o array
S
(boa descoberta: D). Aparentemente, eu também tinha os-g -traceback
sinalizadores do compilador ativos, que estavam diminuindo esse código para cerca de 0,017s. Atualmente, estou compilando isso comoPara quem não tem
ifort
, você pode usarEDIT 2 : A diminuição no tempo de execução é porque eu estava fazendo algo errado anteriormente e obtive uma resposta incorreta. Fazer da maneira certa é aparentemente mais lento. Ainda não consigo acreditar que o C ++ seja mais rápido que o meu, por isso provavelmente vou gastar algum tempo esta semana tentando ajustar essa porcaria para acelerar.
EDIÇÃO 3 : Simplesmente alterando a seção RNG usando uma baseada no RNG da BSD (como sugerido por Sampo Smolander) e eliminando a divisão constante por
m1
, reduzi o tempo de execução para o mesmo que a resposta C ++ de Guy Sirton . O uso de matrizes estáticas (como sugerido pela Sharpie) reduz o tempo de execução para o tempo de execução do C ++! Yay Fortran! : DEDIT 4 Aparentemente, isso não é compilado (com gfortran) e executado corretamente (valores incorretos) porque os números inteiros estão ultrapassando seus limites. Fiz correções para garantir que funcione, mas isso requer que se tenha ifort 11+ ou gfortran 4.7+ (ou outro compilador que permita
iso_fortran_env
e oint64
tipo F2008 ).Aqui está o código:
Suponho que a pergunta agora é: você irá parar de usar o Python lento como melaço e usar o Fortran rápido como elétrons que pode se mover;).
fonte
integer(int64) :: b = 3141592653_int64
para todos os int64. Isso faz parte do padrão fortran e é esperado pelo programador em uma linguagem de programação declarada por tipo. (Note que as configurações padrão de curso pode substituir esse)Python 2.7 -
0.882s0.283s(Original do OP: 6.404s)
Edit: Otimização de Steven Rumbalski pré-computando valores de F. Com essa otimização, o cpython supera os 0.365s do pypy.
O código original do OP usa matrizes tão pequenas que não há benefício em usar o Numpy, como demonstra a implementação pura do python. Mas veja também essa implementação numpy que é três vezes mais rápida do que meu código.
Também otimizo pulando o resto da convolução se o primeiro resultado não for zero.
fonte
F
porque existem apenas 4032 delas. DefinachoicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))
fora dos loops. Em seguida, no loop interno, definaF = random.choice(choicesF)
. Eu recebo uma aceleração de 3x com essa abordagem.range(iters)
fora do loop. Ao todo, recebo uma aceleração de cerca de 7% em relação à sua ótima resposta.Ferrugem: 0.011s
Python original: 8.3
Uma tradução direta do Python original.
--opt-level=3
rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)
para ser mais preciso)fonte
a
eb
s na convolução; fixo (não altera notavelmente o tempo de execução).C ++ (VS 2012) -
0.026s0.015sPython 2.7.6 / Numpy 1.8.1 - 12s
Aceleração ~ x800.
A diferença seria muito menor se as matrizes envolvidas fossem muito grandes ...
Algumas notas:
S[0]
o dígito "menos significativo".Adicione esta função principal para um exemplo independente:
fonte
advance
função, assim meu código é agora mais rápido do que o seu: P (mas muito boa competição!)C
Leva 0,015s na minha máquina, com o código original do OP demorando ~ 7,7s. Tentei otimizar gerando a matriz aleatória e convolvendo no mesmo loop, mas isso não parece fazer muita diferença.
A primeira matriz é gerada usando um número inteiro, escreva-o em binário e altere todos os 1 para -1 e todos os 0 para 1. O restante deve ser bem direto.
Edit: em vez de ter
n
como umaint
, agora temosn
como uma constante definida por macro, para que possamos usar emint arr[n];
vez demalloc
.Edit2: Em vez de
rand()
função interna, isso agora implementa um PRNG xorshift. Além disso, muitas instruções condicionais são removidas ao gerar a matriz aleatória.Instruções de compilação:
Código:
fonte
do{}while(!flag)
ou algo nesse sentido. Não espero que mude muito o tempo de execução (pode torná-lo mais rápido).continue;
declaração que eu atribuído-1
ak
, entãok
fará um loop de 0 novamente.-=
melhor que=-
:-) Um loop while seria mais legível.J
Eu não espero derrotar nenhum idioma compilado, e algo me diz que seria necessário uma máquina milagrosa para obter menos de 0,09 s com isso, mas eu gostaria de enviar esse J de qualquer maneira, porque é muito liso.
Isso leva cerca de 0,5 s em um laptop da década anterior, apenas 20x mais rápido que o Python na resposta. A maior parte do tempo é gasta
conv
porque a escrevemos preguiçosamente (calculamos toda a convolução) e com total generalidade.Como sabemos
S
eF
podemos acelerar, otimizações específicas para este programa. O melhor que pude apresentar é -conv =: ((num, num+1) { +//.)@:(*/)"1
selecione especificamente os dois números que correspondem das somas diagonais aos elementos mais longos da convolução - que reduzem pela metade o tempo.fonte
Perl - 9.3X mais rápido ... 830% de melhoria
No meu netbook antigo, o código do OP demora 53 segundos para ser executado; A versão de Alistair Buxton leva cerca de 6,5 segundos e a versão Perl a seguir leva cerca de 5,7 segundos.
fonte
Python 2.7 - numpy 1.8.1 com ligações mkl - 0.086s
(Original do OP: 6.404s) (python puro de Buxton: 0.270s)
Como Buxton aponta, o código original do OP usa matrizes tão pequenas que não há benefício em usar o Numpy. Essa implementação aproveita o numpy, executando todos os casos F e S de uma só vez, de maneira orientada por matriz. Isso combinado com as ligações mkl para python leva a uma implementação muito rápida.
Observe também que apenas carregar as bibliotecas e iniciar o intérprete leva 0,076s; portanto, o cálculo real leva ~ 0,01 segundos, semelhante à solução C ++.
fonte
python -c "import numpy; numpy.show_config()"
irá mostrar-lhe se a sua versão do numpy é compilado contra blas / atlas / mkl, etc. ATLAS é um pacote de matemática acelerada livre que numpy pode ser ligado contra , Intel MKL você geralmente tem que pagar (a menos que você é um acadêmico) e pode ser vinculado a numpy / scipy .MATLAB 0.024s
Computador 1
Computador 2
Decidi experimentar o Matlab tão lento. Se você sabe como, pode se livrar da maioria dos loops (no Matlab), o que o torna muito rápido. No entanto, os requisitos de memória são mais altos do que as soluções em loop, mas isso não será um problema se você não tiver matrizes muito grandes ...
Aqui está o que eu faço:
Presumo que você não tenha o Matlab, o que é muito ruim, pois eu realmente gostaria de ver como ele se compara ...
(A função pode ser mais lenta na primeira vez que você a executa.)
fonte
Julia: 0,30 s
Op's Python: 21.36 s (Core2 duo)
71x aceleração
Fiz algumas modificações na resposta de Arman na Julia: Antes de tudo, envolvi-a em uma função, pois as variáveis globais dificultam a inferência de tipo de Julia e o JIT: uma variável global pode alterar seu tipo a qualquer momento e deve ser verificada a cada operação . Então, me livrei das funções anônimas e da compreensão de arrays. Eles não são realmente necessários e ainda são muito lentos. Julia é mais rápida com abstrações de nível inferior no momento.
Existem muitas outras maneiras de torná-lo mais rápido, mas isso faz um trabalho decente.
fonte
Ok, estou postando isso apenas porque sinto que o Java precisa ser representado aqui. Sou péssimo com outras línguas e confesso que não entendi exatamente o problema, por isso precisarei de ajuda para corrigir esse código. Roubei a maior parte do exemplo C do ás de código e depois peguei emprestados alguns trechos de outros. Espero que não seja um falso passo ...
Uma coisa que eu gostaria de destacar é que os idiomas que otimizam em tempo de execução precisam ser executados várias / muitas vezes para atingir a velocidade máxima. Eu acho que é justificável usar a velocidade totalmente otimizada (ou pelo menos a velocidade média) porque a maioria das coisas com as quais você está preocupado em correr rápido será executada várias vezes.
O código ainda precisa ser corrigido, mas eu o executei de qualquer maneira para ver que horas chegaria.
Aqui estão os resultados de uma CPU Intel (R) Xeon (E) E3-1270 V2 a 3.50GHz no Ubuntu executando-a 1000 vezes:
servidor: / tmp # time java8 -cp. Testador
firstzero 40000
bothzero 20000
primeiro tempo de execução: 41 ms último tempo de execução: 4 ms
usuário 0m5.014s real 0m4.664s sys 0m0.268s
Aqui está o meu código de baixa qualidade:
E tentei executar o código python depois de atualizar o python e instalar o python-numpy, mas recebo o seguinte:
fonte
currentTimeMillis
para benchmarking (use a versão nano no System) e as execuções de 1k podem não ser suficientes para envolver o JIT (1,5k para o cliente e 10k para o servidor seriam os padrões, embora você chame o myRand com freqüência suficiente JITed que deve fazer com que algumas funções do callstack sejam compiladas, o que pode funcionar aqui). Última, mas não menos importante, o PNRG fraco está trapaceando, mas o mesmo acontece com a solução C ++ e outras, então acho que isso não é injusto demais.gettimeofday(&time, NULL)
por miliSeconds, o que não é monotônico e não oferece nenhuma garantia de precisão (portanto, em algumas plataformas / kernels exatamente o mesmo problemas como a implementação currentTimeMillis do Windows - para que a pessoa esteja bem ou não esteja). Por outro lado, o nanoTime usa oclock_gettime(CLOCK_MONOTONIC, &tp)
que claramente também é a coisa certa a ser usada quando se faz um benchmarking no Linux.Golang versão 45X do python na minha máquina nos códigos Golang abaixo:
e os códigos python abaixo copiados de cima:
e o tempo abaixo:
fonte
"github.com/yanatan16/itertools"
? Você também diria que isso funcionaria bem em várias goroutines?C # 0.135s
C # baseado no python simples de Alistair Buxton : 0.278s
C # paralelo: 0.135s
Python da pergunta: 5.907s
python simples de Alistair: 0.853s
Na verdade, não tenho certeza de que essa implementação esteja correta - sua saída é diferente, se você observar os resultados na parte inferior.
Certamente existem algoritmos mais ótimos. Eu apenas decidi usar um algoritmo muito semelhante ao do Python.
C de rosca única
C # paralelo:
Saída de teste:
Windows (.NET)
O C # é muito mais rápido no Windows. Provavelmente porque o .NET é mais rápido que o mono.
O tempo do usuário e do sistema não parece funcionar (usado
git bash
para o tempo).Linux (mono)
fonte
Haskell: ~ 2000x de aceleração por núcleo
Compile com 'ghc -O3 -funbox-strict-fields -threaded -fllvm' e execute com '+ RTS -Nk' onde k é o número de núcleos em sua máquina.
fonte
Rubi
Ruby (2.1.0) 0.277s
Ruby (2.1.1) 0.281s
Python (Alistair Buxton) 0.330s
Python (alemão) 0.097s
fonte
thread não estaria completo sem PHP
6.6x mais rápido
PHP v5.5.9 -
1.2230,646 seg;vs
Python v2.7.6 - 8.072 sec
convolve
função simplificada um pouco para ser mais rápido$F
e$FS
verificações).Saídas:
Editar. A segunda versão do script funciona apenas para
0.646 sec
:fonte
Solução F #
O tempo de execução é de 0,030s quando compilado para x86 no CLR Core i7 4 (8) a 3,4 Ghz
Não faço ideia se o código está correto.
fonte
Q, 0,296 seg
Q é uma linguagem orientada a coleções (kx.com)
Código reescrito para explorar Q idiomático, mas nenhuma outra otimização inteligente
Linguagens de script otimizam o tempo do programador, não o tempo de execução
Primeira tentativa de codificação = não é um vencedor, mas um tempo razoável (aprox. 30x de aceleração)
NOTAS.-
\S seed
\t sentence
mede o tempo consumido por essa frasefonte
Julia:
12.1496.929 sApesar das reivindicações de velocidade , o tempo inicial de compilação do JIT nos impede!
Observe que o código Julia a seguir é efetivamente uma tradução direta do código Python original (sem otimizações) como uma demonstração de que você pode transferir facilmente sua experiência de programação para uma linguagem mais rápida;)
Editar
Correr com
n = 8
leva 32.935 s. Considerando que a complexidade desse algoritmo éO(2^n)
, então4 * (12.149 - C) = (32.935 - C)
,C
uma constante que representa o tempo de compilação do JIT. ResolvendoC
issoC = 5.2203
, sugerimos que o tempo real de execuçãon = 6
é de 6.929 s.fonte
Ferrugem, 6,6 ms, aceleração de 1950x
Praticamente uma tradução direta do código de Alistair Buxton para Rust. Pensei em usar vários núcleos com rayon (concorrência sem medo!), Mas isso não melhorou o desempenho, provavelmente porque já é muito rápido.
E Cargo.toml, como eu uso dependências externas:
Comparação de velocidade:
6625608 ns é de cerca de 6,6 ms. Isso significa aceleração de 1950 vezes. Existem muitas otimizações possíveis aqui, mas eu estava buscando mais legibilidade do que desempenho. Uma otimização possível seria usar matrizes em vez de vetores para armazenar opções, pois elas sempre terão
n
elementos. Também é possível usar o RNG que não seja o XorShift, pois, embora o Xorshift seja mais rápido que o HC-128 CSPRNG padrão, é mais lento que o ingênuo dos algoritmos PRNG.fonte