J'ai ce code que j'ai écrit en Python / NumPy

from __future__ import division
import numpy as np
import itertools

n = 6
iters = 1000
firstzero = 0
bothzero = 0
""" The next line iterates over arrays of length n+1 which contain only -1s and 1s """
for S in itertools.product([-1, 1], repeat=n+1):
    """For i from 0 to iters -1 """
    for i in xrange(iters):
        """ Choose a random array of length n.
            Prob 1/4 of being -1, prob 1/4 of being 1 and prob 1/2 of being 0. """
        F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """The next loop just makes sure that F is not all zeros."""
        while np.all(F == 0):
            F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """np.convolve(F, S, 'valid') computes two inner products between
        F and the two successive windows of S of length n."""
        FS = np.convolve(F, S, 'valid')
        if FS[0] == 0:
            firstzero += 1
        if np.all(FS == 0):
            bothzero += 1

print("firstzero: %i" % firstzero)
print("bothzero: %i" % bothzero)

Il compte le nombre de fois où la convolution de deux tableaux aléatoires, l'un plus long que l'autre, avec une distribution de probabilité particulière, a un 0 à la première position ou un 0 aux deux positions.

J'ai parié avec un ami qui dit que Python est un langage terrible pour écrire du code qui doit être rapide. Il faut 9s sur mon ordinateur. Il dit que cela pourrait être fait 100 fois plus vite s'il était écrit dans une "langue appropriée".

Le défi est de voir si ce code peut effectivement être rendu 100 fois plus rapide dans la langue de votre choix. Je vais tester votre code et la semaine la plus rapide gagnera. Si quelqu'un obtient moins de 0,09, il gagne automatiquement et je perds.

Statut

• Python . 30 fois plus rapide par Alistair Buxon! Bien que ce ne soit pas la solution la plus rapide, c'est en fait mon préféré.
• Octave . 100 fois plus rapide par @Thethos.
• Rouille . 500 fois plus rapide par @dbaupp.
• C ++ . 570 fois plus rapide par Guy Sirton.
• C . 727 fois plus rapide par @ace.
• C ++ . Incroyablement rapide par @Stefan.

Les solutions les plus rapides sont maintenant trop rapides pour un temps raisonnable. J'ai donc augmenté n à 10 et positionné iters = 100000 pour comparer les meilleurs. Sous cette mesure, les plus rapides sont.

• C . 7.5s par @ace.
• C ++ . 1s par @Stefan.

Ma machine Les timings seront exécutés sur ma machine. Il s’agit d’une installation ubuntu standard sur un processeur AMD FX-8350 à huit cœurs. Cela signifie également que je dois pouvoir exécuter votre code.

Suivi posté Comme ce concours était un peu trop facile à obtenir une accélération x100, j'ai posté un suivi pour ceux qui veulent exercer leur expertise en gourou de la vitesse. Voyez-vous à quel point le python est lent (deuxième partie)?

C ++ bit magic

0.84ms avec RNG simple, 1.67ms avec c ++ 11 std :: knuth

0,16 ms avec une légère modification algorithmique (voir édition ci-dessous)

L'implémentation en python s'exécute en 7,97 secondes sur ma plate-forme. Donc, ceci est 9488 à 4772 fois plus rapide en fonction du choix de RNG que vous avez choisi.

#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;
}

Compiler en 64 bits pour des registres supplémentaires. Lorsque vous utilisez le générateur aléatoire simple, les boucles de convolve () s'exécutent sans accès mémoire, toutes les variables sont stockées dans les registres.

Fonctionnement: plutôt que de stocker Set en Ftant que tableaux en mémoire, il est stocké sous forme de bits dans un uint32_t.
En effet S, les nbits les moins significatifs sont utilisés lorsqu'un bit défini désigne un +1 et un bit non défini désigne un -1.
Fnécessite au moins 2 bits pour créer une distribution de [-1, 0, 0, 1]. Cela se fait en générant des bits aléatoires et en examinant les 16 bits les moins significatifs (appelés r) et les 16 bits les plus significatifs (appelés l). Si l & ~rnous supposons que F est +1, si ~l & rnous supposons que Fc'est -1. Sinon, la valeur Fest 0. Ceci génère la distribution que nous recherchons.

Nous avons maintenant S, posBitsavec un bit défini à chaque emplacement où F == 1 et negBitsun bit défini à chaque emplacement où F == -1.

Nous pouvons prouver que F * S(où * désigne la multiplication) est évalué à +1 dans la condition (S & posBits) | (~S & negBits). Nous pouvons également générer une logique similaire pour tous les cas où F * Sévalue à -1. Et enfin, nous savons quesum(F * S) s’évalue à 0 si et seulement s’il existe une quantité égale de -1 et de +1 dans le résultat. Ceci est très facile à calculer en comparant simplement le nombre de +1 bits et -1 bits.

Cette implémentation utilise des bits 32 bits, et le maximum n accepté est de 16. Il est possible d’échelonner l’implémentation à 31 bits en modifiant le code de génération aléatoire et à 63 bits en utilisant uint64_t au lieu de uint32_t.

modifier

La fonction de convolution suivante:

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);
}

coupe le temps d'exécution à 0.160-0.161ms. Le déroulement manuel de la boucle (non illustré ci-dessus) correspond à 0,150. Le moins trivial n = 10, iter = 100000 cas s’exécute en dessous de 250 ms. Je suis sûr que je peux obtenir moins de 50 ms en exploitant des cœurs supplémentaires, mais c'est trop facile.

Ceci est fait en libérant la branche de la boucle interne et en permutant les boucles F et S.
Si ce bothZeron’est pas nécessaire, je peux réduire le temps d’exécution à 0,02 ms en effectuant une boucle parcimonieuse sur tous les tableaux S possibles.

Python2.7 + Numpy 1.8.1: 10.242 s

Fortran 90+: 0.029 s 0.003 s 0.022 s 0.010 s

Bon sang, vous avez perdu votre pari! Pas une goutte de parallélisation ici aussi, juste le Fortran 90+.

EDIT J'ai pris l'algorithme de Guy Sirton pour permuter le tableau S(bonne découverte: D). J'avais apparemment aussi les -g -tracebackindicateurs de compilation actifs qui ralentissaient ce code à environ 0,017s. Actuellement, je compile ceci en tant que

ifort -fast -o convolve convolve_random_arrays.f90

Pour ceux qui n'ont pas ifort, vous pouvez utiliser

gfortran -O3 -ffast-math -o convolve convolve_random_arrays.f90

EDIT 2 : La diminution du temps d’exécution est due au fait que j’avais fait quelque chose de mal auparavant et que j’ai eu une réponse incorrecte. Le faire de la bonne manière est apparemment plus lent. Je n'arrive toujours pas à croire que le C ++ est plus rapide que le mien, je vais donc probablement passer un peu de temps cette semaine à essayer de régler le problème pour accélérer le processus.

