Mam ten kod, który napisałem w 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)

Zlicza liczbę razy, gdy splot dwóch losowych tablic, z których jeden jest dłuższy od drugiego, ze szczególnym rozkładem prawdopodobieństwa, ma 0 na pierwszej pozycji lub 0 na obu pozycjach.

Założyłem się z przyjacielem, który mówi, że Python jest okropnym językiem do pisania kodu, który musi być szybki. Na moim komputerze zajmuje to 9 sekund. Mówi, że można to zrobić 100 razy szybciej, jeśli zostanie napisane „właściwym językiem”.

Wyzwanie polega na sprawdzeniu, czy ten kod rzeczywiście może być 100-krotnie szybszy w dowolnym wybranym języku. Przetestuję twój kod, a najszybszy za tydzień wygra. Jeśli ktoś spadnie poniżej 0,09 s, automatycznie wygrywa, a ja przegrywam.

Status

• Python . 30 razy przyspieszone przez Alistaira Buxona! Chociaż nie jest to najszybsze rozwiązanie, w rzeczywistości jest moim ulubionym.
• Oktawa . 100-krotnie przyspieszone przez @Thethos.
• Rdza . 500 razy przyspieszy @dbaupp.
• C ++ . 570 razy przyspieszone przez Guy Sirton.
• C . 727 razy przyspieszone przez @ace.
• C ++ . Niewiarygodnie szybki @Stefan.

Najszybsze rozwiązania są teraz zbyt szybkie, aby rozsądnie je wyprzedzić. Dlatego zwiększyłem n do 10 i ustawiłem itery = 100000, aby porównać najlepsze. W ramach tej miary najszybsze są.

• C . 7,5 s @ace.
• C ++ . 1s @Stefan.

Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja ubuntu na ośmiordzeniowym procesorze AMD FX-8350. Oznacza to również, że muszę być w stanie uruchomić Twój kod.

Kontynuacja wysłana Ponieważ ta konkurencja była zbyt łatwa, aby uzyskać przyspieszenie x100, opublikowałem kontynuację dla tych, którzy chcą skorzystać ze swojej wiedzy guru szybkości. Zobacz, jak powolny jest Python (część II)?

C ++ nieco magiczna

0,84 ms z prostym RNG, 1,67 ms z c ++ 11 std :: knuth

0,16 ms z niewielką modyfikacją algorytmu (patrz edycja poniżej)

Implementacja Pythona działa na moim urządzeniu w 7,97 sekundy. Jest to więc 9488 do 4772 razy szybszy, w zależności od wybranego RNG.

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

Skompiluj w wersji 64-bitowej dla dodatkowych rejestrów. Podczas korzystania z prostego generatora losowego pętle w trybie splotowym () działają bez dostępu do pamięci, wszystkie zmienne są przechowywane w rejestrach.

Jak to działa: zamiast przechowywać Si Fjako tablice w pamięci, jest zapisywany jako bity w uint32_t.
W przypadku S, gdy nstosowane są najmniej znaczące bity, gdy ustawiony bit oznacza +1 i wyłączony nieco oznacza -1.
Fwymaga co najmniej 2 bitów, aby utworzyć rozkład [-1, 0, 0, 1]. Odbywa się to poprzez generowanie losowych bitów i badanie 16 najmniej znaczących (nazywanych r) i 16 najbardziej znaczących bitów (nazywanych l). Jeśli l & ~rzałożymy, że F wynosi +1, jeśli ~l & rzałożymy, że Fwynosi -1. W przeciwnym razie Fwynosi 0. To generuje rozkład, którego szukamy.

Teraz mamy S, posBitsz ustawionym bitem w każdej lokalizacji, w której F == 1 i negBitsz ustawionym bitem w każdym miejscu, w którym F == -1.

Możemy udowodnić, że F * S(gdzie * oznacza mnożenie) pod warunkiem warunkuje do +1 (S & posBits) | (~S & negBits). Możemy również wygenerować podobną logikę dla wszystkich przypadków, w których F * Swartość wynosi -1. I na koniec wiemy, że sum(F * S)ocenia się na 0 wtedy i tylko wtedy, gdy w wyniku jest równa liczba -1 i + 1. Jest to bardzo łatwe do obliczenia, po prostu porównując liczbę bitów +1 i -1 bitów.

