C:\test>826456 -N=4000
4000: Took 1.367 seconds

C:\test>826456-a -N=400
400: Took 0.025 seconds

C:\test>826456-a -N=800
800: Took 0.988 seconds

C:\test>826456-a -N=1600
1600: Took 13.999 seconds

C:\test>826456-a -N=3200
3200: Took 119.228 seconds

C:\test>826456-a -N=4000
4000: Took 234.037 seconds

##</code><code>##

C:\test>perl -V
Summary of my perl5 (revision 5 version 10 subversion 1) configuration:

  Platform:
    osname=MSWin32, osvers=5.2, archname=MSWin32-x64-multi-thread
    uname=''
    config_args='undef'
    hint=recommended, useposix=true, d_sigaction=undef
    useithreads=define, usemultiplicity=define
    useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
    use64bitint=define, use64bitall=undef, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cl', ccflags ='-nologo -GF -W3 -MD -Zi -DNDEBUG -Ox -GL -Wp64 -fp:precise -DWIN32 -D_CON
    optimize='-MD -Zi -DNDEBUG -Ox -GL -Wp64 -fp:precise',
    cppflags='-DWIN32'
    ccversion='15.0.21022', gccversion='', gccosandvers=''
    intsize=4, longsize=4, ptrsize=8, doublesize=8, byteorder=12345678
    d_longlong=undef, longlongsize=8, d_longdbl=define, longdblsize=8
    ivtype='__int64', ivsize=8, nvtype='double', nvsize=8, Off_t='__int64', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='link', ldflags ='-nologo -nodefaultlib -debug -opt:ref,icf -ltcg  -libpath:"C:\Perl64\li
    libpth=\lib
    libs=  oldnames.lib kernel32.lib user32.lib gdi32.lib winspool.lib  comdlg32.lib advapi32.li
    perllibs=  oldnames.lib kernel32.lib user32.lib gdi32.lib winspool.lib  comdlg32.lib advapi3
    libc=msvcrt.lib, so=dll, useshrplib=true, libperl=perl510.lib
    gnulibc_version=''
  Dynamic Linking:
    dlsrc=dl_win32.xs, dlext=dll, d_dlsymun=undef, ccdlflags=' '
    cccdlflags=' ', lddlflags='-dll -nologo -nodefaultlib -debug -opt:ref,icf -ltcg  -libpath:"C


Characteristics of this binary (from libperl):
  Compile-time options: MULTIPLICITY PERL_DONT_CREATE_GVSV
                        PERL_IMPLICIT_CONTEXT PERL_IMPLICIT_SYS
                        PERL_MALLOC_WRAP PL_OP_SLAB_ALLOC USE_64_BIT_INT
                        USE_ITHREADS USE_LARGE_FILES USE_PERLIO
                        USE_SITECUSTOMIZE
  Locally applied patches:
        ActivePerl Build 1006 [291086]
        32728 64-bit fix for Time::Local
  Built under MSWin32
  Compiled at Aug 24 2009 13:45:20
  @INC:
    C:/Perl64/site/lib
    C:/Perl64/lib
    .

C:\test>perl -Mautobox -E"say $autobox::VERSION"
2.55

C:\test>perl -Mautobox::Core -E"say $autobox::Core::VERSION"
0.6

##</code><code>##

C:\test>type 826456.pl
#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use List::Util qw[ min ];
use Data::Dump qw[ pp ];

srand 1;

our $N //= 4000;

my $start = time();

my %pvalues = map{ $_ => rand() } 1 .. $N;

#my %pvalues = (
#    1=> 0.5453980,
#    2=> 0.4902384,
#    3=> 0.8167950,
#    4=> 0.2821822,
#    5=> 0.4693030,
#    6=> 0.6491767,
#    7=> 0.9802138,
#    8=> 0.1155778,
#    9=> 0.9585124,
#    10=> 0.4069490
#);

my @orderedKeys = sort {
    $pvalues{ $b } <=> $pvalues{ $a }
} keys %pvalues;

my $d = my $n = values %pvalues;

$pvalues{ $_ } *= $n / $d-- for @orderedKeys;

$pvalues{ $orderedKeys[ $_ ] } =
    min( @pvalues{ @orderedKeys[ 0 .. $_ ] } )
    for 1 .. $n-1;

$pvalues{ $_ } = min( $pvalues{ $_ }, 1 ) for keys %pvalues;

printf "$N: Took %.3f seconds\n", time() - $start;

#pp \%pvalues;


C:\test>type 826456-a.pl
#! perl -slw
use strict;
use autobox::Core;

use Time::HiRes qw[ time ];
use List::Util qw[ min ];
use Data::Dump qw[ pp ];

srand 1;

our $N //= 4000;

my $start = time();

my %pvalues = @{ [ 1 .. $N ]->map( sub{ $_[0] => rand() } ) };

#my %pvalues = (
#    1=> 0.5453980,
#    2=> 0.4902384,
#    3=> 0.8167950,
#    4=> 0.2821822,
#    5=> 0.4693030,
#    6=> 0.6491767,
#    7=> 0.9802138,
#    8=> 0.1155778,
#    9=> 0.9585124,
#    10=> 0.4069490
#);

my @orderedKeys = @{ %pvalues->keys->sort(
        sub{ $pvalues{ $_[1] } <=> $pvalues{ $_[0] } }
    )
};
my $d = my $n = @{ %pvalues->keys };

@orderedKeys->map(
    sub{
        $pvalues{ $_[0] } *= $n / $d--;
    }
);

[ 1 .. $n-1 ]->map(
    sub{
        $pvalues{ $orderedKeys[ $_[0] ] } =
            min( @pvalues{ @orderedKeys[ 0 .. $_[0] ] } );
    }
);

%pvalues->keys->map(
    sub{ $pvalues{ $_[0] } = min( $pvalues{ $_[0] }, 1 ) }
);

printf "$N: Took %.3f seconds\n", time() - $start;

#pp \%pvalues;
__END__

C:\test>826456 -N=4000
4000: Took 1.367 seconds

C:\test>826456-a -N=400
400: Took 0.025 seconds

C:\test>826456-a -N=800
800: Took 0.988 seconds

C:\test>826456-a -N=1600
1600: Took 13.999 seconds

C:\test>826456-a -N=3200
3200: Took 119.228 seconds

C:\test>826456-a -N=4000
4000: Took 234.037 seconds