我的问题
我很惊讶在这里没有找到类似的问题。也许我需要学习如何更好地搜索。主要是,我试图弄清楚我的算法的哪个部分很慢,以及是否有替代的、更快的方法来实现我的目标。
我正在尝试生成一个包含 1 亿对随机字母字符串的文件。这些随机字符串可以包含空格。随机的周围有一些真实的、固定的单词。我想要的输出的一个例子是
rrn TRY gy q OFTEN
ibh TRY mpdw OFTEN
bnq TRY nbjw OFTEN
tky TRY tedr OFTEN
c r TRY fdv OFTEN
cvs TRY dusr OFTEN
ppd TRY qhrc OFTEN
...
我希望能够用Linux脚本语言(我实际上正在使用Cygwin(来做到这一点,所以最好是bash
、python
、perl
等答案。但是,如果我要使用C++
、Java
或其他东西大幅提高速度,我对此持开放态度。
目前,我的脚本通过以下方式运行
$ ./create_big_file.sh 100000000
bash
脚本如下。我已经改变了一些东西,以免硬编码对的数量。
我的可执行代码
#!/bin/bash
#
# @file create_big_file.sh
n_lines=$1
filename="big_file_${n_lines}.out"
n_lett_rand_str1=3 # originally had 5, tried 3 for speed
n_lett_rand_str2=4 # originally had 10, tried 4 for speed
between=" TRY "
after=" OFTEN"
while [ $n -lt $n_lines ]; do
n_lett_rand_str1=3
n_lett_rand_str2=4
random_str1=$(cat /dev/urandom | tr -dc 'a-z ' |
fold -w $n_lett_rand_str1 | head -n 1)
random_str2=$(cat /dev/urandom | tr -dc 'a-z ' |
fold -w $n_lett_rand_str2 | head -n 1)
echo "${random_str1}${between}${random_str2}${after}" >> "$filename"
n=$(($n+1))
done #endof: while [ $n -lt $n_lines ]
正如预期的那样,我的运行范围大致呈线性缩放,但每次迭代所花费的时间对我来说似乎很高。如果我对纯线性时间进行估计,我计算出这将需要 265.0 天。如果我使用完整的t=a*exp[x,b]
拟合,我计算出 1.016 年。如果我只想要一百万行,大约需要 2-3 天。
问题
我想一定有一种方法可以做我想做的事情,但速度更快。有谁知道在更短的时间内创建这样一个文件的方法?如果我能在不到 4 小时内获得 100 万行,我愿意满足于它,但我希望能够在不到一天的时间内获得 1 亿行。
附言这不是家庭作业;我正在做一些文本分析。
我的研究
$ time ./create_big_file.sh 10
real 0m2.487s
user 0m1.115s
sys 0m1.950s
$ time ./create_big_file.sh 100
real 0m22.356s
user 0m11.764s
sys 0m16.517s
$ tail -2 big_file_100.out
mri TRY nzeo OFTEN
hev TRY uqdf OFTEN
$ time ./create_big_file.sh 500
real 1m52.143s
user 0m57.347s
sys 1m19.405s
$ time ./create_big_file.sh 1000
real 3m50.129s
user 1m58.697s
sys 2m45.612s
时间与行数的拟合度,如在 Wolfram|阿尔法,是
t(x( = 0.11905 x1.02845
我尝试更换
random_str1=$(cat /dev/urandom | tr -dc 'a-z ' |
fold -w $n_lett_rand_str1 | head -n 1)
跟
random_str1=$(echo $RANDOM | tr '[0-9]' '[a-z ]')
并对random_str2
进行了相同的更改。这给了我两串最多 5 个字母的字符串。但是,我在运行时没有显着差异。
比较
我在没有任何随机生成字符串的情况下运行脚本。我注释掉了与随机内容有关的任何内容,并仅运行了while循环
echo "${between}${after}"
n=$(($n+1))
里面,我的运行时编号是(格式:{n_lines, n_seconds}
(
{{10, 0.049},{100, 0.097},{500, 0.157},{1000,0.263}, {10000, 1.996}, {100000, 19.222}}
给出增长顺序作为(来源(
t(x( = 0.000243745 x0.979367
这让我非常确定随机的东西导致了问题 - 比如每个随机问题 0.2 秒。
编辑"随机"不一定是极其随机的。我基本上希望它不会重复 10-20 行(很少除外(。同样,它用于文本处理。感谢@zdim要求澄清。
这可能在六个月内只运行一两次。
你可以在Perl中做到这一点,它将在几秒钟内运行1亿行。
use strict;
use warnings;
use feature 'say';
# read command line arguments
my ( $first_length, $second_length, $lines, $first_word, $second_word ) = @ARGV;
$first_word //= 'TRY';
$second_word //= 'OFTEN';
# define your alphabet of random characters
my @alphabet = ( 'a' .. 'z', q{ } );
my $max_rand = scalar @alphabet;
foreach my $i ( 1 .. $lines ) {
say join(
q{ },
( join q{}, map { $alphabet[ int rand $max_rand ] } 1 .. $first_length ),
$first_word,
( join q{}, map { $alphabet[ int rand $max_rand ] } 1 .. $second_length ),
$second_word,
);
}
该程序需要三个或五个参数:
$ perl foo.pl 3 4 100000000 TRY OFTEN
在我的机器上,生成完整的 100M 线大约需要三秒钟。输出如下所示:
wab TRY mcqb OFTEN
tdb TRY tobw OFTEN
rlf TRY lg v OFTEN
ofn TRY oxdf OFTEN
o j TRY vcfp OFTEN
ffv TRY doud OFTEN
lvl TRY ckci OFTEN
xqh TRY wnaa OFTEN
fhj TRY pmp OFTEN
oxe TRY swyi OFTEN