7

この質問のフォローアップnとして、ファイル（またはstdin）からランダムに正確に行を取得する必要があります。headこれはまたはに似ていますtailが、真ん中からいくつか欲しい点が異なります。

リンクされた質問の解決策を含むファイルをループする以外にn、1回の実行で正確に行を取得するための最良の方法は何ですか？

参考までに、私はこれを試しました：

#!/usr/bin/perl -w
use strict;
my $ratio = shift;
print $ratio, "\n";
while () {
    print if ((int rand $ratio) == 1); 
}

ここ$ratioで、必要な行の大まかなパーセンテージを示します。たとえば、10行に1行が必要な場合：

random_select 10 a.list

ただし、これでは正確な金額はわかりません。

aaa> foreach i ( 0 1 2 3 4 5 6 7 8 9 )
foreach? random_select 10 a.list | wc -l
foreach? end
4739
4865
4739
4889
4934
4809
4712
4842
4814
4817

私が持っていたもう1つの考えは、入力ファイルを丸呑みしてnから、配列からランダムに選択することでしたが、非常に大きなファイルがある場合は問題になります。

何か案は？

編集：これはこの質問の正確な複製です。

4

7 に答える 7

5

これは、N行ファイルからM行を読み取るための、O（N）時間計算量とO（M）空間計算量を備えた、私が思いついた素晴らしいワンパスアルゴリズムです。

M<=Nと仮定します。

  1. 選択した行Sのセットとします。Sファイルの最初のM行に初期化します。最終結果の順序が重要な場合は、ここでシャッフルしSます。
  2. 次の行を読んでくださいl。これまでに、n = M + 1合計行を読みました。lしたがって、最終行の1つとして選択する確率はですM/n。
  3. l確率で受け入れるM/n; RNGを使用して、受け入れるか拒否するかを決定しlます。
  4. 受け入れられた場合lは、の行の1つをランダムに選択し、Sそれを。に置き換えlます。
  5. ファイルの行がなくなるまで手順2〜4を繰り返し、n新しい行が読み取られるたびに増分します。
  6. S選択した行のセットを返します。
于 2009-05-13T07:33:19.657 に答える
2

これは、必要な行数 N である単一のコマンドライン引数を取ります。最初の N 行は保持されます。その後、次の行を取るかどうかをランダムに決定します。その場合、現在の N のリストのどの行を上書きするかをランダムに決定します。

#!/usr/bin/perl
my $bufsize = shift;
my @list = ();

srand();
while (<>)
{
    push(@list, $_), next if (@list < $bufsize);
    $list[ rand(@list) ] = $_ if (rand($. / $bufsize) < 1);
}
print foreach @list;
于 2009-05-13T07:47:08.027 に答える
1 
@result = ();

$k = 0;
while(<>) {
    $k++;
    if (scalar @result < $n) {
        push @result, $_;
    } else {
        if (rand <= $n/$k) {
            $result[int rand $n] = $_;
        }
    }
}

print for @result;
于 2009-05-13T07:39:17.683 に答える
1

ファイル内の実際の行番号を知る必要はありません。ランダムな場所を探して、次の行を保持するだけです。（現在の行は、ほとんどの場合、部分的な行になります。）

このアプローチは、大きなファイルでは非常に高速であるはずですが、STDINでは機能しません。ちなみに、STDINではファイル全体をメモリにキャッシュするようなものは機能しません。したがって、STDINが必要な場合、大きなファイルを高速/安価に処理する方法がわかりません。

STDINを検出し、キャッシュされたアプローチに切り替えることができます。それ以外の場合は高速です。

＃！perl
厳密に使用します。

私の$file='file.txt';
私の$count= shift || 10;
私の$size= -s $ file;

open（FILE、$ file）|| 死ぬ"$fileを開けません\n";

while（$ count--）{
   seek（FILE、int（rand（$ size））、0）;
   $ _ = readline（FILE）; ＃部分行を無視する
   定義されていない限りやり直します（$ _ = readline（FILE））; ＃EOFをキャッチ
   $_を印刷します。
}
于 2009-05-14T05:40:42.013 に答える
1

考えられる解決策:

  1. 1 回スキャンして行数をカウントする
  2. ランダムに選ぶ行番号を決める
  3. もう一度スキャンして、ラインを選択します
于 2009-05-13T07:15:35.880 に答える
0

擬似コード:

use List::Util qw[shuffle];

# read and shuffle the whole file
@list = shuffle(<>);

# take the first 'n' from the list
splice(@list, ...);

これは最も単純な実装ですが、最初にファイル全体を読み取る必要があるため、十分なメモリが利用可能である必要があります。

于 2009-05-13T07:21:23.063 に答える