use strict; use warnings; use feature 'say'; use PDL; use List::Util; BEGIN { *_min = \&List::Util::min; # collision *_max = \&List::Util::max } # with PDL use constant MAX => 1e7; use constant TOP => _min( 20, MAX ); use constant CHUNK => _min( 8e4, MAX ); # but keep it even use constant MAXLEN => MAX * 1; # ?? # x(1..2) use Time::HiRes 'time'; my \$t = time; my \$seqs = sequence( longlong, 1 + MAX ); \$seqs-> setbadat( 0 ); \$seqs-> setbadat( 1 ); \$seqs-> badvalue( 2 ); \$seqs-> slice([ CHUNK + 2, MAX, 2]) .= 2 ## if CHUNK + 2 <= MAX; ## my \$lengths = ones( short, 1 + MAXLEN ); \$lengths-> inplace-> setvaltobad( 1 ); \$lengths-> set( 1, 1 ); \$lengths-> set( 2, 2 ); \$lengths-> set( 4, 3 ); CHUNKS: for ( my \$from = my \$to = 0; \$to != MAX; \$from = \$to + 1 ) { \$to = _min( \$from + CHUNK, MAX ); # "_c" is for "chunk" my \$seqs_c = \$seqs-> slice([ \$from, \$to ]); my \$lengths_c = \$lengths-> slice([ \$from, \$to ]); my \$current = zeroes( short, nelem( \$seqs_c )); ITERATIONS: while ( any \$seqs_c-> isgood ) { my ( \$seqs_c_odd, \$current_odd_masked ) = where( \$seqs_c, \$current, \$seqs_c & 1 ); \$current_odd_masked ++; \$current ++; ( \$seqs_c_odd *= 3 ) ++; \$seqs_c >>= 1; my ( \$seqs_cap, \$lengths_cap, \$current_cap ) = where( \$seqs_c, \$lengths_c, \$current, \$seqs_c <= MAXLEN ); my \$lut = \$lengths-> index( \$seqs_cap ); # "_f" is for "finished" my ( \$seqs_f, \$lengths_f, \$lut_f, \$current_f ) = where( \$seqs_cap, \$lengths_cap, \$lut, \$current_cap, \$lut-> isgood ); \$lengths_f .= \$lut_f + \$current_f; \$seqs_f .= 2; # i.e. BAD } # "_e" is for "at even positions, ahead" ## ## # my \$from_e = _max( \$from * 2, \$to ) + 2; # bug ## my \$from_e = \$from == 0 ? \$to + 2 : \$from * 2; # fixed ## my \$to_e = _min( \$to * 2, MAXLEN ); ## ## ( \$lengths-> slice([ \$from_e, \$to_e, 2 ]) ## .= \$lengths-> slice([ \$from_e / 2, \$to_e / 2 ])) ++ ## if \$from_e <= MAXLEN ## } # same finale \$lengths-> badflag( 0 ); \$lengths = \$lengths-> slice([ 1, MAX ]); my \$sorted_i = \$lengths-> qsorti; my \$sorted = \$lengths-> index( \$sorted_i ); my \$value = \$sorted-> at( MAX - TOP ); my \$pos = vsearch_insert_leftmost( \$value, \$sorted ); my \$top_i = \$sorted_i-> slice([ MAX - 1, \$pos ]); ( my \$result = \$lengths -> index( \$top_i ) -> longlong -> bitnot -> cat( \$top_i + 1 ) -> transpose -> qsortvec -> slice([], [ 0, TOP - 1 ]) )-> slice([ 0 ], []) -> inplace -> bitnot; say \$result; say time - \$t; __END__