Seberapa Lambat Sebenarnya Python (Bagian II)?

52

Ini adalah tindak lanjut dari Seberapa lambat sebenarnya Python? (Atau seberapa cepat bahasa Anda?) .

Ternyata agak terlalu mudah untuk mendapatkan speedup x100 untuk pertanyaan terakhir saya. Bagi mereka yang telah menikmati tantangan tetapi menginginkan sesuatu yang lebih keras di mana mereka benar-benar dapat menggunakan keterampilan tingkat rendah mereka, inilah bagian II. Tantangannya adalah untuk mendapatkan speedup x100 untuk kode python berikut seperti yang diuji di komputer saya.

Untuk membuatnya lebih sulit, saya menggunakan pypy kali ini. Waktu saat ini bagi saya adalah 1 menit dan 7 detik menggunakan pypy 2.2.1.

Aturan

  1. Orang pertama yang mengirimkan kode yang dapat saya jalankan, sudah benar dan x100 kali lebih cepat di komputer saya akan diberikan hadiah 50 poin.
  2. Saya akan memberikan penghargaan kepada kode tercepat setelah seminggu.
import itertools 
import operator 
import random

n = 8 
m  = 8 
iters = 1000  

# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m

# itertools.product creates an array of all possible combinations of the 
# args passed to it.
#
# Ex:
#   itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
#   itertools.product("AB", repeat=5) --> [
#    ('A', 'A', 'A', 'A', 'A'),
#    ('A', 'A', 'A', 'A', 'B'),
#    ('A', 'A', 'A', 'B', 'A'),
#    ('A', 'A', 'A', 'B', 'B'),
#    etc.
#   ]
for S in itertools.product([-1,1], repeat = n+m-1):
    for i in xrange(iters):
        F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        # if the array is made up of only zeros keep recreating it until
        # there is at least one nonzero value.
        while not any(F):
            F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        j = 0
        while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
            leadingzerocounts[j] +=1
            j += 1
print leadingzerocounts

Outputnya harus sama dengan

[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]

Anda harus menggunakan seed acak dalam kode Anda dan generator nomor acak apa pun yang cukup baik untuk memberikan jawaban yang dekat dengan yang di atas akan diterima.

Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.

Penjelasan kode

Kode ini berulang pada semua larik S dengan panjang n + m-1 yang dibuat untuk -1s dan 1s. Untuk setiap larik S, sampel 1000 larik acak non-nol F dengan panjang n terdiri dari -1,0 atau 1 dengan probabilitas 1/4, 1/2, / 14 untuk mengambil masing-masing nilai. Ini kemudian menghitung produk dalam antara F dan setiap jendela dengan panjang S sampai menemukan produk dalam yang tidak nol. Ia menambahkan 1 leadingzerocountspada setiap posisi itu menemukan nol produk dalam.

Status

  • Perl . 2,7 kali perlambatan oleh @tobyink. (Dibandingkan dengan pypy, bukan cpython.)

  • J . 39 kali percepatan oleh @Eelvex.

  • C . 59 kali dipercepat oleh @ace.
  • Julia . 197 kali lebih cepat tidak termasuk waktu mulai dengan @ satu menit lagi. 8,5 kali mempercepat termasuk waktu start up (lebih cepat menggunakan 4 prosesor dalam hal ini dari 8).
  • Fortran . 438 kali dipercepat oleh @ semi-ekstrinsik.
  • Rpython . 258 kali dipercepat oleh @primo.
  • C ++ . 508 kali dipercepat oleh @ilmale.

(Saya berhenti menghitung waktu perbaikan baru karena mereka terlalu cepat dan iters terlalu kecil.)


Itu menunjukkan bahwa waktu di bawah satu detik tidak dapat diandalkan dan juga beberapa bahasa memiliki biaya awal. Argumennya adalah bahwa jika Anda ingin menyertakan Anda juga harus memasukkan waktu kompilasi C / C ++ dll. Berikut adalah timing untuk kode tercepat dengan jumlah iterasi meningkat menjadi 100.000.

  • Julia . 42 detik dengan @ satu menit lagi.
  • C ++ . 14 detik oleh @GuySirton.
  • Fortran . 14s oleh @ semi-ekstrinsik.
  • C ++ . 12s oleh @ilmale.
  • Rpython . 18-an oleh @primo.
  • C ++ . 5d oleh @Stefan.

Pemenangnya adalah .. Stefan!

Tantangan tindak lanjut diposting. Seberapa tinggi Anda bisa pergi? (Tantangan coding + algoritma) . Yang ini lebih sulit.

Komunitas
sumber
3
sebuah penjelasan tentang apa yang seharusnya dicapai oleh kode akan menyenangkan, jadi kita dapat menulis ulang dan tidak sekadar porting
Einacio
6
" Orang pertama yang mengirimkan kode yang dapat saya jalankan, sudah benar dan x100 kali lebih cepat pada mesin saya segera menang dan kompetisi ditutup. " Apa tujuan menutup kompetisi seperti itu? Mengapa tidak menggunakan batas waktu tanggal seperti kebanyakan yang lain, sehingga kita dapat melihatnya semakin berkurang dalam bahasa lain?
grovesNL
5
@Einacio Itu ide yang bagus. Saya mengubah aturan yang saya harap tidak akan ada yang keberatan.
1
@Lembik Saya telah meningkatkan versi Fortran saya, membuatnya 2x lebih cepat lagi di mesin saya. Bisakah Anda mengatur waktu lagi? :)
semi-ekstrinsik
1
@ semi-ekstrinsik Selesai.

Jawaban:

13

C ++ bit magic

~ 16ms multithreaded, 56ms singlethreaded. ~ 4000 speedup.

(speedup didasarkan pada kode multithreaded pada i7-2820QM saya dan 1 menit 9 detik yang disebutkan dalam pertanyaan. Karena sistem OP memiliki kinerja single threaded yang lebih buruk daripada CPU saya, tetapi kinerja multi-threaded yang lebih baik saya berharap angka ini akurat)

Bagian multithreaded cukup tidak efisien karena pemijahan benang. Saya mungkin bisa melakukan yang lebih baik dengan memanfaatkan pustaka pekerjaan kustom saya tetapi yang satu memiliki bug di bawah sistem unix .. Untuk penjelasan dan kode yang hampir sama tanpa memasukkan threading ke https://codegolf.stackexchange.com/a/26485/20965 .

sunting

Saya memberi masing-masing utas itu sendiri RNG dan mengurangi panjang bit menjadi 32 yang mengurangi runtime oleh beberapa ms.

#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <array>
#include <tuple>
#include <memory>
#include <thread>
#include <future>
#include <string.h>


#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



