代码之家 › 专栏 › 技术社区 › Kristof Provost

如何在不将文件存储在内存中的情况下从文件中读取n个随机行?

random algorithm

Kristof Provost · 技术社区 · 6 年前

我很熟悉 the algorithm for reading a single random line from a file without reading the whole file into memory . 我想知道这种技术是否可以扩展到n条随机线?

该用例用于密码生成器,它连接从字典文件中提取的n个随机单词,每行一个单词(如 /usr/share/dict/words )你可能会想出 angela.ham.lewis.pathos . 现在它将整个字典文件读取到一个数组中,并从该数组中选择n个随机元素。我想消除数组或其他内存中存储文件的方法,只读取一次文件。

(不,这不是一个实际的优化练习。我对算法感兴趣。)

更新 : 谢谢大家的回答。

答案分为三类:修改全读算法、随机搜索或索引行并随机搜索。

随机搜索要快得多,而且相对于文件大小来说是恒定的,但是根据文件大小而不是字数分布。它还允许重复(这可以避免,但它使算法O(inf))。下面是我使用该算法重新实现的密码生成器。我意识到,通过从搜索点向前阅读,而不是向后阅读,如果搜索落在最后一行,就会出现一个错误。更正操作留给编辑器作为练习。

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my $size = -s $Words;

my @words;
open my $fh, "<", $Words or die $!;

for(1..$Num_Words) {
    seek $fh, int rand $size, 0 or die $!;
    <$fh>;
    my $word = <$fh>;
    chomp $word;
    redo if length $word > $Max_Length;
    push @words, $word;
}
print join ".", @words;

然后是Guffa的答案,这就是我要找的;原始算法的扩展。更慢的是,它必须读取整个文件,但按字分布,允许在不改变算法效率的情况下进行过滤,而且(我认为)没有重复项。

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my @words;
open my $fh, "<", $Words or die $!;
my $count = 0;
while(my $line = <$fh>) {
    chomp $line;
    $count++;
    if( $count <= $Num_Words ) {
        $words[$count-1] = $line;
    }
    elsif( rand($count) <= $Num_Words ) {
        $words[rand($Num_Words)] = $line;
    }
}

print join ".", @words;

最后,索引搜索算法具有按字而不是按文件大小分布的优点。缺点是它读取整个文件,并且内存使用量与文件中的字数成线性关系。也可以使用Guffa的算法。

8 回复 | 直到 10 年前

Guffa 16 年前

在这个例子中,该算法没有以非常好和清晰的方式实现。一些更好地解释它的伪代码是:

cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if random(1 to cnt) = 1 {
      result = line
   }
}

如您所见,其思想是读取文件中的每一行,并计算该行应该是所选行的概率。读第一行后概率为100%,读第二行后概率为50%,以此类推。

通过将数组的大小保留为n而不是单个变量,可以将其扩展为选择n个项,并计算一行替换数组中当前某一行的概率:

var result[1..N]
cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if cnt <= N {
      result[cnt] = line
   } else if random(1 to cnt) <= N {
      result[random(1 to N)] = line
   }
}

编辑:
这是C中实现的代码:

public static List<string> GetRandomLines(string path, int count) {
    List<string> result = new List<string>();
    Random rnd = new Random();
    int cnt = 0;
    string line;
    using (StreamReader reader = new StreamReader(path)) {
        while ((line = reader.ReadLine()) != null) {
            cnt++;
            int pos = rnd.Next(cnt);
            if (cnt <= count) {
                result.Insert(pos, line);
            } else {
                if (pos < count) {
                    result[pos] = line;
                }
            }
        }
    }
    return result;
}

我通过运行100000次方法进行了测试,从20行中选出5行,并计算了这些行的发生次数。结果是:

正如你所看到的,这种分布是你想要的最好的。:)

(我移动了 Random 在运行测试时,对象不在方法中,以避免种子从系统时钟中取出时出现播种问题。)

注:
如果您希望结果数组中的顺序是随机排列的,那么可能需要对它们进行无序排列。由于前n行按顺序排列在数组中,因此如果它们保留在末尾,则不会随机放置。对于ExMaple,如果n大于或等于3,并且拾取了第三行,则它将始终位于阵列中的第三个位置。

