Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re^19: High Performance Game of Life (updated - results)

by eyepopslikeamosquito (Chancellor)
on Aug 16, 2017 at 13:03 UTC ( #1197497=note: print w/replies, xml ) Need Help??


in reply to Re^18: High Performance Game of Life (updated - results)
in thread High Performance Game of Life

I have some news to share. It's possible for tybalt89's excellent optimization to run faster. ... The optimization was made to "Check dead cells".

I don't believe your optimization of tybalt89's original code is correct. At least, it does not pass my more rigorous tgol3.t test program, shown below.

Please test your solutions for correctness against this more thorough test (in addition to the original simple tgol.t blinker test).

# tgol3.t - Simple lidka test of Conway Game of Life Organism class use strict; use warnings; use Organism; use Test::More; my $nticks = 100; my $ntests = 3 + ( $nticks + 1) * 2; plan tests => $ntests; sub test_one { my $org = shift; # Organism handle my $desc = shift; # Test description my $nexpected = shift; # Expected cell count # my $expected = shift; # Array ref of (sorted) expected cells my @cells = $org->get_live_cells(); my $ncells = $org->count(); cmp_ok( $ncells, '==', $nexpected, "$desc cell count ($ncells)" ); cmp_ok( scalar(@cells), '==', $nexpected, "$desc cell array count" +); # is_deeply( \@cells, $expected, "$desc cell array" ); } # Test first 100 ticks from famous lidka methuselah # See: http://conwaylife.com/wiki/Lidka my @lidka_ticks = ( 13, # [ 0] initial count 15, # [ 1] 15, # [ 2] 19, # [ 3] 19, # [ 4] 23, # [ 5] 23, # [ 6] 32, # [ 7] 29, # [ 8] 47, # [ 9] 27, # [10] 32, # [11] 36, # [12] 42, # [13] 48, # [14] 48, # [15] 46, # [16] 60, # [17] 54, # [18] 56, # [19] 64, # [20] 86, # [21] 64, # [22] 74, # [23] 70, # [24] 68, # [25] 52, # [26] 58, # [27] 50, # [28] 44, # [29] 50, # [30] 54, # [31] 80, # [32] 50, # [33] 54, # [34] 56, # [35] 54, # [36] 62, # [37] 50, # [38] 58, # [39] 56, # [40] 70, # [41] 60, # [42] 48, # [43] 52, # [44] 56, # [45] 72, # [46] 70, # [47] 68, # [48] 78, # [49] 86, # [50] 82, # [51] 93, # [52] 98, # [53] 94, # [54] 110, # [55] 87, # [56] 95, # [57] 79, # [58] 88, # [59] 80, # [60] 69, # [61] 76, # [62] 91, # [63] 89, # [64] 93, # [65] 112, # [66] 108, # [67] 140, # [68] 129, # [69] 157, # [70] 138, # [71] 147, # [72] 129, # [73] 111, # [74] 101, # [75] 105, # [76] 98, # [77] 117, # [78] 106, # [79] 114, # [80] 131, # [81] 124, # [82] 132, # [83] 118, # [84] 128, # [85] 133, # [86] 128, # [87] 140, # [88] 129, # [89] 126, # [90] 140, # [91] 147, # [92] 168, # [93] 163, # [94] 174, # [95] 164, # [96] 170, # [97] 152, # [98] 150, # [99] 144, # [100] ); # Lidka cells after 100 ticks my @lidka100 = ( [ -29, 2 ], # 1-10 [ -28, 1 ], [ -28, 2 ], [ -28, 3 ], [ -27, 0 ], [ -27, 4 ], [ -26, 0 ], [ -26, 1 ], [ -26, 4 ], [ -26, 5 ], [ -25, 3 ], # 10-20 [ -25, 4 ], [ -24, 2 ], [ -24, 3 ], [ -23, 1 ], [ -23, 2 ], [ -22, 0 ], [ -21, 0 ], [ -21, 1 ], [ -17, -2 ], [ -17, -1 ], # 20-30 [ -16, -2 ], [ -16, -1 ], [ -12, 8 ], [ -11, 9 ], [ -11, 10 ], [ -11, 16 ], [ -11, 17 ], [ -10, 8 ], [ -10, 9 ], [ -10, 10 ], # 30-40 [ -10, 15 ], [ -10, 16 ], [ -10, 18 ], [ -10, 19 ], [ -9, 18 ], [ -9, 19 ], [ -8, 13 ], [ -8, 18 ], [ -8, 19 ], [ -7, 12 ], # 40-50 [ -6, -19 ], [ -6, -18 ], [ -6, 16 ], [ -6, 17 ], [ -5, -19 ], [ -5, -17 ], [ -5, 12 ], [ -5, 16 ], [ -5, 17 ], [ -4, -19 ], # 50-60 [ -4, 13 ], [ -4, 14 ], [ -4, 15 ], [ -4, 16 ], [ -4, 18 ], [ -3, 14 ], [ -3, 15 ], [ -3, 18 ], [ -2, 17 ], [ -2, 18 ], # 60-70 [ -1, -13 ], [ -1, 6 ], [ 0, -14 ], [ 0, -13 ], [ 0, -12 ], [ 0, 5 ], [ 0, 6 ], [ 0, 7 ], [ 1, -15 ], [ 1, -14 ], # 70-80 [ 1, -12 ], [ 1, 6 ], [ 1, 9 ], [ 1, 10 ], [ 2, -22 ], [ 2, -15 ], [ 2, 3 ], [ 2, 6 ], [ 3, -22 ], [ 3, -16 ], # 80-90 [ 3, 2 ], [ 3, 3 ], [ 3, 4 ], [ 3, 5 ], [ 3, 9 ], [ 4, -22 ], [ 4, -17 ], [ 4, -16 ], [ 4, -15 ], [ 4, -12 ], # 90-100 [ 4, -11 ], [ 4, 3 ], [ 4, 8 ], [ 5, -16 ], [ 5, -14 ], [ 5, -12 ], [ 5, 7 ], [ 6, -16 ], [ 6, -15 ], [ 6, -14 ], # 100-110 [ 6, 4 ], [ 6, 6 ], [ 7, -15 ], [ 7, -14 ], [ 7, 4 ], [ 7, 12 ], [ 7, 13 ], [ 8, -14 ], [ 8, 12 ], [ 8, 13 ], # 110-120 [ 9, -14 ], [ 9, -13 ], [ 9, -4 ], [ 9, -2 ], [ 9, 10 ], [ 9, 11 ], [ 10, -5 ], [ 10, -1 ], [ 10, 10 ], [ 10, 11 ], # 120-130 [ 11, -1 ], [ 11, 0 ], [ 12, -7 ], [ 12, -1 ], [ 12, 0 ], [ 13, -8 ], [ 13, -7 ], [ 13, -3 ], [ 13, -2 ], [ 13, -1 ], # 130-140 [ 14, -8 ], [ 14, -3 ], [ 14, -2 ], [ 14, 1 ], [ 15, -7 ], [ 15, -6 ], [ 15, -5 ], [ 15, -1 ], [ 15, 0 ], [ 15, 1 ], # 140-144 [ 16, -7 ], [ 16, -6 ], [ 16, -5 ], ); my @slidka100 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @l +idka100; # Lidka starting pattern my @lidka0 = ( [ -3, -7 ], [ -4, -6 ], [ -2, -6 ], [ -3, -5 ], [ 4, 3 ], [ 2, 4 ], [ 4, 4 ], [ 1, 5 ], [ 2, 5 ], [ 4, 5 ], [ 0, 7 ], [ 1, 7 ], [ 2, 7 ], ); my @slidka0 = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @lid +ka0; # Initial cell array my $org = Organism->new(); $org->insert_cells(@lidka0); { my @cells = $org->get_live_cells(); is_deeply( \@cells, \@slidka0, "lidka initial cell array" ); test_one( $org, "lidka 0", $lidka_ticks[0] ); } # Test first 100 ticks for my $i ( 1 .. $nticks ) { $org->tick(); test_one( $org, "lidka $i", $lidka_ticks[$i] ); } # Final cell array { my @cells = $org->get_live_cells(); cmp_ok( scalar(@cells), '==', $lidka_ticks[100], "lidka final array + count" ); is_deeply( \@cells, \@slidka100, "lidka final cell array" ); }

Replies are listed 'Best First'.
Re^20: High Performance Game of Life (updated - results)
by marioroy (Priest) on Aug 16, 2017 at 13:33 UTC

    Thank you, eyepopslikeamosquito. I reverted the failing optimization.

    To be sure, I ran the improved test script against the following. All passing, including the two involving bit manipulations.

    $ perl createblinker.pl 500000 -900000 100 >x.tmp 2>y.tmp $ perl tbench1.pl x.tmp 2 mem size v5.26.0 v5.24.2 v5.22.4 cperl infinite 7,548 MB 122 secs 119 secs 133 secs 116 secs original 704 MB 167 secs 168 secs 180 secs 163 secs improvements 744 MB 57 secs 57 secs 63 secs 54 secs optimized i2 1,543 MB 38 secs 39 secs 40 secs 36 secs 2 nums into 1 1,510 MB 39 secs 40 secs 42 secs 37 secs shorter impl 1,661 MB 40 secs 42 secs 44 secs 37 secs

    It's been an interesting ride and learned a lot of things about Perl.

    Regards, Mario

Re^20: High Performance Game of Life (updated - results)
by tybalt89 (Curate) on Aug 16, 2017 at 13:52 UTC

    On first glance, that seems to allow new cells to be generated when 3 or more neighbors are alive, instead of exactly 3.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1197497]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (3)
As of 2017-12-18 04:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (466 votes). Check out past polls.

    Notices?