void convolve()
{
    static const unsigned threadCount = 32;
    static const unsigned n = 8;
    static const unsigned m = 8;
    static const unsigned totalIters = 1000;
    static_assert( n <= 16, "packing of F fails when n > 16.");
    static uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;

    std::array< uint32_t, m * threadCount > out;
    std::vector< std::future<void> > threads;

    for( int threadId = 0; threadId < threadCount; threadId++)
    {
        threads.emplace_back( std::async( [&, threadId]
        {
            std::random_device rd;
            std::knuth_b gen(rd());
            uint32_t nextRandomNumber = gen();

            const unsigned iters = totalIters / threadCount;

            std::array< uint32_t, m > leadingZeros;
            for( auto& x : leadingZeros )
                x = 0;

            for( unsigned i = 0; i < iters; i++ )
            {
                // generate random bit mess
                uint32_t F;
                do {
                    // this funky looking construction shortens the dependancy chain of F
                    F = nextRandomNumber & fmask;
                    nextRandomNumber = gen();
                } 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 + m -1));
                // generate all possible N+1 bit strings
                // 1 = +1
                // 0 = -1
                while ( S-- )
                {
                    for( int shift = 0; shift < m; shift++ )
                    {
                        uint32_t s = (S >> shift) % ( 1 << n );
                        auto firstBits = (s & mask) ^ adjF;

                        if ( desiredBits == popcnt( firstBits ) )
                        {
                            leadingZeros[shift] = leadingZeros[shift] + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }

            memcpy( out.data() + (threadId * m), leadingZeros.data(), sizeof( leadingZeros[0] ) * m );
        } ));

    };

    std::array< uint32_t, m > leadingZeros;
    for( auto& x : leadingZeros )
        x = 0;

    for( auto& thread : threads )
    {
        thread.wait();
    }

    for( int i = 0; i < (threadCount * m); i++ )
    {
        leadingZeros[i % m] += out[i];
    }


    for( auto x : leadingZeros )
        std::cout << x << ", ";

    std::cout << std::endl;
}

int main()
{
    typedef std::chrono::high_resolution_clock clock;
    int rounds = 100;

    // do some rounds to get the cpu up to speed..
    for( int i = 0; i < rounds / 10; i++ )
    {
        convolve();
    }


    auto start = clock::now();

    for( int i = 0; i < rounds; i++ )
        convolve();

    auto end = clock::now();
    double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;

    std::cout << seconds/rounds*1000 << " msec/round" << std::endl;

    return 0;
}

Output sampel:

   6317312, 2515072, 1034368, 434048, 190144, 85200, 39804, 19168,
   6226944, 2481408, 1031168, 438080, 192896, 86816, 40484, 19490,
   6321152, 2524672, 1045376, 442880, 195680, 88464, 41656, 20212,
   6330624, 2517504, 1031104, 430208, 187696, 83976, 38976, 18708,
   6304768, 2510336, 1030720, 433056, 190880, 86824, 40940, 19840,
   6272512, 2494720, 1028160, 432352, 189168, 84752, 39540, 19052,
   6233600, 2507520, 1046912, 447008, 198224, 89984, 42092, 20292,
Stefan
sumber
Outputnya tidak benar saya pikir, mungkin ada bug? Bandingkan dengan apa yang ada dalam pertanyaan. Khususnya kolom terakhir harus berupa angka mendekati 19180.
@Lembik saya bisa melihat apa yang Anda maksud. Saya berpikir bahwa output acak tidak cukup acak yang terkadang membuat output funky. Dengan generator acak C ++ 11 berfungsi dengan baik. Saya akan memperbaiki kodenya hari ini.
Stefan
Saya mendapatkan Stefan.cpp: 104: 101: error: 'memcpy' tidak dideklarasikan dalam memcpy lingkup ini (out.data () + (threadId * m), leadingZeros.data (), sizeof (leadingZeros [0]) * m );
Saya pikir saya perlu memasukkan string.h. Coba lagi.
Stefan
Anda mengkompilasi ini dengan g ++ -O3 -std = c ++ 0x -pthread -Wl, - tidak diperlukan Stefan.cpp -o Stefan
16

C ++ x150 x450 x530

Alih-alih array saya menggunakan bit (dan dark magic).
Terima kasih @ace untuk fungsi acak yang lebih cepat.

Bagaimana cara kerjanya: bit ke-15 pertama dari integer smewakili array S[15]; nol mewakili -1, yang mewakili +1. Array Fdibuat dengan cara yang sama. Tetapi dengan dua bit untuk setiap simbol.

  • 00 mewakili -1
  • 01 dan 10 mewakili 0
  • 11 mewakili 1

Menyebabkan Sdan Fmemiliki representasi yang berbeda saya harus interleave Sdengan dirinya sendiri agar dapat dibandingkan F.

  • 0 (-1) menjadi 00 (-1 dalam representasi F)
  • 1 (+1) menjadi 11 (+1 dalam representasi F)

Sekarang kita cukup menggunakan Carnot untuk menghitung produk dalam. Ingat bahwa satu variabel hanya dapat mengasumsikan nilai 00 atau 11

0. 00 = 11 (-1 * -1 = +1)
0. 01 = 10 (-1 * 0 = 0)
0. 10 = 01 (-1 * 0 = 0)
0. 11 = 00 (-1 * +1 = -1)
1. 00 = 00 (+1 * -1 = -1)
1. 10 = 10 (+1 * 0 = 0)
1. 01 = 01 (+1 * 0 = 0)
1. 11 = 11 (+1 * +1 = +1)

Sepertinya bukan untukku. :)

Jumlah yang ada hanyalah permainan shift dan mask, tidak ada yang benar-benar rumit.

#include <array>
#include <ctime>

// From standford bithacks
// http://graphics.stanford.edu/~seander/bithacks.html
inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   static int b[] = { 1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

inline int32_t sumArray(int32_t v)
{
   static int b[] = { -1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

uint32_t x, y = 24252, z=57768, w=1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x<<1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   std::array<int, 8> leadingZero{0};
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for(int s = 0; s < maxS; ++s)
   {
      const int32_t x = interleaveBit(s);
      for(int i = 0; i < 1000; ++i)
      {
         int32_t random;
         do
         {
            random = 0xFFFF & myRand();
         }while(sumOnes(random) == 0);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j*2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if(sumArray(l) == 0)
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }

      }
   }
   for(int i = 7; i >= 0; --i)
   {
      printf("%d ", leadingZero[i]);
   }
   printf("\n");
   return 0;
}

Di sini keluaran sampel:

6332350 2525218 1041716 438741 192917 87159 41023 19908 

real 0m0.372s
user 0m0.371s
sys  0m0.001s

Program ini telah dikompilasi dengan:

gcc -std=c++11 -O3 -msse4.2 -Wall -lstdc++ 26371.cpp -o fastPy

pada Fedora 20 dengan gcc 4.8.2 Cpu adalah i7 8core.

Mungkin saya bisa mendapatkan beberapa parameter kompiler tweaker ms.

Sementara ini adalah waktu solusi OP pada mesin saya:

time pypy 26371.py
[6330609, 2523914, 1040885, 439303, 192708, 86987, 40710, 19498]

real 0m53.061s
user 0m53.016s
sys  0m0.022s

Sunting:

Hanya menambahkan openmp dan mengubah urutan untuk saya mendapatkan x3, yang mengarah ke peningkatan kinerja x450 terhadap kode OP. : D Dalam hal ini leadingZeroarray harus berupa atom. Global acak ... acak, mereka akan lebih acak.

 #pragma omp parallel for
 for(int i = 0; i < 1000; ++i)
 {
    int32_t random;
    do
    {
       random = 0xFFFF & myRand();
    }while(sumOnes(random) == 0);
    for(int s = 0; s < maxS; ++s)
    {
       const int32_t x = interleaveBit(s);
       int j = 7;
       while( j >= 0 )
       {
          const int32_t h = (x >> (j*2));
          const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
          if( sumArray(l) == 0 )
          {
             leadingZero[j]++;
          } else
          {
             break;
          }
          j--;
       }
    }
 }

perlu menambahkan -fopenmpke flag kompiler


Sunting: 2 Sebagai suggester oleh user71404 Saya mengubah fungsi sumOnes dan sumArray dan sekarang sangat cepat.

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

Dengan openmp lebih lambat, menyebabkan atom menambah terlalu banyak overhead.

real  0m0.253s
user  0m1.870s
sys   0m0.001s

Tanpa atom bahkan lebih cepat, tetapi saya mendapatkan hasil yang salah.

2137992 1147218 619297 321243 155815 70946 32919 15579

real   0m0.048s
user   0m0.338s
sys    0m0.001s

Untuk memahami sumArray pertimbangkan bahwa mewakili 16 bit dan array 8 angka.
00 tidak memiliki 1 dan mewakili -1
01 dan 10 memiliki satu 1 dan mewakili 0
11 memiliki dua 1 dan mewakili 1
Sehingga built-in menghitung jumlah bit yang ditetapkan ke 1 [ http://en.wikipedia.org/wiki/ Hamming_weight] dan untuk setiap grup kami menghapus 1. Cool.

sumOnes hanyalah ilmu hitam.

Di sini kompilasi flag dan kode terbaru.

gcc -std = c ++ 11 -mfpmath = sse -O3 -flto -march = asli -funroll-loop -Wall -lstdc ++

#include <cstdint>
#include <cstdio>
#include <ctime>

inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   /* 0xAAAA == 0b1010 1010 1010 1010 */
   return !!(0xAAAA & (v ^ ~(v << 1)));
}

inline int32_t sumArray(int32_t v)
{
   return __builtin_popcount(v) - 8;
}

uint32_t x, y = 24252, z = 57768, w = 1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x << 1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   int leadingZero[8] = { 0 };
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for( int i = 0; i < 1000; ++i )
   {
      int32_t random;
      do
      {
         random = 0xFFFF & myRand();
      } while(sumOnes(random) == 0 );
      for( int s = 0; s < maxS; ++s )
      {
         const int32_t x = interleaveBit(s);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j * 2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if( sumArray(l) == 0 )
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }
      }
   }
   printf("[%d, %d, %d, %d, %d, %d, %d, %d]\n",
      leadingZero[7], leadingZero[6],
      leadingZero[5], leadingZero[4],
      leadingZero[3], leadingZero[2],
      leadingZero[1], leadingZero[0]);
   return 0;
}
ilmale
sumber
Sekarang saya tidak sabar untuk menguji ini! Sayangnya ini tidak akan selama beberapa jam.
1
Berikut ini adalah dalam sunting yang disarankan, tetapi saya pikir itu mungkin lebih cocok sebagai komentar. Anda dapat mengganti sumOnes Anda, sumArray dengan yang berikut ini (sepertinya memberi saya kecepatan 2x lebih tinggi dari versi openmp). inline int32_t sumOnes(int32_t v) { /* 0xAAAA == 0b1010 1010 1010 1010 */ return !! (0xAAAA & (v ^ ~(v << 1))); } inline int32_t sumArray(int32_t v) { return __builtin_popcount(v) - 8; }ini disarankan oleh @ user71404
ace_HongKongIndependence
@ user71404: profiler mengatakan bahwa program menghabiskan semua waktunya di kedua fungsi itu, tapi kemarin saya sangat lelah memikirkan sesuatu yang lebih baik dari itu. Saya akan mencoba malam ini (UTC). Terima kasih.
ilmale
Maukah Anda mengubah cuplikan kode kedua menjadi salinan lengkap dan kode yang dapat dilewati? Saya pasti melakukan sesuatu yang salah dalam usaha saya untuk membuat kode openmp Anda bekerja sehingga ini akan banyak membantu.
Bagus. Saya pikir ini bisa dilakukan dengan operasi bit.
Guy Sirton
10

