Случайно выбрать строки из файла, не обрезая его с Unix - PullRequest
Новая
       35

Случайно выбрать строки из файла, не обрезая его с Unix

51 голосов
/ 28 марта 2009

У меня есть файл 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

Ответы [ 10 ]

86 голосов
/ 28 марта 2009

если у вас столько строк, вы уверены, что хотите точно 1% или статистической оценки будет достаточно?

Во втором случае просто рандомизируйте по 1% в каждой строке ... 

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

Если вам нужна строка заголовка плюс случайная выборка строк после, используйте: 

awk 'BEGIN {srand()} !/^$/ { if (rand() <= .01 || FNR==1) print $0}'
52 голосов
/ 28 марта 2009

Вы использовали awk, но я не знаю, требуется ли это. Если это не так, вот тривиальный способ сделать w / perl (и без загрузки всего файла в память): 

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

(более простая форма, из комментариев): 

perl -ne 'print if (rand() < .01)' your_file.txt
19 голосов
/ 28 марта 2009

Я написал этот точный код на 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  
}
16 голосов
/ 29 марта 2009

Это должно работать практически на любой машине с GNU / Linux. 

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

Я бы удивился, если бы управление памятью было выполнено ненадлежащим образом командой GNU shuf. * ​​1004 *

5 голосов
/ 23 ноября 2013

Проблема получения единообразной выборки N элементов из большой популяции (неизвестного размера) известна как Выборка из резервуара . (Если вам нравятся проблемы с алгоритмами, потратьте несколько минут на их решение, не читая алгоритм в Википедии.)

Поисковый запрос "Выборка резервуара" найдет множество реализаций. Здесь - это код Perl и Python, который реализует то, что вы хотите, а здесь - еще один поток переполнения стека, обсуждающий его.

5 голосов
/ 21 сентября 2012

Я не знаю awk , но есть отличный метод для решения более общей версии описанной вами проблемы, и в общем случае она намного быстрее, чем для строки в обратной строке файла, если подход rand <0.01 </em>, так что это может быть полезно, если вы собираетесь выполнять задачи, подобные описанным выше, много (тысячи, миллионы) раз. Она известна как отбор проб из резервуара и на этой странице есть довольно хорошее объяснение версии, которая применима к вашей ситуации.

3 голосов
/ 28 марта 2009

Вы можете сделать это в два прохода:

  • Запустите файл один раз, просто чтобы посчитать, сколько строк
  • Случайным образом выбирает номера строк, которые вы хотите распечатать, сохраняя их в отсортированном списке (или наборе)
  • Запустите файл еще раз и выберите строки в выбранных позициях

Пример на 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
2 голосов
/ 19 февраля 2018

В этом случае выборка из резервуара для получения точных значений k достаточно тривиальна с awk, поэтому я удивлен, что решение пока не предложено. Мне пришлось решить ту же проблему, и я написал следующую awk программу для выборки: 

NR < k {
    reservoir[NR] = $0;
}
NR >= k {
    i = int(NR * rand());
    if (i < k) {
        reservoir[i] = $0;
    }
}
END {
    for (i in reservoir) {
        print reservoir[i];
    }
}

Затем выяснить, что k , нужно сделать отдельно, например, установив awk -v 'k=int('$(dc -e "$(cat FILE | wc -l) 0.01 * n")')'

1 голос
/ 11 июня 2017

Если целью является просто избежать исчерпания памяти, а файл является обычным файлом, нет необходимости осуществлять выборку из резервуара. Количество строк в файле может быть известно, если вы сделаете два прохода в файле, один для получения количества строк (как при 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"
1 голос
/ 28 марта 2009

Вместо того, чтобы ждать до конца, чтобы случайно выбрать 1% строк, делайте это каждые 100 строк в "/ ^ $ /". Таким образом, одновременно можно удерживать только 100 строк.

...