EDIT 3 : En changeant simplement la section RNG à l'aide d'une section basée sur le RNG de BSD (comme suggéré par Sampo Smolander) et en éliminant la division constante par m1, j'ai réduit le temps d'exécution au même résultat que la réponse C ++ de Guy Sirton . L'utilisation de tableaux statiques (comme suggéré par Sharpie) laisse le temps d'exécution passer à celui d'exécution C ++! Yay Fortran! :RÉ

EDIT 4 Apparemment, cela ne compile pas (avec gfortran) et ne fonctionne pas correctement (valeurs incorrectes) car les entiers outrepassent leurs limites. J'ai apporté des corrections pour que cela fonctionne, mais cela nécessite d'avoir ifort 11+ ou gfortran 4.7+ (ou un autre compilateur qui le permet iso_fortran_envet du int64type F2008 ).

Voici le code:

program convolve_random_arrays
   use iso_fortran_env
   implicit none
   integer(int64), parameter :: a1 = 1103515245
   integer(int64), parameter :: c1 = 12345
   integer(int64), parameter :: m1 = 2147483648
   real, parameter ::    mi = 4.656612873e-10 ! 1/m1
   integer, parameter :: n = 6
   integer :: p, pmax, iters, i, nil(0:1), seed
   !integer, allocatable ::  F(:), S(:), FS(:)
   integer :: F(n), S(n+1), FS(2)

   !n = 6
   !allocate(F(n), S(n+1), FS(2))
   iters = 1000
   nil = 0

   !call init_random_seed()

   S = -1
   pmax = 2**(n+1)
   do p=1,pmax
      do i=1,iters
         F = rand_int_array(n)
         if(all(F==0)) then
            do while(all(F==0))
               F = rand_int_array(n)
            enddo
         endif

         FS = convolve(F,S)

         if(FS(1) == 0) then
            nil(0) = nil(0) + 1
            if(FS(2) == 0) nil(1) = nil(1) + 1
         endif

      enddo
      call permute(S)
   enddo

   print *,"first zero:",nil(0)
   print *," both zero:",nil(1)

 contains
   pure function convolve(x, h) result(y)
!x is the signal array
!h is the noise/impulse array
      integer, dimension(:), intent(in) :: x, h
      integer, dimension(abs(size(x)-size(h))+1) :: y
      integer:: i, j, r
      y(1) = dot_product(x,h(1:n-1))
      y(2) = dot_product(x,h(2:n  ))
   end function convolve

   pure subroutine permute(x)
      integer, intent(inout) :: x(:)
      integer :: i

      do i=1,size(x)
         if(x(i)==-1) then
            x(i) = 1
            return
         endif
         x(i) = -1
      enddo
   end subroutine permute

   function rand_int_array(i) result(x)
     integer, intent(in) :: i
     integer :: x(i), j
     real :: y
     do j=1,i
        y = bsd_rng()
        if(y <= 0.25) then
           x(j) = -1
        else if (y >= 0.75) then
           x(j) = +1
        else
           x(j) = 0
        endif
     enddo
   end function rand_int_array

   function bsd_rng() result(x)
      real :: x
      integer(int64) :: b=3141592653
      b = mod(a1*b + c1, m1)
      x = real(b)*mi
   end function bsd_rng
end program convolve_random_arrays

Je suppose que la question qui se pose maintenant est la suivante: allez-vous cesser d'utiliser Python à la mélasse lente et utiliser le Fortran rapide comme électrons-peut-déplacer;).

Python 2.7 - 0.882s 0.283s

(OP de l'original: 6.404s)

Edit: l'optimisation de Steven Rumbalski en précalculant les valeurs F. Avec cette optimisation, cpython bat 0.365s.

import itertools
import operator
import random

n=6
iters = 1000
firstzero = 0
bothzero = 0

choicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))

for S in itertools.product([-1,1], repeat = n+1):
    for i in xrange(iters):
        F = random.choice(choicesF)
        if not sum(map(operator.mul, F, S[:-1])):
            firstzero += 1
            if not sum(map(operator.mul, F, S[1:])):
                bothzero += 1

print "firstzero", firstzero
print "bothzero", bothzero

Le code original de l'OP utilise de tels tableaux minuscules; l'utilisation de Numpy ne présente aucun avantage, comme le montre cette implémentation en python pur. Mais voyez aussi cette implémentation numpy qui est trois fois plus rapide que mon code.

J'optimise également en ignorant le reste de la convolution si le premier résultat n'est pas nul.

Rouille: 0.011s

Python d'origine: 8.3

Une traduction directe de l'original Python.

extern crate rand;

use rand::Rng;

static N: uint = 6;
static ITERS: uint = 1000;

fn convolve<T: Num>(into: &mut [T], a: &[T], b: &[T]) {
    // we want `a` to be the longest array
    if a.len() < b.len() {
        convolve(into, b, a);
        return
    }

    assert_eq!(into.len(), a.len() - b.len() + 1);

    for (n,place) in into.mut_iter().enumerate() {
        for (x, y) in a.slice_from(n).iter().zip(b.iter()) {
            *place = *place + *x * *y
        }
    }
}

fn main() {
    let mut first_zero = 0;
    let mut both_zero = 0;
    let mut rng = rand::XorShiftRng::new().unwrap();

    for s in PlusMinus::new() {
        for _ in range(0, ITERS) {
            let mut f = [0, .. N];
            while f.iter().all(|x| *x == 0) {
                for p in f.mut_iter() {
                    match rng.gen::<u32>() % 4 {
                        0 => *p = -1,
                        1 | 2 => *p = 0,
                        _ => *p = 1
                    }
                }
            }

            let mut fs = [0, .. 2];
            convolve(fs, s, f);

            if fs[0] == 0 { first_zero += 1 }
            if fs.iter().all(|&x| x == 0) { both_zero += 1 }
        }
    }

    println!("{}\n{}", first_zero, both_zero);
}



/// An iterator over [+-]1 arrays of the appropriate length
struct PlusMinus {
    done: bool,
    current: [i32, .. N + 1]
}
impl PlusMinus {
    fn new() -> PlusMinus {
        PlusMinus { done: false, current: [-1, .. N + 1] }
    }
}

impl Iterator<[i32, .. N + 1]> for PlusMinus {
    fn next(&mut self) -> Option<[i32, .. N+1]> {
        if self.done {
            return None
        }

        let ret = self.current;

        // a binary "adder", that just adds one to a bit vector (where
        // -1 is the zero, and 1 is the one).
        for (i, place) in self.current.mut_iter().enumerate() {
            *place = -*place;
            if *place == 1 {
                break
            } else if i == N {
                // we've wrapped, so we want to stop after this one
                self.done = true
            }
        }

        Some(ret)
    }
}

• Compilé avec --opt-level=3
• Mon compilateur de rouille est une nuit récente : ( rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)pour être précis)

C ++ (VS 2012) - 0.026s 0.015s

Python 2.7.6 / Numpy 1.8.1 - 12s

Accélération ~ x 800.

L'écart serait beaucoup plus petit si les tableaux convolués étaient très grands ...

#include <vector>
#include <iostream>
#include <ctime>

using namespace std;