Ta implementacja używa 32-bitowych liczb całkowitych, a maksymalna nakceptowana liczba to 16. Możliwe jest skalowanie implementacji do 31 bitów poprzez modyfikację kodu generowania losowego i do 63 bitów przy użyciu uint64_t zamiast uint32_t.

edytować

Następująca funkcja zwojowa:

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

skraca czas działania do 0.160-0.161ms. Ręczne rozwijanie pętli (nie pokazano powyżej) powoduje, że 0.150. Mniej banalne n = 10, iter = 100000 przypadków działa poniżej 250ms. Jestem pewien, że uda mi się go uzyskać poniżej 50 ms, wykorzystując dodatkowe rdzenie, ale to zbyt łatwe.

Odbywa się to poprzez zwolnienie gałęzi wewnętrznej pętli i zamianę pętli F i S.
Jeśli bothZeronie jest to wymagane, mogę skrócić czas pracy do 0,02 ms, rzadko zapętlając wszystkie możliwe tablice S.

Python2.7 + Numpy 1.8.1: 10.242 s

Fortran 90+: 0,029 s 0,003 s 0,022 s 0,010 s

Cholera prosta, przegrałeś zakład! Tu też nie ma kropli paralelizacji, tylko prosty Fortran 90+.

EDYCJA Wziąłem algorytm Guya Sirtona do permutacji tablicy S(dobre znalezisko: D). Najwyraźniej miałem również -g -tracebackaktywne flagi kompilatora, które spowalniały ten kod do około 0,017 s. Obecnie kompiluję to jako

ifort -fast -o convolve convolve_random_arrays.f90

Dla tych, którzy nie mają ifort, możesz użyć

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

EDYCJA 2 : Skrócenie czasu działania wynika z tego, że wcześniej robiłem coś złego i otrzymałem niepoprawną odpowiedź. Robienie tego we właściwy sposób jest najwyraźniej wolniejsze. Nadal nie mogę uwierzyć, że C ++ jest szybszy niż mój, więc prawdopodobnie spędzę trochę czasu w tym tygodniu, próbując ulepszyć to badziewie, aby to przyspieszyć.

EDYCJA 3 : Po prostu zmieniając sekcję RNG za pomocą jednej opartej na RNG BSD (jak sugeruje Sampo Smolander) i eliminując ciągłe dzielenie m1, skróciłem czas działania do tego samego, co odpowiedź C ++ autorstwa Guy Sirton . Użycie tablic statycznych (jak sugeruje Sharpie) obniża czas działania poniżej C ++! Yay Fortran! :RE

EDYCJA 4 Najwyraźniej to się nie kompiluje (z gfortranem) i nie działa poprawnie (nieprawidłowe wartości), ponieważ liczby całkowite przekraczają swoje limity. Wprowadziłem poprawki, aby upewnić się, że to działa, ale wymaga to posiadania albo ifort 11+, albo gfortran 4.7+ (lub innego kompilatora, który pozwala iso_fortran_envi int64rodzaju F2008 ).

Oto kod:

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

Podejrzewam, że teraz pytanie brzmi: czy przestaniesz używać Pythona wolno-jak-melasowego i użyjesz Fortrana szybko-jak-elektronowo-potrafiącego;).

Python 2,7 - 0,882 0,283

(Oryginał OP: 6.404s)

Edycja: Optymalizacja Stevena Rumbalskiego przez wstępne obliczenie wartości F. Dzięki tej optymalizacji cpython bije pypy o 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

Oryginalny kod OP używa tak małych tablic, że korzystanie z Numpy nie ma żadnej korzyści, co pokazuje ta czysta implementacja Pythona. Ale patrz także tę implementację numpy, która jest trzy razy szybsza niż mój kod.

Optymalizuję również, pomijając resztę splotu, jeśli pierwszy wynik nie jest równy zero.

Rdza: 0,011s

Oryginalny Python: 8.3

Proste tłumaczenie oryginalnego języka 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)
    }
}

• Kompilowany z --opt-level=3
• Mój kompilator rdzy to najnowsza noc : ( rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)a ściślej)

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

Python 2.7.6 / Numpy 1.8.1 - 12s

Przyspieszenie ~ x800.

Różnica byłaby znacznie mniejsza, gdyby zwinięte tablice były bardzo duże ...

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

