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 回答