use strict;
use warnings;
use feature 'say';
use PDL;
use Time::HiRes 'time';
my $t = time;
use constant MAX => 1e6;
use constant TOP => MAX < 20 ? MAX : 20;
my $seqs = 1 + sequence( longlong, MAX );
my $lengths = ones( short, MAX );
while ( any my $good_mask = $seqs-> inplace
-> setvaltobad( 1 )
-> isgood ) {
my $odd_mask = $seqs & 1;
$lengths-> where( $odd_mask ) ++;
$lengths-> where( $good_mask ) ++;
( $seqs-> where( $odd_mask ) *= 3 ) ++;
$seqs >>= 1;
}
my $top_i = $lengths-> qsorti
-> slice([ MAX - 1, MAX - TOP ]);
say $lengths-> index( $top_i )
-> longlong
-> cat( $top_i + 1 )
-> transpose;
say time - $t;
__END__
[
[ 525 837799]
[ 509 626331]
...
[ 445 938143]
[ 445 906175]
[ 445 922525]
[ 445 922526]
]
7.98023009300232
####
[ BAD BAD 3 4 5 ... ] # initial $seqs
[ 1 2 2 2 2 ... ] # initial $lengths
##
##
use strict;
use warnings;
use feature 'say';
use PDL;
use Time::HiRes 'time';
my $t = time;
use constant MAX => 1e6;
use constant TOP => MAX < 20 ? MAX : 20;
my $seqs = 1 + sequence( longlong, MAX );
$seqs-> setbadat( 0 );
$seqs-> badvalue( 2 );
my $lengths = ones( short, MAX );
$lengths <<= 1;
$lengths-> set( 0, 1 );
while ( any my $good_mask = $seqs-> isgood ) {
my ( $seqs_odd, $lengths_odd_masked )
= where( $seqs, $lengths, $seqs & 1 );
$lengths_odd_masked ++;
$lengths-> where( $good_mask ) ++;
( $seqs_odd *= 3 ) ++;
$seqs >>= 1;
}
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__
[
[ 525 837799]
[ 509 626331]
...
[ 445 886953]
[ 445 906175]
[ 445 922524]
[ 445 922525]
]
6.0809600353241
##
##
[ BAD BAD BAD 3 4 5 6 ... ] # initial $seqs
[ BAD 1 2 BAD 3 BAD BAD ... ] # initial $lengths
##
##
use strict;
use warnings;
use feature 'say';
use PDL;
use Time::HiRes 'time';
my $t = time;
use constant MAX => 1e6;
use constant TOP => MAX < 20 ? MAX : 20;
my $seqs = sequence( longlong, 1 + MAX );
$seqs-> setbadat( 0 );
$seqs-> setbadat( 1 );
$seqs-> badvalue( 2 );
my $lengths = ones( short, 1 + MAX );
$lengths-> inplace-> setvaltobad( 1 );
$lengths-> set( 1, 1 );
$lengths-> set( 2, 2 );
$lengths-> set( 4, 3 );
my $current = zeroes( short, 1 + MAX );
while ( any $seqs-> isgood ) { # sic
my ( $seqs_odd, $current_odd_masked )
= where( $seqs, $current, $seqs & 1 );
$current_odd_masked ++;
$current ++;
( $seqs_odd *= 3 ) ++;
$seqs >>= 1;
my ( $seqs_cap, $lengths_cap, $current_cap )
= where( $seqs, $lengths, $current, $seqs <= MAX );
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
}
$lengths-> badflag( 0 );
my $sorted_i = $lengths-> qsorti;
my $sorted = $lengths-> index( $sorted_i );
my $value = $sorted-> at( MAX + 1 - TOP );
my $pos = vsearch_insert_leftmost( $value, $sorted );
my $top_i = $sorted_i-> slice([ MAX, $pos ]);
( my $result = $lengths
-> index( $top_i )
-> longlong
-> bitnot
-> cat( $top_i )
-> transpose
-> qsortvec
-> slice([], [ 0, TOP - 1 ])
)-> slice([ 0 ], [])
-> inplace
-> bitnot;
say $result;
say time - $t;
__END__
[
[ 525 837799]
[ 509 626331]
...
[ 445 886953]
[ 445 906175]
[ 445 922524]
[ 445 922525]
]
2.88385105133057