Julia: 0,7 detik, 120x lebih cepat

Seperti yang ditunjukkan oleh user20768, port langsung dari kode ke Julia sekitar dua kali lebih cepat dari PyPy. Tetapi kita dapat melakukan jauh lebih baik dari itu.

function pleadingzerocounts(; n = 8,
                              m = 8,
                              iters = 1000)
  @parallel (+) for S = 1:2^(8+8-1)
    leading_counts = zeros(Int, m)
    F = Array(Int, n)
    for i = 1:iters
      flag = 0
      while flag == 0
        for i = 1:n
          v = (1-(rand(Int8)&3))%2
          @inbounds F[i] = v
          flag += v & 1
        end
      end
      for j = 1:m
        sum = 0
        for i = 1:n
          @inbounds sum += S & (1 << (j + i - 2)) > 0 ? F[i] : -F[i]
        end
        sum == 0 ?
          (leading_counts[j] += 1) :
          break
      end
    end
    leading_counts
  end
end

function main()
  # Warm up the JIT
  pleadingzerocounts()
  # Then go for real
  println(@time pleadingzerocounts())
end

Anda dapat menjalankan ini menggunakan julia -p 8 -e 'require("golf.jl");main()'(8 adalah jumlah proses, Anda mungkin ingin bermain dengannya). Pada pra-rilis terbaru Julia ini membutuhkan 0,7 vs 1m22 untuk PyPy.

Jika Anda memiliki cukup inti di komputer Anda, dan mungkin memutar beberapa instance AWS, Anda harus dapat mencukur lagi :)

satu menit lagi
sumber
Saya yakin Anda salah mengukur waktunya. Python dengan Pypy juga merupakan bahasa berbasis JIT, tetapi timing yang dibuat oleh OP termasuk waktu kompilasi JIT. Anda mengecualikannya. Saya menginstal versi terbaru git Julia dan menguji kode Anda, dan pada mesin saya perintah Anda dengan 8 proses membutuhkan 6,6 detik untuk menyelesaikan, tetapi ia mencetak "waktu berlalu 0,588 .. detik".
semi-ekstrinsik
Waktu Python tidak termasuk startup PyPy dan pemanasan JIT, tapi itu membutuhkan waktu paling banyak detik - perbedaan selama satu menit runtime diabaikan. Saya senang jika OP mengubah cara Python diatur waktunya (tidak akan ada bedanya), tetapi termasuk waktu startup Julia tidak masuk akal.
satu menit lagi
Saya bertanya pada OP di komentar untuk pertanyaan asli, dan dia berkata, "Waktu harus mencakup segalanya untuk bahasa JIT." Dia juga menyatakan akan menciptakan tantangan baru di mana solusi akan memakan waktu lebih lama dari 1 detik, meninggalkan Julia dalam kompetisi.
semi-ekstrinsik
Dalam hal ini solusi optimal adalah dengan menggunakan algoritma serial - yang memakan waktu sekitar 2 detik. Saya telah menerbitkan kode tetapi kompetisi ini sekarang agak berlebihan, karena semua orang sudah tahu bahwa C ++ melakukan booting lebih cepat dari yang lainnya.
satu menit lagi
Saya baru saja memposting solusi Fortran saya, jadi saya tidak melihat mengapa Anda tidak harus memposting yang tercepat Julia (jika Anda sudah memiliki kode).
semi-ekstrinsik
5

C, 1.210-an

Dengan kode OP menjalankan 1m45.729 di mesin saya.

Kompilasi:

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

Terima kasih khusus: @dyp untuk flag kompilasi dan ide-ide untuk optimisasi.

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

#define n (8)
#define m (8)
#define iters (1000)
int leadingzerocounts[m]; // declared as global so initialised to 0
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 dotproduct(int*F, int*S) {
    unsigned int i;
    int sum=0;
    for(i=0; i<n; i++) {
        sum+=F[i]*S[i];
    }
    return sum;
}

int main() {
    unsigned int i, j, tmp;
    x=(int)time(NULL); //seed PRNG

    int S[n+m-1];
    for(i=0; i<(1<<(n+m-1)); i++) {
        tmp=i;
        for(j=0; j<n+m-1; j++) {
            S[j]=(tmp&1)*(-2)+1;
            tmp>>=1;
        }
        for(j=0; j<iters; j++) {
            int F[n];
            unsigned int k, flag=0;
            do {
                for(k=0; k<n; k++) {
                    F[k]=(1-(myRand()&3))%2;
                    flag+=(F[k]&1);
                }
            } while(!flag);
            for(k=0; k<m&&!dotproduct(F, S+k); k++) {
                leadingzerocounts[k]++;
            }
        }
    }
    for(i=0; i<m; i++) printf("%d ", leadingzerocounts[i]);
    return 0;
}

Output sampel:

