52

ファイルからランダムに 1/100 行を選択したい 10^7 行のファイルがあります。これは私が持っている AWK コードですが、事前にすべてのファイル コンテンツを丸呑みします。私の PC メモリは、そのようなスラープを処理できません。それを行うための他のアプローチはありますか？

awk 'BEGIN{srand()}
!/^$/{ a[c++]=$0}
END {  
  for ( i=1;i<=c ;i++ )  { 
    num=int(rand() * c)
    if ( a[num] ) {
        print a[num]
        delete a[num]
        d++
    }
    if ( d == c/100 ) break
  }
 }' file
4

10 に答える 10

89

それほど多くの行がある場合、正確に1% が必要ですか、それとも統計的な見積もりで十分でしょうか?

その 2 番目のケースでは、各行で 1% でランダム化します...

awk 'BEGIN {srand()} !/^$/ { if (rand() <= .01) print $0}'

ヘッダー行とその後の行のランダムなサンプルが必要な場合は、次を使用します。

awk 'BEGIN {srand()} !/^$/ { if (rand() <= .01 || FNR==1) print $0}'
于 2009-03-28T06:04:56.290 に答える
57

awk を使用しましたが、必要かどうかはわかりません。そうでない場合は、perl を使用して (ファイル全体をメモリにロードせずに) 実行する簡単な方法を次に示します。

cat your_file.txt | perl -n -e 'print if (rand() < .01)'

（コメントからの単純な形式）：

perl -ne 'print if (rand() < .01)' your_file.txt
于 2009-03-28T06:02:08.140 に答える
21

私はこの正確なコードを Gawk で書きました -- 幸運です。入力順序が保持されるため、部分的に長くなります。おそらく実行できるパフォーマンスの向上があります。

このアルゴリズムは、事前に入力サイズを知らなくても正しいです。ここにロゼッタストーンを投稿しました。(不必要な比較を行うため、このバージョンは投稿しませんでした。)

元のスレッド:レビューのために送信されました -- awk でのランダム サンプリング。

# Waterman's Algorithm R for random sampling
# by way of Knuth's The Art of Computer Programming, volume 2

BEGIN {
    if (!n) {
        print "Usage: sample.awk -v n=[size]"
        exit
    }
    t = n
    srand()

}

NR <= n {
    pool[NR] = $0
    places[NR] = NR
    next

}

NR > n {
    t++
    M = int(rand()*t) + 1
    if (M <= n) {
        READ_NEXT_RECORD(M)
    }

}

END {
    if (NR < n) {
        print "sample.awk: Not enough records for sample" \
            > "/dev/stderr"
        exit
    }
    # gawk needs a numeric sort function
    # since it doesn't have one, zero-pad and sort alphabetically
    pad = length(NR)
    for (i in pool) {
        new_index = sprintf("%0" pad "d", i)
        newpool[new_index] = pool[i]
    }
    x = asorti(newpool, ordered)
    for (i = 1; i <= x; i++)
        print newpool[ordered[i]]

}

function READ_NEXT_RECORD(idx) {
    rec = places[idx]
    delete pool[rec]
    pool[NR] = $0
    places[idx] = NR  
}
于 2009-03-28T07:46:07.750 に答える
5

(サイズが不明な) 大きな母集団から N 個の要素を均一にサンプリングする方法の問題は、Reservoir Samplingとして知られています。(アルゴリズムの問​​題が好きなら、ウィキペディアのアルゴリズムを読まずに数分かけて解決してみてください。)

「Reservoir Sampling」を Web 検索すると、多くの実装が見つかります。ここに必要なものを実装する Perl と Python のコードがあり、これについて議論している別のスタック オーバーフロー スレッドがあります。

于 2013-11-22T23:02:44.773 に答える
5

私はawkを知りませんが、あなたが説明した問題のより一般的なバージョンを解決するための優れた手法があり、一般的なケースでは、rand < 0.01 の場合、ファイルの戻り行の for 行よりもはるかに高速ですアプローチなので、上記のようなタスクを何千回、何百万回も実行する場合に役立つ可能性があります。これは貯水池サンプリングとして知られており、このページには、状況に適用できるバージョンのかなり良い説明があります.

于 2012-09-21T18:20:44.597 に答える
3

次の 2 つのパスで実行できます。

  • ファイルを 1 回実行して、行数を数えます。
  • 印刷したい行の行番号をランダムに選択し、並べ替えられたリスト (またはセット) に格納します。
  • ファイルをもう一度実行し、選択した位置にある行を選択します

Python での例:

fn = '/usr/share/dict/words'

from random import randint
from sys import stdout

count = 0
with open(fn) as f:
   for line in f:
      count += 1

selected = set()
while len(selected) < count//100:
   selected.add(randint(0, count-1))

index = 0
with open(fn) as f:
   for line in f:
      if index in selected:
          stdout.write(line)
      index += 1
于 2009-03-28T06:23:19.897 に答える
1

行の 1% をランダムに選択するために最後まで待つ代わりに、"/^$/" で 100 行ごとに実行します。そうすれば、一度に 100 行しか保持できません。

于 2009-03-28T06:03:30.163 に答える
1

メモリの枯渇を避けることが目的で、ファイルが通常のファイルである場合、リザーバー サンプリングを実装する必要はありません。ファイル内の 2 つのパスを実行すると、ファイル内の行数を知ることができますwc -l。

file=/some/file
awk -v percent=0.01 -v n="$(wc -l < "$file")" '
  BEGIN {srand(); p = int(n * percent)}
  rand() * n-- < p {p--; print}' < "$file"
于 2017-06-11T08:06:32.783 に答える