编辑2:
我把代码改成了 List<string> 而不是 string[] .这使得以随机顺序插入前n个项目变得容易。我从新的测试运行中更新了测试数据,这样您就可以看到分布仍然良好。

user44511 16 年前

现在,我的Perl不再是以前的样子,而是相信您引用的隐式声明(这样选择的行号分布是一致的),它似乎可以工作:

srand;
(rand($.) < 1 && ($line1 = $_)) || (rand($.) <1 && ($line2 = $_)) while <>;

就像最初的算法一样,这是一次通过和恒定内存。

编辑我刚意识到你需要N,而不是2。如果事先知道n,可以重复或ed表达式n次。

Daniel Brückner 16 年前

我第一次看到Perl代码…这是难以置信的不可读…但这不重要。你为什么不把这条神秘的线重复N次呢?

如果要写这个,我只需要在文件中寻找一个随机位置,读到行的末尾(下一行),然后读到下一行。如果您刚刚看到最后一行,请添加一些错误处理,重复这n次,然后就完成了。我猜

srand;
rand($.) < 1 && ($line = $_) while <>;

是Perl完成这一步的方法。您还可以从初始位置向后读取到priviouse新行或文件开头,然后再向前读取一行。但这并不重要。

更新

我不得不承认,在文件中寻找某个位置不会产生完美的均匀分布,因为行长度不同。当然,如果这种波动很重要,取决于使用场景。

如果您需要一个完美的统一分布,您需要阅读整个文件至少一次,以获得行数。在这种情况下,Guffa给出的算法可能是最聪明的解决方案,因为它需要读取文件一次。

tstirrat 10 年前

如果您不需要在Perl的范围内进行此操作, shuf 是一个非常好的命令行实用程序。做你想做的事:

$ shuf -n N file > newfile

Stefano Borini 16 年前

又快又脏的重击

function randomLine {
  numlines=`wc -l $1| awk {'print $1'}`
  t=`date +%s`
  t=`expr $t + $RANDOM`
  a=`expr $t % $numlines + 1`
  RETURN=`head -n $a $1|tail -n 1`
  return 0
}

randomLine test.sh
echo $RETURN

Will Hartung 16 年前

在文件中选择一个随机点,向后查找以前的EOL,向前搜索当前的EOL,然后返回该行。

FILE * file = fopen("words.txt");
int fs = filesize("words.txt");
int ptr = rand(fs); // 0 to fs-1
int start = min(ptr - MAX_LINE_LENGTH, 0);
int end = min(ptr + MAX_LINE_LENGTH, fs - 1);
int bufsize = end - start;

fseek(file, start);
char *buf = malloc(bufsize);
read(file, buf, bufsize);

char *startp = buf + ptr - start;
char *finp = buf + ptr - start + 1;

while (startp > buf  && *startp != '\n') {
    startp--;
}

while (finp < buf + bufsize && *finp != '\n') {
    finp++;
}

*finp = '\0';
startp++;
return startp;

其中有很多一次性错误和垃圾,糟糕的内存管理和其他恐怖。如果这真的可以编译,你就得到一个镍币。(请寄上自定地址的有邮票的信封和5美元的手续费,以便收到免费的镍币。)

但你应该明白这个想法。

从统计上看,长线比短线更有可能被选中。但不管文件大小如何,它的运行时间实际上是恒定的。如果你有很多长度差不多的词,统计学家就不会高兴了(反正他们也不会高兴),但在实践中,它就足够接近了。

-1

Seb 16 年前

我会说:

读取文件并搜索 \n . 这就是电话线的数目-我们就这么说吧 L
将他们的位置存储在内存中的一个小数组中
得到两条低于 L 获取他们的偏移量,你就完成了。

您只需使用一个小数组,然后读取整个文件一次+2行。

-2

Brian R. Bondy 16 年前

你可以做一个二次通过的算法。首先得到每条新行的位置,将这些位置推到一个向量中。然后选取向量中的随机项,称之为i。

从位置v[i]到v[i+1]的文件中读取您的行。

在第一次传递过程中,您使用一个小的缓冲区读取文件,以免同时将其全部读取到RAM中。