6334411 2527506 1042239 439328 192914 87005 40847 19728
ace_HongKongIndependence
sumber
1
Menarik memang, saya bisa melakukan pengamatan serupa ketika menjatuhkan semua bendera optimasi. Coba -march=native -fwhole-program -fstrict-aliasing -ftree-vectorizeBtw. Saya turun ke <4 s dengan menggunakan beberapa C ++ 11 termasuk MT19937 plus a uniform_int_distribution.
dyp
1
1,119 membuat speedup sekitar 59!
1
@ Ya, saya hanya ingin menunjukkan ini. Lebih mudah bagi saya hanya untuk mencoba beberapa PRNG perpustakaan standar dalam C ++. Perhatikan bahwa Anda dapat menggunakan satu hasil bilangan bulat 32-bit dari PRNG untuk menghasilkan 8 entri F.
dyp
1
Karena nsama dengan 8, Anda mungkin dapat menggunakan AVX (atau 2 * SSE) untuk menghitung dotproduct dengan Spenyimpanan yang tepat .
Michael M.
2
Versi SSE, percepatan kecil: gist.github.com/anonymous/11394210 (jangan lupa sertakan smmintrin.h)
Michael M.
5

Perl

Ini tidak mendekati secepat solusi C, tetapi saya kira cukup cepat untuk bahasa yang ditafsirkan tingkat tinggi. Ini mencukur sekitar 40% dari waktu berjalan implementasi Python.

#!/usr/bin/env perl

use v5.10;
use strict;
use warnings;
use Algorithm::Combinatorics qw( variations_with_repetition );
use List::Util qw( any sum );

use constant {
  N        => 8,
  M        => 8,
  ITERS    => 1000,
};

my @leadingzerocounts;

my $variations = variations_with_repetition([-1, 1], N + M - 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;
    }

    my $j = 0;
    while ($j < M)
    {
      last if sum map $F[$_]*$S->[$j+$_], 0..N-1;
      $leadingzerocounts[$j++]++;
    }
  }
}

say join ", ", @leadingzerocounts;

Algoritma :: Combinatorics tersedia di Ubuntu ( sudo apt-get install libalgorithm-combinatorics-perl). Modul lain yang digunakan adalah modul inti Perl, jadi harus sudah diinstal sebagai bagian dari instalasi dasar Ubuntu.

tobyink
sumber
1
Itu tidak akan memengaruhi kecepatan, tetapi 0..N-1berkisar pada yang terakhir map, bukan? Apakah kamu lupa use warnings? :-) Meskipun logika dalam OP membingungkan, jendela geser tidak pernah sampai ke elemen terakhir S.
user2846289
Ah. Saya baru saja membayangkan bahwa array berukuran tidak cocok, jadi saya menonaktifkan warningsmemungkinkan elemen yang hilang diperlakukan sebagai nol. N-1meningkatkan ini. Dan itu benar-benar meningkatkan kecepatan sangat sedikit - sekarang sekitar 40% lebih cepat daripada implementasi Python.
tobyink
Saya pikir kode Anda memerlukan versi List :: Util yang sangat modern. Di ubuntu 14.04 saya mendapatkan "any" tidak diekspor oleh List :: Util module
Oh ya, itu benar - Anda mungkin perlu menginstal List :: Util off CPAN. anyatau dapat ditemukan di List :: MoreUtils, yang walaupun bukan modul inti adalah salah satu modul CPAN yang paling umum digunakan.
tobyink
4

Julia: 4.66x lebih lambat!

Saya benar-benar mulai meragukan statistik di situs web mereka ...

Perhatikan bahwa kode Julia berikut ini secara efektif merupakan transkripsi langsung dari kode Python OP tanpa optimisasi apa pun. Saya menggunakan time()fungsi ini untuk mengecualikan waktu startup Julia yang lambat ...

srand(27182818284590)
t = time()

require("Iterators")

n = 8
m = 8
iters = 1000
bothzero = 0
leadingzerocounts = zeros(m)

for S in Iterators.product(fill([-1,1], n+m-1)...)
    for i = 1:iters
        F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        while all((x) -> x == 0, F)
            F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        end
        j = 1
        while j <= m && sum(map(*, F, S[j:j+n-1])) == 0
            leadingzerocounts[j] += 1
            j += 1
        end
    end
end

println(leadingzerocounts)

t = time() - t
println("$t seconds")

Julia: 5 m 32,912 dtk

Kode OP dalam PyPy: 1 m 11,506 dtk

Output Julia:

6332170
2525472
1041522
438761
193119
86873
40705
19662
agar gesit
sumber
7
Beri +1 untuk sportifitas <s> Anda yang tidak tahu malu </s>.
ace_HongKongIndependence
Variabel global, impor, dan pemahaman array lambat. Ini bukan bagaimana orang biasanya menulis program Julia untuk kinerja.
Alex A.
4

RPython 0.187s (258x lebih cepat)

Sumber Asli dengan PyPy2.2.1: 1m 6.718s

Sekarang dengan threading, dukungan kembali untuk standar Python telah dibatalkan. Jumlah utas pekerja dapat ditentukan sebagai parameter baris perintah, standarnya adalah dua.

from time import time, sleep
from math import fmod

from rpython.rlib.rthread import start_new_thread, allocate_lock, get_ident
class Random:
  __slots__ = ['s']

  def __init__(self, s=1):
    self.s = s

  def init_genrand(self, seed):
    self.s = seed

  def genrand32(self):
    # xorshift PRNG with period 2^32-1
    # see http://core.kmi.open.ac.uk/download/pdf/6250138.pdf
    self.s ^= (self.s << 13)
    self.s ^= (self.s >> 17)
    self.s ^= (self.s << 5)
    return self.s

class ThreadEnv:
  __slots__ = ['n', 'm', 'iters', 'counts', 'running', 'lock']

  def __init__(self):
    self.n = 8
    self.m = 8
    self.iters = 1000
    self.counts = [0]*8
    self.running = 0
    self.lock = None

env = ThreadEnv()
truth = [-1,0,0,1]

def main(argv):
  argc = len(argv)
  if argc < 4 or argc > 5:
    print 'Usage: %s N M ITERS [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 5:
    num_threads = int(argv[4])
  else:
    num_threads = 2

  env.n = int(argv[1])
  env.m = int(argv[2])
  env.iters = int(argv[3]) // num_threads
  env.counts = [0]*env.m
  env.lock = allocate_lock()

  for i in xrange(num_threads-1):
    start_new_thread(run,())
    env.running += 1

  env.running += 1

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.01)

  print env.counts
  return 0

def run():
  n, m, iters = env.n, env.m, env.iters
  counts = [0]*m
  sbits = [0]*(n+m-1)

  random = Random()
  seed = int(fmod(time(), 2147483.648)*1000) ^ get_ident()
  random.init_genrand(seed)

  for S in xrange(1<<n+m-1):
    i = 0
    sbit = 0
    while not sbit:
      sbits[i] ^= 3
      sbit = sbits[i]
      i += 1

    for i in xrange(iters):
      f = 0
      while not f:
        F = random.genrand32()

        G, x = F, 0
        for k in xrange(n):
          x += truth[(G&3)^sbits[k]]
          f |= x
          G >>= 2

      if not x:
        counts[0] += 1
        for j in xrange(1, m):
          G, x = F, 0
          for k in xrange(j, n+j):
            x += truth[(G&3)^sbits[k]]
            G >>= 2
          if x: break
          counts[j] += 1

  # passing True stalls until a lock can be obtained
  env.lock.acquire(True)

  for i in xrange(m):
    env.counts[i] += counts[i]
  env.running -= 1

  env.lock.release()

def target(*args):
  return main, None

RPython adalah subset terbatas dari Python, yang dapat diterjemahkan ke C dan kemudian dikompilasi menggunakan RPython Toolchain . Tujuannya adalah untuk membantu dalam menciptakan penerjemah bahasa, tetapi juga dapat digunakan untuk menyusun program-program sederhana seperti yang di atas. Sebagian besar fitur 'pelamun' dari Python, seperti itertoolsatau bahkan maptidak tersedia.

Untuk mengkompilasi, buat klon lokal repositori pypy saat ini , dan jalankan yang berikut:

$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution.py

Eksekusi yang dihasilkan akan diberi nama convolution-catau serupa di direktori kerja saat ini.