static unsigned int seed = 35;

int my_random()
{
   seed = seed*1664525UL + 1013904223UL; // numerical recipes, 32 bit

   switch((seed>>30) & 3)
   {
   case 0: return 0;
   case 1: return -1;
   case 2: return 1;
   case 3: return 0;
   }
   return 0;
}

bool allzero(const vector<int>& T)
{
   for(auto x : T)
   {
      if(x!=0)
      {
         return false;
      }
   }
   return true;
}

void convolve(vector<int>& out, const vector<int>& v1, const vector<int>& v2)
{
   for(size_t i = 0; i<out.size(); ++i)
   {
      int result = 0;
      for(size_t j = 0; j<v2.size(); ++j)
      {
         result += v1[i+j]*v2[j];
      }
      out[i] = result;
   }
}

void advance(vector<int>& v)
{
   for(auto &x : v)
   {
      if(x==-1)
      {
         x = 1;
         return;
      }
      x = -1;
   }
}

void convolve_random_arrays(void)
{
   const size_t n = 6;
   const int two_to_n_plus_one = 128;
   const int iters = 1000;
   int bothzero = 0;
   int firstzero = 0;

   vector<int> S(n+1);
   vector<int> F(n);
   vector<int> FS(2);

   time_t current_time;
   time(&current_time);
   seed = current_time;

   for(auto &x : S)
   {
      x = -1;
   }
   for(int i=0; i<two_to_n_plus_one; ++i)
   {
      for(int j=0; j<iters; ++j)
      {
         do
         {
            for(auto &x : F)
            {
               x = my_random();
            }
         } while(allzero(F));
         convolve(FS, S, F);
         if(FS[0] == 0)
         {
            firstzero++;
            if(FS[1] == 0)
            {
               bothzero++;
            }
         }
      }
      advance(S);
   }
   cout << firstzero << endl; // This output can slow things down
   cout << bothzero << endl; // comment out for timing the algorithm
}

Quelques notes:

• La fonction random étant appelée dans la boucle, j’ai opté pour un générateur congruentiel linéaire très léger (mais j’ai regardé généreusement les MSB).
• Ce n’est vraiment que le point de départ d’une solution optimisée.
• Ça n'a pas pris longtemps pour écrire ...
• Je parcoure toutes les valeurs de S en prenant S[0]le chiffre "le moins significatif".

Ajoutez cette fonction principale pour un exemple autonome:

int main(int argc, char** argv)
{
  for(int i=0; i<1000; ++i) // run 1000 times for stop-watch
  {
      convolve_random_arrays();
  }
}

C

Prend 0.015s sur ma machine, avec le code original de l'OP prenant ~ 7.7s. J'ai essayé d'optimiser en générant le tableau aléatoire et en convolution dans la même boucle, mais cela ne semble pas faire beaucoup de différence.

Le premier tableau est généré en prenant un entier, en l'écrivant en binaire et en changeant tous les 1 en -1 et tous les 0 en 1. Le reste doit être très simple.

Éditer: au lieu d’avoir nun int, nous avons maintenant nune constante définie par une macro, donc nous pouvons utiliser int arr[n];au lieu de malloc.

Edit2: Au lieu de la rand()fonction intégrée, cela implémente maintenant un PRNG xorshift. En outre, de nombreuses instructions conditionnelles sont supprimées lors de la génération du tableau aléatoire.

Instructions de compilation:

gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall ./test.c -o ./test

Code:

#include <stdio.h>
#include <time.h>

#define n (6)
#define iters (1000)
unsigned int x,y=34353,z=57768,w=1564; //PRNG seeds