Kilka uwag:

• Funkcja losowa jest wywoływana w pętli, więc wybrałem bardzo lekki liniowy generator kongruencjalny (ale hojnie spojrzałem na MSB).
• To naprawdę tylko punkt wyjścia do zoptymalizowanego rozwiązania.
• Nie trzeba było długo pisać ...
• Powtarzam wszystkie wartości S przyjmujące, S[0]że jest „najmniej znaczącą” cyfrą.

Dodaj tę główną funkcję do samodzielnego przykładu:

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

do

Zajmuje 0,015 s na moim komputerze, z oryginalnym kodem OP zajmuje ~ 7,7 s. Próbowałem zoptymalizować, generując losową tablicę i zwijając w tej samej pętli, ale wydaje się, że nie robi to dużej różnicy.

Pierwsza tablica jest generowana przez pobranie liczby całkowitej, zapisanie jej w postaci binarnej i zmianę wszystkich 1 na -1 i wszystkich 0 na 1. Reszta powinna być bardzo prosta.

Edycja: zamiast mieć njako int, teraz mamy njako stałą zdefiniowaną w makrze, więc możemy użyć int arr[n];zamiast malloc.

Edycja2: Zamiast wbudowanej rand()funkcji, teraz implementuje ona xorshift PRNG. Ponadto podczas generowania tablicy losowej usuwanych jest wiele instrukcji warunkowych.

Skompiluj instrukcje:

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

Kod:

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

jot

Nie spodziewam się pokonać żadnych skompilowanych języków i coś mi mówi, że zajęłoby to cudowną maszynę, aby uzyskać z tym mniej niż 0,09 s, ale i tak chciałbym przesłać to J, ponieważ jest to dość śliskie.

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

To trwa około 0,5 s na laptopie z poprzedniej dekady, tylko około 20 razy szybciej niż Python w odpowiedzi. Większość czasu spędza wconv ponieważ piszemy to leniwie (obliczamy cały splot) iw pełnej ogólności.