Saya telah parameterkan variabel input, sehingga program harus dijalankan sebagai:

convolution-c 8 8 1000

untuk mencocokkan kode sampel.


Catatan Implementasi

S in itertools.product([-1,1], repeat = n+m-1)menjadi S in xrange(1<<n+m-1), menafsirkan Ssebagai bit map: [ 0, 1] → [ -1, 1]

Demikian juga, Fjuga peta bit, dengan masing-masing dua bit mewakili nilai tunggal:
[ 00, 01, 10, 11] → [ -1, 0, 0, 1]

Tabel kebenaran digunakan untuk mencari produk, daripada melakukan mulitplikasi.

Karena bilangan bulat bertanda 32-bit digunakan, nmungkin tidak lebih besar dari 15, dan n+mtidak lebih besar dari 31. Dukungan bilangan bulat sewenang-wenang dapat dicapai dengan rpython.rlib.rbigintmodul, jika perlu.

Iterasi pertama dari loop titik-produk tidak terbuka, dan dikombinasikan dengan uji nolitas F.

PRNG homebrew digunakan, sumber terdaftar. Penulis makalah ini menunjukkan periode 2 32 -1, dan mengklaim bahwa ia lulus semua tes Diehard kecuali satu, walaupun saya belum secara pribadi mengkonfirmasi hal ini.

Benih acak berubah setiap milidetik, yang memungkinkan menggunakan stempel waktu. Selain itu, setiap pekerja memasang xorid proses mereka dengan nilai ini, untuk memastikan bahwa mereka masing-masing memiliki seed yang berbeda.


Contoh waktu

2 utas pekerja:

$ timeit convolution-c 8 8 1000 2
[6331845, 2526161, 1042330, 440018, 193724, 87147, 40943, 19603]

Elapsed Time:     0:00:00.375
Process Time:     0:00:00.687
System Calls:     6927

4 utas pekerja:

$ timeit convolution-c 8 8 1000 4
[6334565, 2527684, 1043502, 440216, 193225, 87398, 40799, 19338]

Elapsed Time:     0:00:00.218
Process Time:     0:00:00.796
System Calls:     3417

8 thread pekerja:

$ timeit convolution-c 8 8 1000 8
[6327639, 2522483, 1039869, 437884, 192460, 86771, 40420, 19403]

Elapsed Time:     0:00:00.187
Process Time:     0:00:00.734
System Calls:     3165

Sumber asli OP:

$ timeit pypy convolution-orig.py
[6330610, 2525644, 1041481, 438980, 193001, 86622, 40598, 19449]

Elapsed Time:     0:01:06.718
Process Time:     0:01:06.718
System Calls:     11599808

Waktu untuk 100000 iterasi:

$ timeit convolution-c 8 8 100000 8
[633156171, 252540679, 104129386, 43903716, 19307215, 8709157, 4072133, 1959124]

Elapsed Time:     0:00:16.625
Process Time:     0:01:02.406
System Calls:     171341
primo
sumber
Saya belum pernah melihat program rpython sebelumnya. Ini bagus. Sekarang adakah program python murni yang dapat dijalankan di 1.03s?
@Lembik Saya ingin melihatnya. Saya pikir 4.7s cukup bagus, mengingat upaya pertama saya di python murni adalah ~ 15s.
Primo
Ya, maaf atas keterlambatannya. Saya belum menjalankan kode tetapi akan sesegera mungkin.
Anda harus mencoba menambahkan JIT. Sekarang, itu akan cepat!
kirbyfan64sos
@Lembik terima kasih atas penyebutannya;) Karena penasaran, apakah ini berjalan tercepat dengan 4 utas pekerja, atau 8?
Primo
3

Julia: 1 menit 21,4 detik (lebih cepat 2,2x) (modifikasi kode Arman)

Kode op dalam PyPy: 3 mnt 1.4 dtk

Keduanya dilakukan dalam REPL, tidak termasuk waktu untuk memuat paket.

function foo()                                                                                                                                                             
    n = 8                                                                                                                                                                  
    m = 8                                                                                                                                                                  
    iters = 1000                                                                                                                                                           
    bothzero = 0                                                                                                                                                           
    leadingzerocounts = zeros(Int,m)                                                                                                                                       
    P=[-1,0,0,1]                                                                                                                                                           

    for S in Iterators.product(fill([-1,1], n+m-1)...)                                                                                                                     
        Sm=[S...]                                                                                                                                                          
        for i = 1:iters                                                                                                                                                    
            F = P[rand(1:4,n)]                                                                                                                                             
            while all(F==0)                                                                                                                                                
                F = P[rand(1:4,n)]                                                                                                                                         
            end                                                                                                                                                            
            j = 1                                                                                                                                                          

            while j <= m && dot(F,Sm[j:j+n-1]) == 0                                                                                                                        
                leadingzerocounts[j] += 1                                                                                                                                  
                j += 1                                                                                                                                                     
            end                                                                                                                                                            
        end                                                                                                                                                                
    end                                                                                                                                                                    

    println(leadingzerocounts)                                                                                                                                             
end 

Ada beberapa masalah dengan kode Arman membuatnya sangat lambat: Menggunakan banyak fungsi anonim dan fungsi urutan yang lebih tinggi tidak perlu. Untuk menguji apakah semua vektor F adalah nol, mengapa tidak hanya menulis semua (F == 0) alih-alih semua (x-> x == 0, F)? Ini lebih pendek, dan seribu kali lebih cepat.

Itu juga menggunakan jumlah (peta (*, x, y)) sebagai produk titik bukan hanya titik (x, y). Versi pertama 650 kali lebih lambat untuk vektor 10k ganda. Dan fungsi titik produk diimplementasikan sebagai untuk loop di Julia murni.

Juga, pemahaman array lambat. Lebih baik menulis [0,1,0, -1] [rand (1: 4, n)] daripada [[-1 0 0 1] [rand (1: 4)] untuk j = 1: n] .

Akhirnya, variabel global adalah juju buruk di Julia. Julia hanya cepat jika Anda menulis kode sedemikian rupa yang memungkinkan JIT dan ketik inferensi untuk bekerja. Sebagian besar dari ini adalah stabilitas tipe: Compiler harus dapat memastikan bahwa tipe variabel tidak akan berubah saat berada di dalam loop, misalnya.

pengguna20768
sumber
Terima kasih! Saya melihat bahwa saya masih memiliki sedikit belajar tentang Bahasa Julia sebelum saya dapat membuat klaim tentang kecepatannya :) Sangat senang melihat bahwa beberapa perbaikan sepele pada kode saya meningkatkan waktu eksekusi beberapa kali lipat.
agar gesit
2

Nimrod

import times, locks, strutils, unsigned

const
  N = 8
  M = 8
  iters = 1000
  numThreads = 8

type
  SVec = array[0..N+M-1, int]
  FVec = array[0..N-1, int]
  ComputeThread = TThread[int]

var
  rngSeed = int(epochTime()*1000)
  totalLeadingZeros: array[0..M-1, int]
  lock: TLock

type
  RNGState = object
    x, y, z, w: uint32

proc newRNG(seed: int): RNGState =
  result.x = uint32(seed)

proc random(rng: var RNGState): int =
  let t = rng.x xor (rng.x shl 11)
  rng.x = rng.y; rng.y = rng.z; rng.z = rng.w
  rng.w = rng.w xor (rng.w shr 19) xor t xor (t shr 8)
  result = int(rng.w)

proc initVecRand(v: var FVec, rng: var RNGState) =
  const values = [ -1, 0, 0, 1 ]
  var rnd = rng.random
  var bitAcc = 0
  for i in 0 .. <len(v):
    let val = values[rnd and 3]
    rnd = rnd shr 2
    v[i] = val
    bitAcc = bitAcc or val
  if bitAcc == 0:
    initVecRand(v, rng)