/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
int myRand() {
    unsigned int t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

int main() {
    int firstzero=0, bothzero=0;
    int arr[n+1];
    unsigned int i, j;
    x=(int)time(NULL);

    for(i=0; i< 1<<(n+1) ; i++) {
        unsigned int tmp=i;
        for(j=0; j<n+1; j++) {
            arr[j]=(tmp&1)*(-2)+1;
            tmp>>=1;
        }
        for(j=0; j<iters; j++) {
            int randArr[n];
            unsigned int k, flag=0;
            int first=0, second=0;
            do {
                for(k=0; k<n; k++) {
                    randArr[k]=(1-(myRand()&3))%2;
                    flag+=(randArr[k]&1);
                    first+=arr[k]*randArr[k];
                    second+=arr[k+1]*randArr[k];
                }
            } while(!flag);
            firstzero+=(!first);
            bothzero+=(!first&&!second);
        }
    }
    printf("firstzero %d\nbothzero %d\n", firstzero, bothzero);
    return 0;
}

J

Je ne m'attends pas à battre tous les langages compilés, et quelque chose me dit que cela prendrait une machine miraculeuse pour obtenir moins de 0,09 seconde avec cela, mais j'aimerais quand même soumettre ce J, parce que c'est plutôt lisse.

NB. constants
num =: 6
iters =: 1000

NB. convolve
NB. take the multiplication table                */
NB. then sum along the NE-SW diagonals           +//.
NB. and keep the longest ones                    #~ [: (= >./) #/.
NB. operate on rows of higher dimensional lists  " 1
conv =: (+//. #~ [: (= >./) #/.) @: (*/) " 1

NB. main program
S  =: > , { (num+1) # < _1 1                NB. all {-1,1}^(num+1)
F  =: (3&= - 0&=) (iters , num) ?@$ 4       NB. iters random arrays of length num
FS =: ,/ S conv/ F                          NB. make a convolution table
FB =: +/ ({. , *./)"1 ] 0 = FS              NB. first and both zero
('first zero ',:'both zero ') ,. ":"0 FB    NB. output results

Cela prend environ 0,5 s sur un ordinateur portable de la décennie précédente, seulement environ 20 fois plus vite que le Python dans la réponse. La plupart du temps est passé convdedans parce que nous l'écrivons paresseusement (nous calculons la convolution entière) et en toute généralité.

Puisque nous savons des choses sur Set F, nous pouvons accélérer les choses en faisant des optimisations spécifiques pour ce programme. Le mieux que j'ai pu trouver est conv =: ((num, num+1) { +//.)@:(*/)"1—sélectionnez précisément les deux nombres qui correspondent des sommes diagonales aux éléments les plus longs de la convolution — ce qui réduit approximativement le temps de moitié.

Perl - 9.3X plus rapide ... amélioration de 830%

Sur mon ancien netbook, le code de l'OP prend 53 secondes; La version d'Alistair Buxton prend environ 6,5 secondes et la version suivante de Perl, environ 5,7 secondes.

use v5.10;
use strict;
use warnings;

use Algorithm::Combinatorics qw( variations_with_repetition );
use List::Util qw( any sum );
use List::MoreUtils qw( pairwise );

my $n         = 6;
my $iters     = 1000;
my $firstzero = 0;
my $bothzero  = 0;

my $variations = variations_with_repetition([-1, 1], $n+1);
while (my $S = $variations->next)
{
  for my $i (1 .. $iters)
  {
    my @F;
    until (@F and any { $_ } @F)
    {
      @F = map +((-1,0,0,1)[rand 4]), 1..$n;
    }

    # The pairwise function doesn't accept array slices,
    # so need to copy into a temp array @S0
    my @S0 = @$S[0..$n-1];

    unless (sum pairwise { $a * $b } @F, @S0)
    {
      $firstzero++;
      my @S1 = @$S[1..$n];  # copy again :-(
      $bothzero++ unless sum pairwise { $a * $b } @F, @S1;
    }
  }
}

say "firstzero ", $firstzero;
say "bothzero ", $bothzero;

Python 2.7 - numpy 1.8.1 avec des liaisons mkl - 0.086s

(OP de l'original: 6.404s) (Le python pur de Buxton: 0.270s)

import numpy as np
import itertools

n=6
iters = 1000

#Pack all of the Ses into a single array
S = np.array( list(itertools.product([-1,1], repeat=n+1)) )

# Create a whole array of test arrays, oversample a bit to ensure we 
# have at least (iters) of them
F = np.random.rand(int(iters*1.1),n)
F = ( F < 0.25 )*-1 + ( F > 0.75 )*1
goodrows = (np.abs(F).sum(1)!=0)
assert goodrows.sum() > iters, "Got very unlucky"
# get 1000 cases that aren't all zero
F = F[goodrows][:iters]

# Do the convolution explicitly for the two 
# slots, but on all of the Ses and Fes at the 
# same time
firstzeros = (F[:,None,:]*S[None,:,:-1]).sum(-1)==0
secondzeros = (F[:,None,:]*S[None,:,1:]).sum(-1)==0

firstzero_count = firstzeros.sum()
bothzero_count = (firstzeros * secondzeros).sum()
print "firstzero", firstzero_count
print "bothzero", bothzero_count

Comme le souligne Buxton, le code d'origine de l'OP utilise de tels tableaux minuscules; l'utilisation de Numpy ne présente aucun avantage. Cette implémentation exploite numpy en effectuant tous les cas F et S à la fois de manière orientée tableau. Cette combinaison avec les liaisons mkl pour python conduit à une implémentation très rapide.

Notez également que le simple chargement des bibliothèques et le démarrage de l'interpréteur prend 0,076 seconde, donc le calcul prend environ 0,01 seconde, comme pour la solution C ++.

MATLAB 0.024s

Ordinateur 1

• Code d'origine: ~ 3.3 s
• Code de Alistar Buxton: ~ 0.51 s
• Le nouveau code d'Alistar Buxton: ~ 0,25 s
• Code Matlab: ~ 0.024 s (Matlab est déjà en cours d'exécution)

Ordinateur 2

• Code d'origine: ~ 6.66 s
• Code de Alistar Buxton: ~ 0.64 s
• Le nouveau code d'Alistar Buxton:?
• Matlab: ~ 0,07 s (Matlab est déjà en cours d'exécution)
• Octave: ~ 0.07 s

J'ai décidé d'essayer le si lent Matlab. Si vous savez comment faire, vous pouvez vous débarrasser de la plupart des boucles (en Matlab), ce qui le rend assez rapide. Cependant, les besoins en mémoire sont plus importants que pour les solutions en boucle, mais cela ne sera pas un problème si vous ne disposez pas de très grands tableaux ...

function call_convolve_random_arrays
tic
convolve_random_arrays
toc
end

function convolve_random_arrays

n = 6;
iters = 1000;
firstzero = 0;
bothzero = 0;

rnd = [-1, 0, 0, 1];

S = -1 *ones(1, n + 1);

IDX1 = 1:n;
IDX2 = IDX1 + 1;

for i = 1:2^(n + 1)
    F = rnd(randi(4, [iters, n]));
    sel = ~any(F,2);
    while any(sel)
        F(sel, :) = rnd(randi(4, [sum(sel), n]));
        sel = ~any(F,2);
    end

    sum1 = F * S(IDX1)';
    sel = sum1 == 0;
    firstzero = firstzero + sum(sel);

    sum2 = F(sel, :) * S(IDX2)';
    sel = sum2 == 0;
    bothzero = bothzero + sum(sel);

    S = permute(S); 
end

fprintf('firstzero %i \nbothzero %i \n', firstzero, bothzero);

end

function x = permute(x)

for i=1:length(x)
    if(x(i)==-1)
        x(i) = 1;
            return
    end
        x(i) = -1;
end

end

Voici ce que je fais:

• utiliser la fonction Kyle Kanos pour permuter à travers S
• calculer tous les nombres aléatoires à la fois
• carte 1 à 4 à [-1 0 0 1]
• use La multiplication matricielle (la somme élémentaire (F * S (1: 5)) est égale à la multiplication matricielle de F * S (1: 5) '
• pour bothzero: ne calcule que les membres qui remplissent la première condition

Je suppose que vous n'avez pas matlab, ce qui est bien dommage car j'aurais vraiment aimé voir comment il se compare ...

(La fonction peut être plus lente la première fois que vous l'exécutez.)

Julia: 0.30 s

Op Python: 21.36 s (Core2 duo)

71 fois plus rapide

function countconv()                                                                                                                                                           
    n = 6                                                                                                                                                                      
    iters = 1000                                                                                                                                                               
    firstzero = 0                                                                                                                                                              
    bothzero = 0                                                                                                                                                               
    cprod= Iterators.product(fill([-1,1], n+1)...)                                                                                                                             
    F=Array(Float64,n);                                                                                                                                                        
    P=[-1. 0. 0. 1.]                                                                                                                                                                                                                                                                                                             

    for S in cprod                                                                                                                                                             
        Sm=[S...]                                                                                                                                                              
        for i = 1:iters                                                                                                                                                        
            F=P[rand(1:4,n)]                                                                                                                                                  
            while all(F==0)                                                                                                                                                   
                F=P[rand(1:4,n)]                                                                                                                                              
            end                                                                                                                                                               
            if  dot(reverse!(F),Sm[1:end-1]) == 0                                                                                                                           
                firstzero += 1                                                                                                                                                 
                if dot(F,Sm[2:end]) == 0                                                                                                                              
                    bothzero += 1                                                                                                                                              
                end                                                                                                                                                            
            end                                                                                                                                                                
        end                                                                                                                                                                    
    end
    return firstzero,bothzero
end

Julia apporta quelques modifications à la réponse d'Arman: Tout d'abord, je l'ai enveloppée dans une fonction, car les variables globales rendent difficile l'inférence de type de Julia et JIT: une variable globale peut changer de type à tout moment et doit être vérifiée à chaque opération. . Ensuite, je me suis débarrassé des fonctions anonymes et des compréhensions de tableaux. Ils ne sont pas vraiment nécessaires et sont encore assez lents. Julia est plus rapide avec les abstractions de niveau inférieur en ce moment.

Il y a beaucoup plus de moyens d'accélérer les choses, mais cela fait un travail décent.

Ok, je poste ceci simplement parce que j'estime que Java doit être représenté ici. Je suis terrible avec d’autres langues et j’avoue ne pas comprendre exactement le problème. Il me faut donc de l’aide pour corriger ce code. J'ai volé la plupart de l'exemple C de l'as de code, puis emprunté des extraits à d'autres. J'espère que ce n'est pas un faux pas ...

Une chose que je voudrais souligner est que les langages optimisés au moment de l'exécution doivent être exécutés plusieurs fois pour atteindre leur vitesse maximale. Je pense qu'il est justifié de prendre la vitesse entièrement optimisée (ou du moins la vitesse moyenne) car la plupart des choses qui vous intéressent de courir vite le seront plusieurs fois.

Le code doit encore être corrigé, mais je l’ai couru quand même pour voir le nombre de fois que j’aurais.

Voici les résultats obtenus sur un processeur Intel (R) Xeon (E) E3-1270 V2 à 3.50 GHz sous Ubuntu exécuté 1 000 fois:

serveur: / tmp # time java8 -cp. Testeur

firstzero 40000

bothzero 20000

premier temps d'exécution: 41 ms dernier temps d'exécution: 4 ms

réel 0m5.014s utilisateur 0m4.664 sys 0m0.268s

Voici mon code merdique:

public class Tester 
{
    public static void main( String[] args )
    {
        long firstRunTime = 0;
        long lastRunTime = 0;
        String testResults = null;
        for( int i=0 ; i<1000 ; i++ )
        {
            long timer = System.currentTimeMillis();
            testResults = new Tester().runtest();
            lastRunTime = System.currentTimeMillis() - timer;
            if( i ==0 )
            {
                firstRunTime = lastRunTime;
            }
        }
        System.err.println( testResults );
        System.err.println( "first run time: " + firstRunTime + " ms" );
        System.err.println( "last run time: " + lastRunTime + " ms" );
    }

    private int x,y=34353,z=57768,w=1564; 

    public String runtest()
    {
        int n = 6;
        int iters = 1000;
        //#define iters (1000)
        //PRNG seeds

        /* xorshift PRNG
         * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
         * Used under CC-By-SA */

            int firstzero=0, bothzero=0;
            int[] arr = new int[n+1];
            int i=0, j=0;
            x=(int)(System.currentTimeMillis()/1000l);

            for(i=0; i< 1<<(n+1) ; i++) {
                int tmp=i;
                for(j=0; j<n+1; j++) {
                    arr[j]=(tmp&1)*(-2)+1;
                    tmp>>=1;
                }
                for(j=0; j<iters; j++) {
                    int[] randArr = new int[n];
                    int k=0;
                    long flag = 0;
                    int first=0, second=0;
                    do {
                        for(k=0; k<n; k++) {
                            randArr[k]=(1-(myRand()&3))%2;
                            flag+=(randArr[k]&1);
                            first+=arr[k]*randArr[k];
                            second+=arr[k+1]*randArr[k];
                        }
                    } while(allzero(randArr));
                    if( first == 0 )
                    {
                        firstzero+=1;
                        if( second == 0 )
                        {
                            bothzero++;
                        }
                    }
                }
            }
         return ( "firstzero " + firstzero + "\nbothzero " + bothzero + "\n" );
    }

    private boolean allzero(int[] arr)
    {
       for(int x : arr)
       {
          if(x!=0)
          {
             return false;
          }
       }
       return true;
    }

    public int myRand() 
    {
        long t;
        t = x ^ (x << 11);
        x = y; y = z; z = w;
        return (int)( w ^ (w >> 19) ^ t ^ (t >> 8));
    }
}

Et j'ai essayé d'exécuter le code python après la mise à niveau de python et l'installation de python-numpy mais je comprends ceci:

server:/tmp# python tester.py
Traceback (most recent call last):
  File "peepee.py", line 15, in <module>
    F = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = n)
AttributeError: 'module' object has no attribute 'choice'

Golang version 45X de python sur ma machine en dessous des codes Golang:

package main

import (
"fmt"
"time"
)

const (
n     = 6
iters = 1000
)

var (
x, y, z, w = 34353, 34353, 57768, 1564 //PRNG seeds
)

/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
func myRand() int {
var t uint
t = uint(x ^ (x << 11))
x, y, z = y, z, w
w = int(uint(w^w>>19) ^ t ^ (t >> 8))
return w
}

func main() {
var firstzero, bothzero int
var arr [n + 1]int
var i, j int
x = int(time.Now().Unix())

for i = 0; i < 1<<(n+1); i = i + 1 {
    tmp := i
    for j = 0; j < n+1; j = j + 1 {
        arr[j] = (tmp&1)*(-2) + 1
        tmp >>= 1
    }
    for j = 0; j < iters; j = j + 1 {
        var randArr [n]int
        var flag uint
        var k, first, second int
        for {
            for k = 0; k < n; k = k + 1 {
                randArr[k] = (1 - (myRand() & 3)) % 2
                flag += uint(randArr[k] & 1)
                first += arr[k] * randArr[k]
                second += arr[k+1] * randArr[k]
            }
            if flag != 0 {
                break
            }
        }
        if first == 0 {
            firstzero += 1
            if second == 0 {
                bothzero += 1
            }
        }
    }
}
println("firstzero", firstzero, "bothzero", bothzero)
}

et les codes python ci-dessous copiés d'en haut:

import itertools
import operator
import random

n=6
iters = 1000
firstzero = 0
bothzero = 0

choicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))

for S in itertools.product([-1,1], repeat = n+1):
    for i in xrange(iters):
        F = random.choice(choicesF)
        if not sum(map(operator.mul, F, S[:-1])):
            firstzero += 1
            if not sum(map(operator.mul, F, S[1:])):
                bothzero += 1

print "firstzero", firstzero
print "bothzero", bothzero

et l'heure ci-dessous:

$time python test.py
firstzero 27349
bothzero 12125

real    0m0.477s
user    0m0.461s
sys 0m0.014s

$time ./hf
firstzero 27253 bothzero 12142

real    0m0.011s
user    0m0.008s
sys 0m0.002s

C # 0.135s

C # basé sur le python brut d' Alistair Buxton : 0.278s
C parallélisé: 0.135s
Python tiré de la question: 5.907s
Le python ordinaire d'Aristair: 0.853s

En réalité, je ne suis pas certain que cette implémentation est correcte - sa sortie est différente, si vous regardez les résultats plus bas.

Il y a certainement plus d'algorithmes optimaux. J'ai juste décidé d'utiliser un algorithme très similaire à celui de Python.

C simple filetage

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConvolvingArrays
{
    static class Program
    {
        static void Main(string[] args)
        {
            int n=6;
            int iters = 1000;
            int firstzero = 0;
            int bothzero = 0;

            int[] arraySeed = new int[] {-1, 1};
            int[] randomSource = new int[] {-1, 0, 0, 1};
            Random rand = new Random();

            foreach (var S in Enumerable.Repeat(arraySeed, n+1).CartesianProduct())
            {
                for (int i = 0; i < iters; i++)
                {
                    var F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
                    while (!F.Any(f => f != 0))
                    {
                        F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
                    }
                    if (Enumerable.Zip(F, S.Take(n), (f, s) => f * s).Sum() == 0)
                    {
                        firstzero++;
                        if (Enumerable.Zip(F, S.Skip(1), (f, s) => f * s).Sum() == 0)
                        {
                            bothzero++;
                        }
                    }
                }
            }

            Console.WriteLine("firstzero {0}", firstzero);
            Console.WriteLine("bothzero {0}", bothzero);
        }

        // itertools.product?
        // http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
        static IEnumerable<IEnumerable<T>> CartesianProduct<T>
            (this IEnumerable<IEnumerable<T>> sequences)
        {
            IEnumerable<IEnumerable<T>> emptyProduct =
              new[] { Enumerable.Empty<T>() };
            return sequences.Aggregate(
              emptyProduct,
              (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item }));
        }
    }
}

Parallèle C #:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ConvolvingArrays
{
    static class Program
    {
        static void Main(string[] args)
        {
            int n=6;
            int iters = 1000;
            int firstzero = 0;
            int bothzero = 0;

            int[] arraySeed = new int[] {-1, 1};
            int[] randomSource = new int[] {-1, 0, 0, 1};

            ConcurrentBag<int[]> results = new ConcurrentBag<int[]>();

            // The next line iterates over arrays of length n+1 which contain only -1s and 1s
            Parallel.ForEach(Enumerable.Repeat(arraySeed, n + 1).CartesianProduct(), (S) =>
            {
                int fz = 0;
                int bz = 0;
                ThreadSafeRandom rand = new ThreadSafeRandom();
                for (int i = 0; i < iters; i++)
                {
                    var F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
                    while (!F.Any(f => f != 0))
                    {
                        F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
                    }
                    if (Enumerable.Zip(F, S.Take(n), (f, s) => f * s).Sum() == 0)
                    {
                        fz++;
                        if (Enumerable.Zip(F, S.Skip(1), (f, s) => f * s).Sum() == 0)
                        {
                            bz++;
                        }
                    }
                }

                results.Add(new int[] { fz, bz });
            });

            foreach (int[] res in results)
            {
                firstzero += res[0];
                bothzero += res[1];
            }

            Console.WriteLine("firstzero {0}", firstzero);
            Console.WriteLine("bothzero {0}", bothzero);
        }

        // itertools.product?
        // http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
        static IEnumerable<IEnumerable<T>> CartesianProduct<T>
            (this IEnumerable<IEnumerable<T>> sequences)
        {
            IEnumerable<IEnumerable<T>> emptyProduct =
              new[] { Enumerable.Empty<T>() };
            return sequences.Aggregate(
              emptyProduct,
              (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item }));
        }
    }

    // http://stackoverflow.com/a/11109361/1030702
    public class ThreadSafeRandom
    {
        private static readonly Random _global = new Random();
        [ThreadStatic]
        private static Random _local;

        public ThreadSafeRandom()
        {
            if (_local == null)
            {
                int seed;
                lock (_global)
                {
                    seed = _global.Next();
                }
                _local = new Random(seed);
            }
        }
        public int Next()
        {
            return _local.Next();
        }
        public int Next(int maxValue)
        {
            return _local.Next(maxValue);
        }
    }
}

Test de sortie:

Windows (.NET)

Le C # est beaucoup plus rapide sous Windows. Probablement parce que .NET est plus rapide que mono.

Le timing utilisateur et système ne semble pas fonctionner (utilisé git bashpour le timing).

$ time /c/Python27/python.exe numpypython.py
firstzero 27413
bothzero 12073

real    0m5.907s
user    0m0.000s
sys     0m0.000s
$ time /c/Python27/python.exe plainpython.py
firstzero 26983
bothzero 12033

real    0m0.853s
user    0m0.000s
sys     0m0.000s
$ time ConvolvingArrays.exe
firstzero 28526
bothzero 6453

real    0m0.278s
user    0m0.000s
sys     0m0.000s
$ time ConvolvingArraysParallel.exe
firstzero 28857
bothzero 6485

real    0m0.135s
user    0m0.000s
sys     0m0.000s

Linux (mono)

bob@phoebe:~/convolvingarrays$ time python program.py
firstzero 27059
bothzero 12131

real    0m11.932s
user    0m11.912s
sys     0m0.012s
bob@phoebe:~/convolvingarrays$ mcs -optimize+ -debug- program.cs
bob@phoebe:~/convolvingarrays$ time mono program.exe
firstzero 28982
bothzero 6512

real    0m1.360s
user    0m1.532s
sys     0m0.872s
bob@phoebe:~/convolvingarrays$ mcs -optimize+ -debug- parallelprogram.cs
bob@phoebe:~/convolvingarrays$ time mono parallelprogram.exe
firstzero 28857
bothzero 6496

real    0m0.851s
user    0m2.708s
sys     0m3.028s

Haskell: ~ 2000x accélération par coeur

Compilez avec 'ghc -O3 -funbox-strict-fields -threaded -fllvm' et exécutez-le avec '+ RTS -Nk' où k est le nombre de cœurs de votre machine.

import Control.Parallel.Strategies
import Data.Bits
import Data.List
import Data.Word
import System.Random

n = 6 :: Int
iters = 1000 :: Int

data G = G !Word !Word !Word !Word deriving (Eq, Show)

gen :: G -> (Word, G)
gen (G x y z w) = let t  = x `xor` (x `shiftL` 11)
                      w' = w `xor` (w `shiftR` 19) `xor` t `xor` (t `shiftR` 8)
                  in (w', G y z w w')  

mask :: Word -> Word
mask = (.&.) $ (2 ^ n) - 1

gen_nonzero :: G -> (Word, G)
gen_nonzero g = let (x, g') = gen g 
                    a = mask x
                in if a == 0 then gen_nonzero g' else (a, g')


data F = F {zeros  :: !Word, 
            posneg :: !Word} deriving (Eq, Show)

gen_f :: G -> (F, G)       
gen_f g = let (a, g')  = gen_nonzero g
              (b, g'') = gen g'
          in  (F a $ mask b, g'')

inner :: Word -> F -> Int
inner s (F zs pn) = let s' = complement $ s `xor` pn
                        ones = s' .&. zs
                        negs = (complement s') .&. zs
                    in popCount ones - popCount negs

specialised_convolve :: Word -> F -> (Int, Int)
specialised_convolve s f@(F zs pn) = (inner s f', inner s f) 
    where f' = F (zs `shiftL` 1) (pn `shiftL` 1)

ss :: [Word]
ss = [0..2 ^ (n + 1) - 1]

main_loop :: [G] -> (Int, Int)
main_loop gs = foldl1' (\(fz, bz) (fz', bz') -> (fz + fz', bz + bz')) . parMap rdeepseq helper $ zip ss gs
    where helper (s, g) = go 0 (0, 0) g
                where go k u@(fz, bz) g = if k == iters 
                                              then u 
                                              else let (f, g') = gen_f g
                                                       v = case specialised_convolve s f
                                                               of (0, 0) -> (fz + 1, bz + 1)
                                                                  (0, _) -> (fz + 1, bz)
                                                                  _      -> (fz, bz)
                                                   in go (k + 1) v g'

seed :: IO G                                        
seed = do std_g <- newStdGen
          let [x, y, z, w] = map fromIntegral $ take 4 (randoms std_g :: [Int])
          return $ G x y z w

main :: IO ()
main = (sequence $ map (const seed) ss) >>= print . main_loop

Rubis

Ruby (2.1.0) 0.277s
Ruby (2.1.1) 0.281s
Python (Alistair Buxton) 0.330s
Python (normal) 0.097s

n = 6
iters = 1000
first_zero = 0
both_zero = 0

choices = [-1, 0, 0, 1].repeated_permutation(n).select{|v| [0] != v.uniq}

def convolve(v1, v2)
  [0, 1].map do |i|
    r = 0
    6.times do |j|
      r += v1[i+j] * v2[j]
    end
    r
  end
end

[-1, 1].repeated_permutation(n+1) do |s|
  iters.times do
    f = choices.sample
    fs = convolve s, f
    if 0 == fs[0]
      first_zero += 1
      if 0 == fs[1]
        both_zero += 1
      end
    end
  end
end

puts 'firstzero %i' % first_zero
puts 'bothzero %i' % both_zero

le fil ne serait pas complet sans PHP

6.6x plus rapide

PHP v5.5.9 - 1.223 0.646 sec;

contre

Python v2.7.6 - 8.072 sec

<?php

$n = 6;
$iters = 1000;
$firstzero = 0;
$bothzero = 0;

$x=time();
$y=34353;
$z=57768;
$w=1564; //PRNG seeds

function myRand() {
    global $x;
    global $y;
    global $z;
    global $w;
    $t = $x ^ ($x << 11);
    $x = $y; $y = $z; $z = $w;
    return $w = $w ^ ($w >> 19) ^ $t ^ ($t >> 8);
}

function array_cartesian() {
    $_ = func_get_args();
    if (count($_) == 0)
        return array();
    $a = array_shift($_);
    if (count($_) == 0)
        $c = array(array());
    else
        $c = call_user_func_array(__FUNCTION__, $_);
    $r = array();
    foreach($a as $v)
        foreach($c as $p)
            $r[] = array_merge(array($v), $p);
    return $r;
}

function rand_array($a, $n)
{
    $r = array();
    for($i = 0; $i < $n; $i++)
        $r[] = $a[myRand()%count($a)];
    return $r;
}

function convolve($a, $b)
{
    // slows down
    /*if(count($a) < count($b))
        return convolve($b,$a);*/
    $result = array();
    $w = count($a) - count($b) + 1;
    for($i = 0; $i < $w; $i++){
        $r = 0;
        for($k = 0; $k < count($b); $k++)
            $r += $b[$k] * $a[$i + $k];
        $result[] = $r;
    }
    return $result;
}

$cross = call_user_func_array('array_cartesian',array_fill(0,$n+1,array(-1,1)));

foreach($cross as $S)
    for($i = 0; $i < $iters; $i++){
        while(true)
        {
            $F = rand_array(array(-1,0,0,1), $n);
            if(in_array(-1, $F) || in_array(1, $F))
                break;
        }
        $FS = convolve($S, $F);
        if(0==$FS[0]) $firstzero += 1;
        if(0==$FS[0] && 0==$FS[1]) $bothzero += 1;
    }

echo "firstzero $firstzero\n";
echo "bothzero $bothzero\n";

• Utilisé un générateur aléatoire personnalisé (volé de la réponse C), PHP est nul et les chiffres ne correspondent pas
• convolve fonction simplifiée un peu pour être plus rapide
• La vérification de type tableau avec zéros uniquement est également très optimisée (voir $Fet $FScontrôles).

Les sorties:

$ time python num.py 
firstzero 27050
bothzero 11990

real    0m8.072s
user    0m8.037s
sys 0m0.024s
$ time php num.php
firstzero 27407
bothzero 12216

real    0m1.223s
user    0m1.210s
sys 0m0.012s

Modifier. La deuxième version du script fonctionne pour seulement 0.646 sec:

<?php

$n = 6;
$iters = 1000;
$firstzero = 0;
$bothzero = 0;

$x=time();
$y=34353;
$z=57768;
$w=1564; //PRNG seeds

function myRand() {
    global $x;
    global $y;
    global $z;
    global $w;
    $t = $x ^ ($x << 11);
    $x = $y; $y = $z; $z = $w;
    return $w = $w ^ ($w >> 19) ^ $t ^ ($t >> 8);
}

function array_cartesian() {
    $_ = func_get_args();
    if (count($_) == 0)
        return array();
    $a = array_shift($_);
    if (count($_) == 0)
        $c = array(array());
    else
        $c = call_user_func_array(__FUNCTION__, $_);
    $r = array();
    foreach($a as $v)
        foreach($c as $p)
            $r[] = array_merge(array($v), $p);
    return $r;
}

function convolve($a, $b)
{
    // slows down
    /*if(count($a) < count($b))
        return convolve($b,$a);*/
    $result = array();
    $w = count($a) - count($b) + 1;
    for($i = 0; $i < $w; $i++){
        $r = 0;
        for($k = 0; $k < count($b); $k++)
            $r += $b[$k] * $a[$i + $k];
        $result[] = $r;
    }
    return $result;
}

$cross = call_user_func_array('array_cartesian',array_fill(0,$n+1,array(-1,1)));

$choices = call_user_func_array('array_cartesian',array_fill(0,$n,array(-1,0,0,1)));

foreach($cross as $S)
    for($i = 0; $i < $iters; $i++){
        while(true)
        {
            $F = $choices[myRand()%count($choices)];
            if(in_array(-1, $F) || in_array(1, $F))
                break;
        }
        $FS = convolve($S, $F);
        if(0==$FS[0]){
            $firstzero += 1;
            if(0==$FS[1])
                $bothzero += 1;
        }
    }

echo "firstzero $firstzero\n";
echo "bothzero $bothzero\n";

Solution F #

Le temps d’exécution est de 0.030s lorsque compilé en x86 sur le CLR Core i7 4 (8) à 3.4 Ghz

Je n'ai aucune idée si le code est correct.

• Optimisation fonctionnelle (pli en ligne) -> 0.026s
• Bâtiment via le projet de console -> 0.022s
• Ajout d'un meilleur algorithme pour la génération des tableaux de permutation -> 0.018s
• Mono pour Windows -> 0.089s
• Exécution du script Python d'Alistair -> 0.259s

let inline ffoldi n f state =
    let mutable state = state
    for i = 0 to n - 1 do
        state <- f state i
    state

let product values n =
    let p = Array.length values
    Array.init (pown p n) (fun i ->
        (Array.zeroCreate n, i)
        |> ffoldi n (fun (result, i') j ->
            result.[j] <- values.[i' % p]
            result, i' / p
        )
        |> fst
    )

let convolute signals filter =
    let m = Array.length signals
    let n = Array.length filter
    let len = max m n - min m n + 1

    Array.init len (fun offset ->
        ffoldi n (fun acc i ->
            acc + filter.[i] * signals.[m - 1 - offset - i]
        ) 0
    )

let n = 6
let iters = 1000

let next =
    let arrays =
        product [|-1; 0; 0; 1|] n
        |> Array.filter (Array.forall ((=) 0) >> not)
    let rnd = System.Random()
    fun () -> arrays.[rnd.Next arrays.Length]

let signals = product [|-1; 1|] (n + 1)

let firstzero, bothzero =
    ffoldi signals.Length (fun (firstzero, bothzero) i ->
        let s = signals.[i]
        ffoldi iters (fun (first, both) _ ->
            let f = next()
            match convolute s f with
            | [|0; 0|] -> first + 1, both + 1
            | [|0; _|] -> first + 1, both
            | _ -> first, both
        ) (firstzero, bothzero)
    ) (0, 0)

printfn "firstzero %i" firstzero
printfn "bothzero %i" bothzero

Q, 0.296 seg

n:6; iter:1000  /parametrization (constants)
c:n#0           /auxiliar constant (sequence 0 0.. 0 (n))
A:B:();         /A and B accumulates results of inner product (firstresult, secondresult)

/S=sequence with all arrays of length n+1 with values -1 and 1
S:+(2**m)#/:{,/x#/:-1 1}'m:|n(2*)\1 

f:{do[iter; F:c; while[F~c; F:n?-1 0 0 1]; A,:+/F*-1_x; B,:+/F*1_x];} /hard work
f'S               /map(S,f)
N:~A; +/'(N;N&~B) / ~A is not A (or A=0) ->bitmap.  +/ is sum (population over a bitmap)
                  / +/'(N;N&~B) = count firstResult=0, count firstResult=0 and secondResult=0

Q est un langage orienté collection (kx.com)

Code réécrit pour expliquer Q idiomatique, mais pas d'autres optimisations intelligentes

Les langages de script optimisent le temps du programmeur, pas le temps d'exécution

• Q n'est pas le meilleur outil pour résoudre ce problème

Première tentative de codage = pas un gagnant, mais un temps raisonnable (environ 30 fois plus rapide)

• assez compétitif parmi les interprètes
• arrêter et choisir un autre problème

REMARQUES.-

• programme utilise la graine par défaut (execs répétables) Pour choisir une autre graine pour une utilisation aléatoire \S seed
• Le résultat est donné sous la forme d'une suite de deux ints, il y a donc un suffixe i final à la deuxième valeur 27421 12133i -> comme suit (27241, 12133)
• Temps ne comptant pas le démarrage de l'interprète. \t sentence mesure le temps consommé par cette phrase

Julia: 12.149 6.929 s

Malgré leurs prétentions de rapidité , le temps de compilation JIT initial nous retient!

Notez que le code Julia suivant est en réalité une traduction directe du code Python original (aucune optimisation n’est apportée) car il montre que vous pouvez facilement transférer votre expérience de programmation dans un langage plus rapide;)

require("Iterators")

n = 6
iters = 1000
firstzero = 0
bothzero = 0

for S in Iterators.product(fill([-1,1], n+1)...)
    for i = 1:iters
        F = [[-1 0 0 1][rand(1:4)] for _ = 1:n]
        while all((x) -> round(x,8) == 0, F)
            F = [[-1 0 0 1][rand(1:4)] for _ = 1:n]
        end
        FS = conv(F, [S...])
        if round(FS[1],8) == 0
            firstzero += 1
        end
        if all((x) -> round(x,8) == 0, FS)
            bothzero += 1
        end
    end
end

println("firstzero ", firstzero)
println("bothzero ", bothzero)

Modifier

Courir avec n = 8prend 32.935 s. Considérant que la complexité de cet algorithme est O(2^n), alors 4 * (12.149 - C) = (32.935 - C), où Cest une constante représentant le temps de compilation JIT. Résoudre pourCNous trouvons cela enC = 5.2203 , ce qui donne à penser que le temps d'exécution réel n = 6est de 6,929 s.

Rouille, 6,6 ms, accélération 1950x

Une bonne partie de la traduction directe du code d’ Alistair Buxton dans Rust. J'ai envisagé d'utiliser plusieurs cœurs avec de la rayonne (concurrence sans peur!), Mais cela n'a pas amélioré les performances, probablement parce que c'est déjà très rapide.

extern crate itertools;
extern crate rand;
extern crate time;

use itertools::Itertools;
use rand::{prelude::*, prng::XorShiftRng};
use std::iter;
use time::precise_time_ns;

fn main() {
    let start = precise_time_ns();

    let n = 6;
    let iters = 1000;
    let mut first_zero = 0;
    let mut both_zero = 0;
    let choices_f: Vec<Vec<i8>> = iter::repeat([-1, 0, 0, 1].iter().cloned())
        .take(n)
        .multi_cartesian_product()
        .filter(|i| i.iter().any(|&x| x != 0))
        .collect();
    // xorshift RNG is faster than default algorithm designed for security
    // rather than performance.
    let mut rng = XorShiftRng::from_entropy(); 
    for s in iter::repeat(&[-1, 1]).take(n + 1).multi_cartesian_product() {
        for _ in 0..iters {
            let f = rng.choose(&choices_f).unwrap();
            if f.iter()
                .zip(&s[..s.len() - 1])
                .map(|(a, &b)| a * b)
                .sum::<i8>() == 0
            {
                first_zero += 1;
                if f.iter().zip(&s[1..]).map(|(a, &b)| a * b).sum::<i8>() == 0 {
                    both_zero += 1;
                }
            }
        }
    }
    println!("first_zero = {}\nboth_zero = {}", first_zero, both_zero);

    println!("runtime {} ns", precise_time_ns() - start);
}

Et Cargo.toml, car j'utilise des dépendances externes:

[package]
name = "how_slow_is_python"
version = "0.1.0"

[dependencies]
itertools = "0.7.8"
rand = "0.5.3"
time = "0.1.40"

Comparaison de vitesse:

$ time python2 py.py
firstzero: 27478
bothzero: 12246
12.80user 0.02system 0:12.90elapsed 99%CPU (0avgtext+0avgdata 23328maxresident)k
0inputs+0outputs (0major+3544minor)pagefaults 0swaps
$ time target/release/how_slow_is_python
first_zero = 27359
both_zero = 12162
runtime 6625608 ns
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 2784maxresident)k
0inputs+0outputs (0major+189minor)pagefaults 0swaps

6625608 ns est d'environ 6,6 ms. Cela signifie 1950 fois plus rapide. Il y a beaucoup d'optimisations possibles ici, mais je visais la lisibilité plutôt que la performance. Une optimisation possible consisterait à utiliser des tableaux au lieu de vecteurs pour stocker les choix, car ils auront toujours des néléments. Il est également possible d’utiliser un autre groupe que XorShift, car si Xorshift est plus rapide que le CSPRNG HC-128 par défaut, il est plus lent que la plus naïve des algorithmes PRNG.