Ponieważ wiemy rzeczy o SiF możemy przyspieszyć, dokonując konkretnych optymalizacji dla tego programu. Najlepsze, co udało mi się wymyślić, to conv =: ((num, num+1) { +//.)@:(*/)"1wybranie dwóch liczb, które odpowiadają sumom diagonalnym i najdłuższym elementom splotu, co w przybliżeniu zmniejsza czas o połowę.

Perl - 9,3 razy szybszy ... 830% poprawy

Na moim starożytnym netbooku kod OP trwa 53 sekundy; Wersja Alistair Buxton zajmuje około 6,5 sekundy, a następna wersja Perla zajmuje około 5,7 sekundy.

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 z powiązaniami mkl - 0,086s

(Oryginał OP: 6,404 s) (czysty python Buxtona: 0,270 s)

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

Jak zauważa Buxton, oryginalny kod OP używa tak małych tablic, że korzystanie z Numpy nie przynosi żadnych korzyści. Ta implementacja wykorzystuje numpy, wykonując wszystkie przypadki F i S jednocześnie w sposób zorientowany na tablicę. To w połączeniu z powiązaniami mkl dla Pythona prowadzi do bardzo szybkiej implementacji.

Zauważ też, że samo ładowanie bibliotek i uruchomienie interpretera zajmuje 0,076s, więc faktyczne obliczenie zajmuje ~ 0,01 sekundy, podobnie jak w rozwiązaniu C ++.

MATLAB 0,024s

Komputer 1

• Kod oryginalny: ~ 3,3 s
• Kod Alistara Buxtona: ~ 0,51 s
• Nowy kod Alistara Buxtona: ~ 0,25 s
• Kod Matlab: ~ 0,024 s (Matlab już działa)

Komputer 2

• Kod oryginalny: ~ 6,66 s
• Kod Alistara Buxtona: ~ 0,64 s
• Nowy kod Alistara Buxtona:?
• Matlab: ~ 0,07 s (Matlab już działa)
• Oktawa: ~ 0,07 s

Postanowiłem spróbować och tak powolnego Matlaba. Jeśli wiesz jak, możesz pozbyć się większości pętli (w Matlabie), co czyni go dość szybkim. Jednak wymagania dotyczące pamięci są wyższe niż w przypadku rozwiązań zapętlonych, ale nie będzie to stanowić problemu, jeśli nie masz bardzo dużych tablic ...

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

Oto co robię:

• użyj funkcji Kyle Kanos do permutacji przez S
• obliczyć wszystkie n * itery liczb losowych jednocześnie
• mapa od 1 do 4 do [-1 0 0 1]
• użyj mnożenia macierzy (suma elementarna (F * S (1: 5)) jest równa mnożeniu macierzy F * S (1: 5) ”
• dla Bothzero: obliczaj tylko członków, którzy spełniają pierwszy warunek

Zakładam, że nie masz Matlaba, co jest bardzo złe, ponieważ naprawdę chciałbym zobaczyć, jak to wygląda ...

(Funkcja może działać wolniej przy pierwszym uruchomieniu).

Julia: 0,30 s

Op's Python: 21.36 s (duet Core2)

71-krotne przyspieszenie

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

Dokonałem pewnych modyfikacji odpowiedzi Juliana Armana: Po pierwsze, zawinąłem ją w funkcję, ponieważ zmienne globalne utrudniają wnioskowanie o typie Julii i JIT: Zmienna globalna może zmienić swój typ w dowolnym momencie i musi być sprawdzana przy każdej operacji . Potem pozbyłem się anonimowych funkcji i interpretacji tablic. Nie są tak naprawdę konieczne i wciąż są dość powolne. Julia jest teraz szybsza dzięki abstrakcjom niższego poziomu.

Jest o wiele więcej sposobów, aby przyspieszyć, ale robi to przyzwoitą robotę.

Ok, publikuję to tylko dlatego, że uważam, że Java musi być tutaj reprezentowana. Jestem okropny z innymi językami i przyznaję, że nie rozumiem dokładnie problemu, więc potrzebuję pomocy w naprawie tego kodu. Ukradłem większość przykładu C asa kodu, a potem pożyczyłem fragmenty od innych. Mam nadzieję, że to nie jest faux pas ...

Jedną rzeczą, na którą chciałbym zwrócić uwagę, jest to, że języki optymalizujące się w czasie wykonywania muszą być uruchamiane kilka / wiele razy, aby osiągnąć pełną prędkość. Myślę, że uzasadnione jest przyjęcie w pełni zoptymalizowanej prędkości (lub przynajmniej średniej prędkości), ponieważ większość rzeczy, które dotyczą szybkiego biegania, będą uruchamiane kilka razy.

Kod nadal wymaga poprawek, ale i tak go uruchomiłem, aby zobaczyć, o której godzinie.

Oto wyniki dla procesora Intel (R) Xeon (E) E3-1270 V2 @ 3.50GHz na Ubuntu z uruchomionym 1000 razy:

server: / tmp # time java8 -cp. Próbnik

firstzero 40000

Bothzero 20000

czas pierwszego uruchomienia: 41 ms czas ostatniego uruchomienia: 4 ms

rzeczywisty użytkownik 0m5.014s 0m4.664s sys 0m0.268s

Oto mój gówniany kod:

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

Próbowałem uruchomić kod Pythona po aktualizacji Pythona i zainstalowaniu python-numpy, ale otrzymuję to:

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 wersja 45X Pythona na mojej maszynie na poniższych kodach 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)
}

i poniższe kody python skopiowane z góry:

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

a czas poniżej:

$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,133

C # w oparciu o zwykły python Alistaira Buxtona : 0,278 s Sparaliżowany
C #: 0,135 s
Python z pytania: 5,907
s Zwykły python Alistaira: 0,853 s

Nie jestem pewien, czy ta implementacja jest poprawna - jej wyniki są inne, jeśli spojrzysz na wyniki na dole.

Z pewnością istnieją bardziej optymalne algorytmy. Właśnie zdecydowałem się użyć bardzo podobnego algorytmu do Pythona.

Jednowątkowy C

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

Równoległy 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);
        }
    }
}

Wyjście testowe:

Windows (.NET)

C # jest znacznie szybszy w systemie Windows. Prawdopodobnie dlatego, że .NET jest szybszy niż mono.

Czas użytkownika i sys wydaje się nie działać (używany git bashdo mierzenia czasu).

$ 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 przyspieszenie na rdzeń