proc convolve(s: SVec, f: FVec, offset: int): int =
  for i in 0 .. <len(f):
    result += s[i+offset]*f[i]

proc iterate(v: var SVec) =
  for i in 0 .. <len(v):
    if v[i] == -1:
      v[i] = 1
      return
    v[i] = -1

proc mainThread(id: int) {.thread.} =
  const numS = 1 shl (N+M-1)
  var
    s: SVec
    f: FVec
    leadingZeros: array[0..M-1, int]
    rng = newRNG(rngSeed + id)
  for k in 0 .. <len(s):
    s[k] = -1
  for i in 1..numS:
    for j in countUp(id, iters, numThreads):
      initVecRand(f, rng)
      if convolve(s, f, 0) == 0:
        leadingZeros[0] += 1
        for k in 1 .. <M:
          if convolve(s, f, k) == 0:
            leadingZeros[k] += 1
          else:
            break
    iterate(s)
  acquire(lock)
  for i in 0 .. <M:
    totalLeadingZeros[i] += leadingZeros[i]
  release(lock)

proc main =
  let startTime = epochTime()
  var threads: array[1..numThreads, ComputeThread]
  initLock(lock)
  for i in 1..numThreads:
    createThread(threads[i], mainThread, i)
  for i in 1..numThreads:
    joinThread(threads[i])
  echo("Leading zeros: ", @totalLeadingZeros)
  let endTime = epochTime()
  echo("Time taken:    ", formatFloat(endTime - startTime, ffDecimal, 3),
       " seconds")

main()

Contoh output:

Leading zeros: @[6333025, 2525808, 1042466, 439138, 192391, 86751, 40671, 19525]
Time taken:    0.145 seconds

Nimrod mengkompilasi ke C, oleh karena itu pilihan kompiler C untuk hal-hal backend juga.

Menggunakan dentang, kompilasi dengan:

nimrod cc --threads:on --cc=clang --passc:-flto -d:release conv.nim

Menggunakan gcc, kompilasi dengan:

nimrod cc --threads:on --cc=gcc --passc:-flto -d:release conv.nim

Hapus --passc:-fltojika Anda memiliki kompiler C lama yang tidak mendukung KPP. Hapus --cc=...opsi jika Anda baik-baik saja dengan pilihan default untuk kompiler C. Kode membutuhkan Nimrod 0.9.4 atau 0.9.5 .

Pada quadcore iMac saya (2,66 GHz core i5), kode ini berjalan sekitar 0,15 detik dengan gcc 4,9, 0,16 detik dengan dentang, dibandingkan dengan 88 detik untuk PyPy 2.2.1 (yaitu percepatan 500 kali). Sayangnya, saya tidak memiliki akses ke mesin dengan lebih dari empat core yang juga telah menginstal PyPy atau di mana saya dapat dengan mudah menginstal PyPy, meskipun saya mendapatkan sekitar 0,1 detik (dengan banyak suara pengukuran) pada AMD 64-core Opteron 6376 1.4 GHz (menurut / proc / cpuinfo) dengan gcc 4.4.6.

Implementasi mencoba untuk setia pada kode asli daripada mengoptimalkan kode dengan biaya keterbacaan, sementara tidak meninggalkan optimasi yang jelas. Yang cukup menarik, rekursi ekor initVecRand()sedikit lebih cepat daripada loop dengan instruksi istirahat dengan gcc dan dentang. Membuka gulungan secara manual satu iterasi dari convolveloop tes di dalam loop utama juga menghasilkan percepatan, mungkin karena prediksi cabang yang lebih baik.

Reimer Behrends
sumber
Bagaimana Anda mendapatkan nimrod untuk ubuntu?
@Lembik Pencarian Google yang cepat akan memberi Anda nimrod-lang.org/download.html
ace_HongKongIndependence
@ace Saya juga telah memasukkan tautan dalam posting saya (meskipun sulit untuk melihat dengan warna biru hitam sekarang saya melihatnya).
Reimer Behrends
Anda bisa mempercepat ini lebih banyak lagi dengan meningkatkan ukuran seed menjadi 128 bit: xorshift.di.unimi.it
user60561
2

Jawa

Saya menerjemahkan solusi C ++ di atas ke Java:

import java.util.Random;
import java.util.Arrays;

public class Bench2 {
  public static int[] bits = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
  public static int[] oneValues = { 1, 0, 0, 1 };
  public static int[] values = { -1, 0, 0, 1 };
  public static int n = 8;
  public static int m = 8;
  public static int iters = 1000;

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

  public static void main( String[] args ) {
    x = (int) (System.currentTimeMillis()/1000l);

    int[] leadingzerocounts = new int[ m ];
    Arrays.fill( leadingzerocounts, 0 );

    int maxS = 1 << 15;

    for( int s = 0; s < maxS; s++ ) {
      int x = interleaveBit( s );

      for( int i=0; i<iters; i++ ) {
        int random;

        do {
          random = 0xFFFF & fastRandom( );
        } while( sumOnes( random ) == 0 );

        int j = 7;

        while( j >= 0 ) {
          int h = ( x >> (j*2) );
          int l = 0xFFFF & (~(random ^ h));

          if( sumArray( l ) == 0 ) {
            leadingzerocounts[ j ]++;
          } else {
            break;
          }

          j--;
        }
      }
    }

    for( int i = 7; i >= 0; --i ) {
      System.out.print( leadingzerocounts[ i ] + " " );
    }

    System.out.println( );
  }

  public static int interleaveBit( int x ) {
    x = (x | ( x << 8)) & bits[3];
    x = (x | ( x << 4)) & bits[2];
    x = (x | ( x << 2)) & bits[1];
    x = (x | ( x << 1)) & bits[0];
    return x | (x << 1);
  }

  public static int sumOnes( int v ) {
    return (0xAAAA & (v ^ ~(v << 1)));
    // int s = 0;

    // for( int i = 0; i < 8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += oneValues[ a ];
    // }

    // return s;
  }

  public static int sumArray( int v ) {
    return Integer.bitCount( v ) - 8;
    // int s = 0;

    // for( int i=0; i<8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += values[ a ];
    // }

    // return s;
  }

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

Di mesin saya, saya mendapatkan output berikut untuk program java:

time java Bench2
6330616 2524569 1040372 439615 193290 87131 40651 19607 
java Bench2  0.36s user 0.02s system 102% cpu 0.371 total

Program OPs berjalan sekitar 53 detik di mesin saya:

time pypy start.py
[6330944, 2524897, 1040621, 439317, 192731, 86850, 40830, 19555]
pypy start.py  52.96s user 0.06s system 99% cpu 53.271 total

Program c ++ dijalankan hanya sekitar 0,15 detik:

time ./benchcc
[6112256, 2461184, 1025152, 435584, 193376, 87400, 40924, 19700]
./benchcc  0.15s user 0.00s system 99% cpu 0.151 total

Itu sekitar 2,5x lebih cepat dari solusi java yang sesuai (saya tidak mengecualikan VM startup). Solusi java ini sekitar 142x lebih cepat dari program yang dijalankan dengan PyPy.

Karena saya tertarik secara pribadi, saya menetapkan iterske 100_000 untuk Java dan C ++ tetapi faktor 2.5 tidak berkurang untuk Java jika ada yang lebih besar.

EDIT: Saya menjalankan program pada PC Linux 64bit Arch.

EDIT2: Saya ingin menambahkan bahwa saya mulai dengan terjemahan kasar dari kode python:

import java.util.Random;
import java.util.Arrays;

public class Bench {
    public static int[] values = { -1, 0, 0, 1 };
    public static int n = 8;
    public static int m = 8;
    public static int iters = 1000;

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

