52

我有一个 10^7 行的文件,我想从文件中随机选择 1/100 行。这是我拥有的 AWK 代码,但它会预先删除所有文件内容。我的电脑内存无法处理这样的啜饮。还有其他方法吗?

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 % 还是统计估计就足够了?

在第二种情况下,只需在每行随机化 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 回答
16

这应该适用于大多数 GNU/Linux 机器。

$ shuf -n $(( $(wc -l < $file) / 100)) $file

如果 GNU shuf 命令不恰当地完成内存管理,我会感到惊讶。

于 2009-03-29T05:36:11.173 回答
5

我不知道awk,但是有一种很好的技术可以解决您所描述的问题的更一般版本,并且在一般情况下,如果 rand < 0.01,它比文件返回行中的 for 行快得多方法,因此如果您打算多次(数千次,数百万次)执行上述任务,它可能会很有用。它被称为水库采样此页面对适用于您的情况的版本进行了很好的解释。

于 2012-09-21T18:20:44.597 回答
5

如何从大量(未知大小)中均匀采样 N 个元素的问题被称为Reservoir Sampling。(如果您喜欢算法问题,请花几分钟尝试解决它,而无需阅读 Wikipedia 上的算法。)

在网络上搜索“Reservoir Sampling”会发现很多实现。是实现您想要的 Perl 和 Python 代码,是另一个讨论它的 Stack Overflow 线程。

于 2013-11-22T23:02:44.773 回答
4

在这种情况下,获取精确k值的水库采样是微不足道的awk,我很惊讶没有任何解决方案建议这样做。我必须解决同样的问题,我编写了以下awk采样程序:

#!/usr/bin/env awk -f
BEGIN{
    srand();
    if(k=="") k=10
}

NR <= k {
    reservoir[NR-1] = $0;
    next;
}

{ i = int(NR * rand()) }

i < k { reservoir[i] = $0 }

END {
    for (i in reservoir) {
        print reservoir[i];
    }
}

如果保存为sample_lines可执行文件,它可以像这样运行:./sample_lines -v k=5 input_file. 如果k未给出,则默认使用 10。

然后弄清楚k是什么必须单独完成,例如通过设置-v "k=$(dc -e "$(cat input_file | wc -l) 100 / n")"

于 2018-02-19T15:52:00.353 回答
3

您可以分两次完成:

  • 遍历文件一次,只是为了计算有多少行
  • 随机选择要打印的行的行号,将它们存储在排序列表(或集合)中
  • 再次运行文件并选择选定位置的行

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

如果目的只是避免内存耗尽,并且文件是常规文件,则无需执行存储库采样。如果您在文件中执行两次传递,则可以知道文件中的行数,一次获取行数(如 with 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 回答