Skompiluj z 'ghc -O3 -funbox-strict-fields -threaded -fllvm' i uruchom z '+ RTS -Nk' gdzie k jest liczbą rdzeni na twoim komputerze.

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

Rubin

Ruby (2.1.0) 0.277s
Ruby (2.1.1) 0.281s
Python (Alistair Buxton) 0.330s
Python (alemi) 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

wątek nie byłby kompletny bez PHP

6.6x szybszy

PHP v.5.5.9 - 1.223 0.646 s;

vs

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";

• Użyłem niestandardowego generatora losowego (skradzionego z odpowiedzi C), PHP jest do bani, a liczby nie pasują
• convolve funkcja została nieco uproszczona, aby być szybszym
• Sprawdzanie tylko tablic z zerami jest również bardzo zoptymalizowane (patrz $Fi $FSsprawdzanie).

Wyjścia:

$ 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

Edytować. Druga wersja skryptu działa tylko dla 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";

Rozwiązanie F #

Czas działania wynosi 0,030 s po skompilowaniu do x86 na CLR Core i7 4 (8) @ 3,4 Ghz

Nie mam pojęcia, czy kod jest poprawny.

• Optymalizacja funkcjonalna (krotnie w linii) -> 0,026s
• Budowanie za pośrednictwem projektu konsoli -> 0,022 s
• Dodano lepszy algorytm do generowania tablic permutacji -> 0,018s
• Mono dla Windows -> 0,089s
• Uruchamianie skryptu Python Alistair -> 0,259

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 to język zorientowany na kolekcję (kx.com)

Przepisano kod, aby wyjaśnić idiomatyczne Q, ale nie ma innych sprytnych optymalizacji

Języki skryptowe optymalizują czas programisty, a nie czas wykonywania

• Q nie jest najlepszym narzędziem do tego problemu

Pierwsza próba kodowania = nie zwycięzca, ale rozsądny czas (przyspieszenie około 30x)

• dość konkurencyjny wśród tłumaczy
• zatrzymaj się i wybierz inny problem

UWAGI. -

• program używa domyślnego ziarna (powtarzalne pliki wykonywalne) Aby wybrać inne ziarno do losowego użycia generatora \S seed
• Wynik podano jako kwantyfikator dwóch liczb całkowitych, więc końcowy i-sufiks ma drugą wartość 27421 12133i -> odczytany jako (27241, 12133)
• Czas nie licząc uruchomienia interpretera. \t sentence mierzy czas zajęty przez to zdanie

Julia: 12.149 6.929 s

Pomimo ich pretensji do szybkości , początkowy czas kompilacji JIT powstrzymuje nas!

Zauważ, że poniższy kod Julii jest faktycznie bezpośrednim tłumaczeniem oryginalnego kodu Pythona (bez optymalizacji) jako dowód na to, że możesz łatwo przenieść swoje doświadczenie programistyczne na szybszy język;)

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)

Edytować

Bieg z n = 8zajmuje 32,935 s. Biorąc pod uwagę, że złożoność tego algorytmu polega na O(2^n)tym 4 * (12.149 - C) = (32.935 - C), że Cjest stałą reprezentującą czas kompilacji JIT. Rozwiązujemy Cto C = 5.2203, co sugeruje, że faktyczny czas wykonania n = 6wynosi 6,929 s.

Rdza, 6,6 ms, przyspieszenie 1950x

Prawie bezpośrednie tłumaczenie kodu Alistaira Buxtona na Rust. Zastanawiałem się nad użyciem wielu rdzeni ze sztucznego jedwabiu (nieustraszona współbieżność!), Ale to nie poprawiło wydajności, prawdopodobnie dlatego, że jest już bardzo szybkie.

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

I Cargo.toml, ponieważ używam zależności zewnętrznych:

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

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

Porównanie prędkości:

$ 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 wynosi około 6,6 ms. Oznacza to 1950-krotne przyspieszenie. Możliwych jest tutaj wiele optymalizacji, ale chciałem raczej uzyskać czytelność niż wydajność. Jedną z możliwych optymalizacji byłoby użycie tablic zamiast wektorów do przechowywania wyborów, ponieważ zawsze będą miały nelementy. Możliwe jest także użycie RNG innego niż XorShift, ponieważ chociaż Xorshift jest szybszy niż domyślny CSPRNG HC-128, jest najwolniejszy niż naiwny algorytm PRNG.