    public static void main( String[] args ) {
        x = (int) (System.currentTimeMillis()/1000l);

        int[] leadingzerocounts = new int[ m ];
        Arrays.fill( leadingzerocounts, 0 );

        int[] S = new int[ n+m-1 ];
        Arrays.fill( S, -1 );

        do {
            for( int i=0; i<iters; i++ ) {
                int[] F = new int[ n ];

                do {
                    randomArray( F );
                } while( containsOnlyZeros( F ) );

                for( int j=0; j < m && check( F, S, j ); j++ ) {
                    leadingzerocounts[ j ] += 1;
                }
            }
        } while( next( S ) );

        System.out.println( Arrays.toString( leadingzerocounts ) );
    }

    public static void randomArray( int[] F ) {
        for( int i = 0; i<F.length; i++ ) {
            F[ i ] = (1-(fastRandom()&3))%2;
        }
    }

    public static boolean containsOnlyZeros( int[] F ) {
        for( int x : F ) {
            if( x != 0 ) {
                return false;
            }
        }

        return true;
    }

    public static boolean next( int[] S ) {
        for( int i=0; i<S.length; i++ ) {
            if( ( S[ i ] = -S[ i ] ) == 1 ) {
                return true;    
            }
        }

        return false;
    }

    public static boolean check( int[] F, int[] S, int j ) {
      int sum = 0;

      for( int i=0; i<n; i++ ) {
          sum += F[ i ] * S[ j + i ];
      }

      return sum == 0;
    }

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

Program ini berjalan sekitar 3,6 detik:

time java Bench   
[6330034, 2524369, 1040723, 439261, 193673, 87338, 40840, 19567]
java Bench  3.64s user 0.01s system 101% cpu 3.600 total

Yaitu sekitar 14 kali lebih cepat dari solusi PyPy. (Memilih fungsi acak standar daripada fungsi fastRandom mengarah ke waktu eksekusi 5 detik)

dinfuehr
sumber
2

Python 3,5 + numpy 1,10.1, 3,76 detik

Tes dijalankan di Macbook Pro saya. Kode OP memakan waktu ~ 6 menit pada mesin yang sama.

Alasan saya menjawab pertanyaan ini sebenarnya adalah karena saya tidak memiliki 10 reputasi dan tidak dapat menjawab Bagian I :-p

Selama beberapa hari terakhir, saya telah mencoba mencari tahu bagaimana melakukan konvolusi besar secara efisien dengan numpy (tanpa mengandalkan paket pihak ketiga, bahkan scipy). Ketika saya menemukan serangkaian tantangan selama penelitian saya, saya memutuskan untuk mencobanya. Saya mungkin terlambat datang ke game ini, tetapi ini adalah usaha saya menggunakan Python 3.5 dan numpy 1.10.1.

def test_convolv():
    n = 8 
    m  = 8 
    iters = 1000
    ilow = np.ceil(0+n/2).astype(int)
    ihigh = np.ceil(m+n/2).astype(int)

    leadingzerocounts = np.zeros(m)

    # Pre-compute S & F
    S = np.array(list(itertools.product([-1,1], repeat = n+m-1)))
    choicesF = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*iters).reshape(iters,n)
    imask = ~np.any(choicesF, axis=1)
    while np.any(imask):
        imasksize = np.count_nonzero(imask)
        choicesF[imask,:] = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*imasksize).reshape(imasksize, n)
        imask = ~np.any(choicesF, axis=1)

    for i in np.arange(iters):
        F = choicesF[i, :]
        # This is where the magic is: by flattening the S array, 
        # I try to take advantage of speed of the np.convolve 
        # (really numpy.multiarray.correlate). 
        FS = (np.convolve(S.reshape(-1), F, 'same').reshape(S.shape))[:, ilow:ihigh]
        jmask_not = (FS[:, 0] != 0)
        leadingzerocounts[0] = leadingzerocounts[0]+np.count_nonzero(~jmask_not)
        for j in np.arange(n-1)+1:
            jmask = (FS[jmask_not, j] != 0)
            leadingzerocounts[j] = leadingzerocounts[j] + np.count_nonzero(~jmask)
            jmask_not[(jmask_not.nonzero()[0])[jmask]] = False

    print(leadingzerocounts)

Saya pra-komputasi array S dan F, dan meratakan array S sambil melakukan konvolusi, yang (berdasarkan percobaan saya) dapat mengambil keuntungan dari kecepatan np.convolve. Dengan kata lain, karena saya tidak menemukan rutin konvolusi vectorized, saya memalsukan vektorisasi kode dengan meratakan seluruh array dan berharap np.convolved akan melakukan vektorisasi di bawah tenda untuk saya, yang sepertinya berfungsi. Catatan saya menggunakan mode = 'sama' dan memangkas elemen memimpin dan mengekor yang tidak berguna.

Di Macbook Pro saya, hasil tes memberikan 3,76 detik . Ketika saya menjalankan kode OP (dimodifikasi ke Python 3.5), saya mendapat sekitar 6 menit . Percepatan sekitar 100 kali.

Salah satu kelemahannya adalah karena array S dan F disimpan, kebutuhan memori dapat menjadi masalah jika ukurannya terlalu besar.

Saya menggunakan metode yang sama untuk Bagian I dan saya mendapat speedup ~ 60-100x di laptop saya.

Ketika saya melakukan semua yang ada di Macbook Pro saya, jika seseorang dapat menguji kode saya dan memberi tahu saya cara kerjanya di komputer Anda, saya akan sangat menghargainya!

Mencoba. Terlalu keras
sumber
1

J, 130x ~ 50x speedup?

n =: m =: 8
len =: 1000
S =: (] - 0 = ])S0=: #:i.2^<:+/n,m
k =: (n#0) -.~ (_1 0 0 1) {~ (n#4) #: i.4^n
sn =: (]-0=])#:i.2^n
ku =: ~. k
M =: 0=+/"1 sn *"1/ ku
fs =: (ku&i.)"1 k
snum =: n #.\"1 S0

