algorithm - How Break The Infinite Loop in Perl Under Redo(生成随机数)

Question

我打算通过以下步骤生成随机数:

1. 从文件中读取数据(<DATA>)
2. 生成与输入数据行一样多的随机数
3. 随机数应该不生成两次，例如如果在循环 no x 中生成的兰数已经创建 在此之前，重新创建随机数。

这是导致无限循环的代码。我的逻辑有什么问题，我该如何解决？

#!/usr/bin/perl -w
use strict;
my %chrsize = ('chr1' =>249250621);

# For example case I have created the
# repository where a value has been inserted.
my %done =("chr1    182881372" => 1);

while ( <DATA> ) {
 chomp;
 next if (/^\#/);

 my ($chr,$pos) = split(/\s+/,$_);
 # this number has been generated before
 # with this: int(rand($chrsize{$chr}));
 # hence have to create other than this one
 my $newst =182881372;

 my $newpos = $chr ."\t".$newst;


 # recreate random number
 for (0...10){
     if ( $done{$newpos} ) {

            # INFINITE LOOP
            $newst = int(rand($chrsize{$chr}));
            redo;
     }
 }

 $done{$newpos}=1;
print "$newpos\n";

}


__DATA__
# In reality there are 20M of such lines
# name  positions
chr1    157705682
chr1    19492676
chr1    169660680
chr1    226586538
chr1    182881372
chr1    11246753
chr1    69961084
chr1    180227256
chr1    141449512

Answer 1

你有几个错误:

1. 您每次都在循环中设置 $newst，因此 $newpos 从未采用新值。
2. 您的内部 for 循环没有意义，因为您在再次检查条件之前从未真正更改过 $newpos。
3. redo; 正在处理内部循环。

这是一个完全避免重做的更正版本。

更新:我稍微编辑了算法以使其更简单。

 #!/usr/bin/perl -w
use strict;
my $chr1size = 249250621;

my %done;
my $newst;

while ( <DATA> ) {
    chomp;
    next if (/^\#/);
    my ($chr,$pos) = split(/\s+/,$_);

    my $newpos;
    #This will always run at least once
    do {
        $newst = int(rand($chr1size));
        $newpos = $chr ."\t".$newst;
    } while ( $done{$newpos} );

    $done{$newpos}=1;
    print "$newpos\n";
}

更新 2:虽然上述算法可以工作，但在 20,000,000 行上它会变得非常慢。这是一种应该更快的替代方法(它生成的随机数有某种模式，但在大多数情况下可能没问题)。

#!/usr/bin/perl -w
use strict;
my $newst;

#make sure you have enough.  This is good if you have < 100,000,000 lines.
use List::Util qw/shuffle/;
my @rand_pieces = shuffle (0..10000);

my $pos1   = 0;
my $offset = 1;
while ( <DATA> ) {
    chomp;
    next if (/^\#/);
    my ($chr,$pos) = split(/\s+/,$_);

    $newst = $rand_pieces[$pos1] * 10000 + $rand_pieces[($pos1+$offset)%10000];
    my $newpos = $chr ."\t".$newst;

    $pos1++;
    if ($pos1 > $#rand_pieces) 
    {
        $pos1 = 0;
        $offset = ++$offset % 10000;
        if ($offset == 1) { die "Out of random numbers!"; } 
    }

    print "$newpos\n";
}