C ++ bit magic
0.84ms con RNG simple, 1.67ms con c ++ 11 std :: knuth
0,16 ms con una ligera modificación algorítmica (ver edición a continuación)
La implementación de Python se ejecuta en 7.97 segundos en mi plataforma. Entonces, esto es de 9488 a 4772 veces más rápido dependiendo de qué RNG elijas.
#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 en 64 bits para registros adicionales. Cuando se usa el generador aleatorio simple, los bucles en convolve () se ejecutan sin acceso a la memoria, todas las variables se almacenan en los registros.
Cómo funciona: en lugar de almacenar S
y F
como matrices en memoria, se almacena como bits en un uint32_t.
Para S
, los n
bits menos significativos se utilizan donde un bit establecido denota un +1 y un bit no establecido denota un -1.
F
requiere al menos 2 bits para crear una distribución de [-1, 0, 0, 1]. Esto se realiza generando bits aleatorios y examinando los 16 bits menos significativos (llamados r
) y los 16 bits más significativos (llamados l
). Si l & ~r
suponemos que F es +1, si ~l & r
suponemos que F
es -1. De F
lo contrario, es 0. Esto genera la distribución que estamos buscando.
Ahora tenemos S
, posBits
con un bit establecido en cada ubicación donde F == 1 y negBits
con un bit establecido en cada ubicación donde F == -1.
Podemos demostrar que F * S
(donde * denota multiplicación) se evalúa a +1 bajo la condición (S & posBits) | (~S & negBits)
. También podemos generar una lógica similar para todos los casos donde se F * S
evalúa a -1. Y finalmente, sabemos que se sum(F * S)
evalúa a 0 si y solo si hay una cantidad igual de -1 y + 1 en el resultado. Esto es muy fácil de calcular simplemente comparando el número de +1 bits y -1 bits.
Esta implementación usa entradas de 32 bits, y el máximo n
aceptado es 16. Es posible escalar la implementación a 31 bits modificando el código de generación aleatorio, y a 63 bits usando uint64_t en lugar de uint32_t.
editar
La siguiente función de convolución:
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);
}
corta el tiempo de ejecución a 0.160-0.161ms. El desenrollado manual del bucle (no se muestra arriba) hace que 0.150. El menos trivial n = 10, iter = 100000 casos se ejecuta por debajo de 250 ms. Estoy seguro de que puedo obtener menos de 50 ms aprovechando núcleos adicionales, pero eso es demasiado fácil.
Esto se hace liberando la rama del bucle interno e intercambiando el bucle F y S.
Si bothZero
no es necesario, puedo reducir el tiempo de ejecución a 0.02 ms haciendo un bucle escaso sobre todas las matrices S posibles.
-std=c++0x -mpopcnt -O2
y tarda 1.01 ms en ejecutarse en modo de 32 bits (no tengo una versión GCC de 64 bits disponible).Python2.7 + Numpy 1.8.1: 10.242 s
Fortran 90+:
0.029 s0.003 s0.022 s0.010 s¡Maldita sea, perdiste tu apuesta! No es una gota de paralelización aquí también, solo Fortran 90+.
EDITAR He tomado el algoritmo de Guy Sirton para permutar la matriz
S
(buen hallazgo: D). Aparentemente, también tenía-g -traceback
activadas las marcas del compilador, que ralentizaban este código a aproximadamente 0.017s. Actualmente, estoy compilando esto comoPara aquellos que no tienen
ifort
, pueden usarEDIT 2 : La disminución en el tiempo de ejecución se debe a que estaba haciendo algo mal anteriormente y obtuve una respuesta incorrecta. Hacerlo de la manera correcta es aparentemente más lento. Todavía no puedo creer que C ++ sea más rápido que el mío, por lo que probablemente voy a pasar algo de tiempo esta semana tratando de modificar esto para acelerarlo.
EDITAR 3 : simplemente cambiando la sección de RNG usando una basada en RNG de BSD (como lo sugiere Sampo Smolander) y eliminando la división constante entre
m1
, reduzco el tiempo de ejecución al mismo que la respuesta de C ++ de Guy Sirton . ¡El uso de matrices estáticas (como sugiere Sharpie) reduce el tiempo de ejecución a menos del tiempo de ejecución de C ++! Yay Fortran! :REEDITAR 4 Aparentemente esto no se compila (con gfortran) y se ejecuta correctamente (valores incorrectos) porque los enteros están sobrepasando sus límites. He realizado correcciones para garantizar que funciona, pero esto requiere que uno tenga ifort 11+ o gfortran 4.7+ (u otro compilador que lo permita
iso_fortran_env
y elint64
tipo F2008 ).Aquí está el código:
Supongo que la pregunta ahora es si dejarás de usar Python lento como la melaza y usarás Fortran rápido como electrones;
fuente
integer(int64) :: b = 3141592653_int64
para todos los int64. Esto es parte del estándar fortran y el programador lo espera en un lenguaje de programación de tipo declarado. (nótese que la configuración por defecto, por supuesto, puede anular este)Python 2.7 -
0.882s0.283s(Original de OP: 6.404s)
Editar: optimización de Steven Rumbalski al precalcular los valores de F. Con esta optimización, cpython supera los 0.365s de pypy.
El código original de OP utiliza matrices tan pequeñas que no hay ningún beneficio en usar Numpy, como demuestra esta implementación pura de Python. Pero vea también esta implementación numpy que es tres veces más rápida que mi código.
También optimizo saltando el resto de la convolución si el primer resultado no es cero.
fuente
F
porque solo hay 4032 de ellas. DefinirchoicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))
fuera de los bucles. Luego, en el bucle interno definirF = random.choice(choicesF)
. Tengo una aceleración 3x con este enfoque.range(iters)
fuera del bucle. En total, obtengo una aceleración de alrededor del 7% sobre su muy buena respuesta.Moho: 0.011s
Python original: 8.3
Una traducción directa del Python original.
--opt-level=3
rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)
para ser precisos)fuente
a
s yb
s mezclado en la convolución; fijo (no cambia notablemente el tiempo de ejecución).C ++ (VS 2012) -
0.026s0.015sPython 2.7.6 / Numpy 1.8.1 - 12s
Aceleración ~ x800.
La brecha sería mucho menor si las matrices enrevesadas fueran muy grandes ...
Algunas notas
S[0]
como el dígito "menos significativo".Agregue esta función principal para un ejemplo autónomo:
fuente
advance
función, por lo que mi código ahora es más rápido que el suyo: P (¡pero muy buena competencia!)C
Toma 0.015s en mi máquina, con el código original de OP tomando ~ 7.7s. Intenté optimizar generando la matriz aleatoria y convolucionando en el mismo bucle, pero no parece hacer mucha diferencia.
La primera matriz se genera tomando un número entero, escribiéndolo en binario y cambiando todo 1 a -1 y todo 0 a 1. El resto debería ser muy sencillo.
Editar: en lugar de tener
n
como unint
, ahora tenemosn
como una constante macrodefinida, por lo que podemos usar enint arr[n];
lugar demalloc
.Edit2: en lugar de la
rand()
función incorporada, esto ahora implementa un xorshift PRNG. Además, se eliminan muchas declaraciones condicionales al generar la matriz aleatoria.Compilar instrucciones:
Código:
fuente
do{}while(!flag)
o algo por el estilo. No espero que cambie mucho el tiempo de ejecución (puede hacerlo más rápido).continue;
declaración he asignado-1
ak
, por lo quek
se repetirá desde 0 otra vez.-=
más que=-
:-) Un ciclo while sería más legible.J
No espero superar ningún lenguaje compilado, y algo me dice que se necesitaría una máquina milagrosa para obtener menos de 0.09 s con esto, pero me gustaría enviar este J de todos modos, porque es bastante hábil.
Esto toma aproximadamente 0.5 s en una computadora portátil de la década anterior, solo alrededor de 20 veces más rápido que el Python en la respuesta. La mayor parte del tiempo se gasta
conv
porque lo escribimos perezosamente (calculamos toda la convolución) y en general.Dado que sabemos cosas sobre
S
yF
, podemos acelerar las cosas haciendo optimizaciones específicas para este programa. Lo mejor que he podido encontrar esconv =: ((num, num+1) { +//.)@:(*/)"1
—seleccionar específicamente los dos números que corresponden desde las sumas diagonales a los elementos más largos de la convolución— que reduce a la mitad aproximadamente el tiempo.fuente
Perl: 9.3 veces más rápido ... 830% de mejora
En mi netbook antiguo, el código del OP tarda 53 segundos en ejecutarse; La versión de Alistair Buxton tarda unos 6,5 segundos, y la siguiente versión de Perl tarda unos 5,7 segundos.
fuente
Python 2.7 - numpy 1.8.1 con enlaces mkl - 0.086s
(Original de OP: 6.404s) (Python puro de Buxton: 0.270s)
Como señala Buxton, el código original de OP utiliza matrices tan pequeñas que no hay ningún beneficio en usar Numpy. Esta implementación aprovecha numpy haciendo todos los casos F y S a la vez en una forma orientada a la matriz. Esto combinado con enlaces mkl para python conduce a una implementación muy rápida.
Tenga en cuenta también que solo cargar las bibliotecas e iniciar el intérprete toma 0.076s, por lo que el cálculo real tarda ~ 0.01 segundos, similar a la solución C ++.
fuente
python -c "import numpy; numpy.show_config()"
le mostrará si su versión de numpy está compilada contra blas / atlas / mkl, etc. ATLAS es un paquete matemático acelerado gratuito con el que numpy se puede vincular , Intel MKL generalmente tiene que pagar (a menos que sea un académico) y se puede vincular a numpy / scipy .MATLAB 0.024s
Computadora 1
Computadora 2
Decidí probar el tan lento Matlab. Si sabe cómo, puede deshacerse de la mayoría de los bucles (en Matlab), lo que lo hace bastante rápido. Sin embargo, los requisitos de memoria son más altos que para las soluciones en bucle, pero esto no será un problema si no tiene matrices muy grandes ...
Esto es lo que hago:
Supongo que no tienes matlab, lo cual es una pena, ya que realmente me hubiera gustado ver cómo se compara ...
(La función puede ser más lenta la primera vez que la ejecuta).
fuente
Julia: 0,30 s
Python de operación: 21.36 s (dúo Core2)
71x aceleración
Hice algunas modificaciones de la respuesta de Arman a Julia: en primer lugar, la envolví en una función, ya que las variables globales dificultan la inferencia de tipos de Julia y JIT: una variable global puede cambiar su tipo en cualquier momento, y debe verificarse en cada operación . Luego, me deshice de las funciones anónimas y las comprensiones de matriz. No son realmente necesarios y siguen siendo bastante lentos. Julia es más rápida con abstracciones de nivel inferior en este momento.
Hay muchas más formas de hacerlo más rápido, pero esto hace un trabajo decente.
fuente
Ok, estoy publicando esto solo porque siento que Java necesita ser representado aquí. Soy terrible con otros idiomas y confieso que no entiendo el problema exactamente, por lo que necesitaré ayuda para solucionar este código. Robé la mayor parte del código C del ejemplo as, y luego tomé prestados algunos fragmentos de otros. Espero que no sea un paso en falso ...
Una cosa que me gustaría señalar es que los lenguajes que se optimizan en tiempo de ejecución deben ejecutarse varias / muchas veces para alcanzar la velocidad máxima. Creo que está justificado tomar la velocidad totalmente optimizada (o al menos la velocidad promedio) porque la mayoría de las cosas con las que te preocupa correr rápido se ejecutarán muchas veces.
El código todavía necesita ser reparado, pero lo ejecuté de todos modos para ver qué horas obtendría.
Aquí están los resultados en una CPU Intel (R) Xeon (R) E3-1270 V2 @ 3.50GHz en Ubuntu ejecutándola 1000 veces:
servidor: / tmp # time java8 -cp. Ensayador
firstzero 40000
Bothzero 20000
primer tiempo de ejecución: 41 ms último tiempo de ejecución: 4 ms
usuario real 0m5.014s 0m4.664s sys 0m0.268s
Aquí está mi código de mierda:
E intenté ejecutar el código de Python después de actualizar Python e instalar Python-numpy, pero obtengo esto:
fuente
currentTimeMillis
para la evaluación comparativa (use la versión nano en el Sistema) y las ejecuciones de 1k pueden no ser suficientes para involucrar al JIT (1.5k para el cliente y 10k para el servidor serían los valores predeterminados, aunque llame a myRand con la frecuencia suficiente para que eso sea JITed, que debería hacer que se compilen algunas funciones en la pila de llamadas, lo que puede funcionar aquí). Por último, pero no menos importante, el débil PNRG está engañando, pero también lo hace la solución C ++ y otras, así que supongo que eso no es demasiado injusto.gettimeofday(&time, NULL)
para milisegundos que no es monotónico y no ofrece ninguna garantía de precisión (por lo que en algunas plataformas / núcleos son exactamente iguales) problemas como la implementación actual de Windows de TimeMillis, por lo que también está bien o ninguno lo está). nanoTime, por otro lado, usa loclock_gettime(CLOCK_MONOTONIC, &tp)
que claramente también es lo correcto para usar cuando se compara en Linux.Golang versión 45X de python en mi máquina en los siguientes códigos de Golang:
y los siguientes códigos de Python copiados desde arriba:
y el tiempo a continuación:
fuente
"github.com/yanatan16/itertools"
? ¿también dirías que esto funcionaría bien en múltiples goroutines?C # 0.135s
C # basado en la pitón simple de Alistair Buxton : 0.278s
C # paralelo: 0.135s
Python de la pregunta: 5.907s
Pitón simple de Alistair : 0.853s
En realidad, no estoy seguro de que esta implementación sea correcta: su resultado es diferente, si observa los resultados en la parte inferior.
Ciertamente hay algoritmos más óptimos. Simplemente decidí usar un algoritmo muy similar al de Python.
C de un solo hilo
Paralelo C #:
Prueba de salida:
Windows (.NET)
El C # es mucho más rápido en Windows. Probablemente porque .NET es más rápido que mono.
La sincronización del usuario y del sistema no parece funcionar (se usa
git bash
para la sincronización).Linux (mono)
fuente
Haskell: ~ 2000x de aceleración por núcleo
Compile con 'ghc -O3 -funbox-strict-fields -threaded -fllvm', y ejecute con '+ RTS -Nk' donde k es el número de núcleos en su máquina.
fuente
Rubí
Ruby (2.1.0) 0.277s
Ruby (2.1.1) 0.281s
Python (Alistair Buxton) 0.330s
Python (alemi) 0.097s
fuente
el hilo no estaría completo sin PHP
6.6x más rápido
PHP v5.5.9 -
1.2230.646 segundos;vs
Python v2.7.6 - 8.072 segundos
convolve
función simplificada un poco para ser más rápido$F
y$FS
verificaciones).Salidas:
Editar. La segunda versión del script funciona por solo
0.646 sec
:fuente
Solución F #
El tiempo de ejecución es 0.030s cuando se compila a x86 en el CLR Core i7 4 (8) @ 3.4 Ghz
No tengo idea si el código es correcto.
fuente
Q, 0.296 seg
Q es un lenguaje orientado a la colección (kx.com)
Código reescrito para explotar Q idiomático, pero ninguna otra optimización inteligente
Los lenguajes de script optimizan el tiempo del programador, no el tiempo de ejecución
Primer intento de codificación = no ganador, pero tiempo razonable (aprox. 30x de aceleración)
NOTAS.-
\S seed
\t sentence
mide el tiempo que consume esa oraciónfuente
Julia:
12.1496.929 sA pesar de sus afirmaciones de velocidad , ¡el tiempo inicial de compilación JIT nos detiene!
Tenga en cuenta que el siguiente código de Julia es efectivamente una traducción directa del código original de Python (sin optimizaciones) como una demostración de que puede transferir fácilmente su experiencia de programación a un lenguaje más rápido;)
Editar
Correr con
n = 8
toma 32.935 s. Teniendo en cuenta que la complejidad de este algoritmo esO(2^n)
, entonces4 * (12.149 - C) = (32.935 - C)
, dondeC
es una constante que representa el tiempo de compilación JIT. ResolviendoC
esto, encontramos queC = 5.2203
, sugiriendo que el tiempo de ejecución realn = 6
es de 6.929 s.fuente
Óxido, 6.6 ms, 1950x aceleración
Prácticamente una traducción directa del código de Alistair Buxton a Rust. Pensé en utilizar múltiples núcleos con rayón (concurrencia sin miedo), pero esto no mejoró el rendimiento, probablemente porque ya es muy rápido.
Y Cargo.toml, ya que uso dependencias externas:
Comparación de velocidad:
6625608 ns es de aproximadamente 6,6 ms. Esto significa 1950 veces la aceleración. Aquí hay muchas optimizaciones posibles, pero estaba buscando legibilidad en lugar de rendimiento. Una posible optimización sería usar matrices en lugar de vectores para almacenar opciones, ya que siempre tendrán
n
elementos. También es posible usar RNG que no sea XorShift, ya que si bien Xorshift es más rápido que el CSPRNG HC-128 predeterminado, es más lento que los algoritmos PRNG más ingenuos.fuente