run =: 3 : 0
 r =: n#0
 for_t. (snum) do.
   rn =: fs{~? len # #k
   r =: r + +/"1*/\rn{"1 t{M
 end.
 r
)
echo run 0
exit''

Waktu pada debian acak:

u#>time j slowpy.ijs
6334123 2526955 1041600 440039 193567 87321 40754 19714

real    0m2.453s
user    0m2.368s
sys     0m0.084s


u#>time python slow_pyth.py
[6331017, 2524166, 1041731, 438731, 193599, 87578, 40919, 19705]

real    5m25.541s
user    5m25.548s
sys     0m0.012s

Saya pikir ada ruang untuk perbaikan.

Eelvex
sumber
Skrip Python seharusnya dieksekusi menggunakan pypy, bukan python, itulah sebabnya skrip Anda tampaknya memberikan kecepatan 130x.
ace_HongKongIndependence
@ Ya saya perhatikan tapi saya tidak bisa menginstal pypy: - / Saya pikir urutan besarnya akan tetap.
Eelvex
Belum tentu ... i.imgur.com/n566hzw.png
ace_HongKongIndependence
Memang belum tentu.
Eelvex
Masalah apa yang Anda miliki menginstal pypy?
1

C ++: x200 (4-core i7, harus diubah ke x400 pada 8-core)

Mencoba untuk solusi C ++ 11 yang lebih mudah (Diuji dengan VS 2012, gcc dan dentang) dengan paralelisasi.

Untuk mendapatkan ini untuk dikompilasi dan dijalankan di Linux dengan gcc 4.8.1:

g ++ -O3 -msse -msse2 -msse3 -march = asli -std = c ++ 11 -pthread -Wl, - golf.cpp tidak diperlukan

Di Linux kita juga perlu std::launch::asyncmemaksa banyak utas. Saya melewatkan itu di versi sebelumnya.

Di Visual Studio (2012+) ini seharusnya hanya berfungsi tetapi buat rilis untuk waktu ...

Pada dual core i3 lama saya ini berjalan dalam ~ 0,9 detik. Pada quad core i7 saya ini adalah 0,319 vs pypy 66 detik.

Pada 8-core i7 ini harus dalam kisaran speedup x400. Beralih ke array gaya C akan mempercepatnya tetapi saya tertarik untuk tetap menggunakan wadah C ++. Bagi saya itu menarik untuk melihat speedup yang bisa Anda dapatkan sambil tetap relatif dekat dengan domain masalah dan pada tingkat yang relatif tinggi, sesuatu yang saya pikir C ++ sangat bagus. Yang juga perlu diperhatikan adalah relatif mudahnya paralleization menggunakan konstruksi C ++ 11.

Solusi bit @ ilmale sangat keren dan bekerja untuk -1/1/0. Satu juga bisa melempar SSE ini dan mungkin mendapatkan speedup yang signifikan.

Di luar paralelisasi ada "trik" lain di sana yang mengurangi jumlah penjumlahan. Contoh hasil: 6332947 2525357 1041957 438353 193024 87331 40902 19649

#include <vector>
#include <iostream>
#include <thread>
#include <future>
#include <time.h>
#include <ctime>
#include <algorithm>

using namespace std;

// Bring some of these constants out to share
const size_t m = 8;
const int nthreads = 16;
const size_t cn = 15;
const int two_to_cn = 32768;

static unsigned int seed = 35;

int my_random() // not thread safe but let's call that more random!
{
   seed = seed*1664525UL + 1013904223UL; // numberical recipes, 32 bit
   return ((seed>>30)&1)-!!((seed>>30)&2); // Credit to Dave!
}

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

// Return the position of the first non-zero element
size_t convolve_until_nonzero(size_t max_n, const vector<int>& v1, const vector<int>& v2)
{
   for(size_t i = 0; i<max_n; ++i)
   {
      int result = 0;
      for(size_t j = 0; j<v2.size(); ++j)
      {
         result += v1[i+j]*v2[j];
      }
      if(result!=0)
      {
         return i;
      }
   }
   return max_n;
}

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

vector<int> convolve_random_arrays(vector<int> S, int range)
{
   const int iters = 1000;
   int bothzero = 0;
   int firstzero = 0;

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


   vector<int> F(m);
   vector<int> leadingzerocounts(m+1);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   for(int i=0; i<range; ++i)
   {
      for(int j=0; j<iters; ++j)
      {
         do
         {
            for(auto &x : F)
            {
               x = my_random();
            }
         } while(allzero(F));
         leadingzerocounts[convolve_until_nonzero(m, S, F)]++;
      }
      advance(S);
   }

   // Finish adding things up...
   for(int i=m-1; i>0; --i)
   {
      leadingzerocounts[i] += leadingzerocounts[i+1];
   }

   vector<int> withoutfirst(leadingzerocounts.begin()+1, leadingzerocounts.end());
   return withoutfirst;
}

int main(int argc, char* argv[])
{

   vector<int> leadingzerocounts(m);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   clock_t start = clock();

   vector<int> S(cn);
   for(auto &x : S)
   {
      x = -1;
   }

   vector< future< vector< int > > > fs; // The future results of the threads

   // Go make threads to work on parts of the problem
   for(int i=0; i<nthreads; ++i)
   {
      vector<int> S_reversed = S; // S counts using LSBs but we want the thread start to be in MSBs
      reverse(S_reversed.begin(), S_reversed.end());
      fs.push_back(async(std::launch::async, convolve_random_arrays, S_reversed, two_to_cn/nthreads));
      advance(S);
   }
   // And now collect the data
   for(auto &f : fs)
   {
      vector<int> result = f.get();
      for(int i=0; i<result.size(); ++i)
      {
         leadingzerocounts[i] += result[i];
      }
   }

   for(auto count : leadingzerocounts)
   {
      cout << count << endl;
   }

   return 0;
}
Guy Sirton
sumber
1

Fortran: 316x

Oke, Fortran: Saya sudah mempercepatnya hingga 106x 155x 160x 316x saat menggunakan Xorshift RNG dan OpenMP pada CPU 4 core i7. Selain itu, tidak ada trik besar. Untuk iterator untuk membangun S, saya hanya menggunakan representasi biner dari integer 16-bit i. Anda akan perhatikan bahwa selain dari inline RNG dan "iterator" / pemetaan dari i ke S, kodenya sama tingginya dengan kode Python.

Sunting: menghapus "jika" di Xorshift, sekarang menggunakan "r = abs (w / ...)" alih-alih "r = w / ...". Mulai dari 106x hingga 155x.

Sunting2: Ini menghasilkan 15x angka acak sebanyak solusi C ++. Jika seseorang memiliki solusi nol-overhead untuk mengubah int acak menjadi array 0s dan 1s di Fortran, saya dengar. Maka kita bisa mengalahkan C ++ :)

Sunting3: Suntingan pertama memperkenalkan bug, seperti yang ditunjukkan Lembik. Ini sudah diperbaiki sekarang, dengan sedikit peningkatan pada speedup. Saya akan mencoba menggunakan saran oleh Eelvex untuk mendapatkan lebih banyak speedup.

Sunting4: Pembuatan profil menunjukkan bahwa mengonversi ke nyata dan kembali ke integer dengan nint () lambat. Saya mengganti ini dengan satu divisi integer melakukan penskalaan dan pembulatan, pergi dari 160x ke 316x speedup.

Kompilasi dengan:

gfortran -O3 -march = asli -fopenmp golf.f90

program golf
implicit none
integer, parameter :: m=8, n=8
integer :: F(n), S(m+n-1), leadingzerocounts(m)
integer :: j,k,bindec,enc,tmp,x=123456789,y=362436069,z=521288629,w=88675123
integer*2 :: i
real :: r

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k,tmp,x,y,z,w,r) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,32766
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=16,2,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j-1)=1
      enc=enc-bindec
    else
      S(j-1)=-1
    endif
  end do
  do j=1,1000
    F=0
    do while (.not. any(F /= 0))
      do k=1,n
        ! Start Xorshift RNG
        tmp = ieor(x,ishft(x,11))
        x = y
        y = z
        z = w
        w = ieor(ieor(w,ishft(w,-19)),ieor(tmp,ishft(tmp,-8)))
        ! End Xorshift RNG
        ! Just scale it inside the nint:
        !F(k)=nint(w/2147483648.0)
        ! Scaling by integer division is faster, but then we need the random 
        ! number to be in (-2,2) instead of [-1,1]:
        F(k)=w/1073741824

      end do
    end do
    do k=1,m
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end

Contoh output:

$ waktu ./a.out
6329624 2524831 1039787 438809 193044 6860
40486 19517./a.out pengguna 1,45 sistem 0,6 746% cpu 0,192 total

Kode OP:

$ time pypy golf.py
pypy golf.py 60.68s pengguna sistem 0.04s 99% cpu 1: 00.74 total

semi ekstrinsik
sumber
Apa yang saya gunakan di J adalah daftar prebuild dari 4 ^ n angka di basis-4, kemudian dikonversi menjadi triadik dan tidak termasuk 0. RNG baru saja memilih dari daftar ini.
Eelvex
Saya tidak yakin kode Anda benar. Untuk 100.000 iterasi saya mendapatkan 633140285 271390368 118307997 52751245 23725837 10744292 4944464 2388125 tapi saya pikir itu harus lebih dekat ke 633170604 252560981 104156146 43911426 19316309 8713324 4073378 1959440. Ini adalah perbedaan yang konsisten antara berjalan.
1
Ah, terima kasih, @Lembik, edit saya untuk mempercepat (menghapus if-statement) memang bug. Saya telah memperbarui kode saya sehingga seharusnya benar sekarang. Saya akan mencoba memposting versi menggunakan saran oleh Eelvex nanti.
semi-ekstrinsik
Itu juga mempercepatnya sepertinya!
Ya, kurasa sedikit peningkatan. Saya menyadari bahwa saya menambahkan 1,0 dan kemudian mengurangi 1,0 di dalam lingkaran yang ketat.
semi-ekstrinsik