Получить случайные строки из больших файлов в Bash

Question

Получить случайные строки из больших файлов в Bash

Как я могу получить n случайные строки из очень больших файлов, которые не помещаются в памяти.

Также было бы здорово, если бы я мог добавить фильтры до или после рандомизации.

обновление 1

в моем случае спецификации таковы:

> 100 миллионов строк
> 10 ГБ файлов
обычный случайный размер партии 10000-30000
512RAM хостинг Ubuntu Server 14.10

так что потеря нескольких строк из файла не будет такой большой проблемой, так как в любом случае у них есть шанс 1 на 10000, но производительность и потребление ресурсов будут проблемой

6

bash command-line random-sample line-processing

Источник

user1342199 17 мар '15 в 15:03

5 ответов

Другие вопросы по тегам bash command-line random-sample line-processing

user632407 18 мар '15 в 10:25 2015-03-18 10:25 · Answer 1 · 2015-03-18 10:25

При таких ограничивающих факторах следующий подход будет лучше.

искать случайную позицию в файле (например, вы будете "внутри" в какой-то строке)
вернуться назад из этой позиции и найти начало данной строки
идти вперед и распечатать всю строку

Для этого вам нужен инструмент, который можно искать в файлах, например perl,

use strict;
use warnings;
use Symbol;
use Fcntl qw( :seek O_RDONLY ) ;
my $seekdiff = 256; #e.g. from "rand_position-256" up to rand_positon+256

my($want, $filename) = @ARGV;

my $fd = gensym ;
sysopen($fd, $filename, O_RDONLY ) || die("Can't open $filename: $!");
binmode $fd;
my $endpos = sysseek( $fd, 0, SEEK_END ) or die("Can't seek: $!");

my $buffer;
my $cnt;
while($want > $cnt++) {
    my $randpos = int(rand($endpos));   #random file position
    my $seekpos = $randpos - $seekdiff; #start read here ($seekdiff chars before)
    $seekpos = 0 if( $seekpos < 0 );

    sysseek($fd, $seekpos, SEEK_SET);   #seek to position
    my $in_count = sysread($fd, $buffer, $seekdiff<<1); #read 2*seekdiff characters

    my $rand_in_buff = ($randpos - $seekpos)-1; #the random positon in the buffer

    my $linestart = rindex($buffer, "\n", $rand_in_buff) + 1; #find the begining of the line in the buffer
    my $lineend = index $buffer, "\n", $linestart;            #find the end of line in the buffer
    my $the_line = substr $buffer, $linestart, $lineend < 0 ? 0 : $lineend-$linestart;

    print "$the_line\n";
}

Сохраните вышеупомянутое в некотором файле, таком как "randlines.pl" и используйте это как:

perl randlines.pl wanted_count_of_lines file_name

например

perl randlines.pl 10000 ./BIGFILE

Скрипт выполняет операции ввода-вывода очень низкого уровня, т.е. он ОЧЕНЬ БЫСТРО. (на моем ноутбуке выбор 30 тыс. строк из 10М занял полсекунды).

user1072112 17 мар '15 в 18:00 2015-03-17 18:00 · Answer 2 · 2015-03-17 18:00

Вот небольшая функция для вас. Как вы говорите, он захватывает "пакет" строк со случайной начальной точкой в файле.

randline() {
  local lines c r _

  # cache the number of lines in this file in a symlink in the temp dir
  lines="/tmp/${1//\//-}.lines"
  if [ -h "$lines" ] && [ "$lines" -nt "${1}" ]; then
    c=$(ls -l "$lines" | sed 's/.* //')
  else
    read c _ < <(wc -l $1)
    ln -sfn "$c" "$lines"
  fi

  # Pick a random number...
  r=$[ $c * ($RANDOM * 32768 + $RANDOM) / (32768 * 32768) ]
  echo "start=$r" >&2

  # And start displaying $2 lines before that number.
  head -n $r "$1" | tail -n ${2:-1}
}

Изменить echo линии по мере необходимости.

Преимущество этого решения - меньше труб, меньше ресурсоемких труб (т.е. нет | sort ... |), меньше зависимость от платформы (т.е. нет sort -R который является специфическим для сортировки GNU).

Обратите внимание, что это зависит от Баша $RANDOM переменная, которая может или не может быть на самом деле случайной. Кроме того, он пропустит строки, если ваш исходный файл содержит более 32768^2 строк, и есть крайний случай сбоя, если число строк, которые вы указали (N), составляет>1, а случайная начальная точка меньше, чем N строк из начало. Решение этой проблемы оставлено в качестве упражнения для читателя.:)

ОБНОВЛЕНИЕ № 1:

mklement0 задает отличный вопрос в комментариях о потенциальных проблемах производительности с head ... | tail ... подход. Честно говоря, я не знаю ответа, но я надеюсь, что оба head а также tail оптимизированы настолько, что они не буферизуют ВСЕ входные данные до отображения их выходных данных.

На случай, если моя надежда не оправдается, вот альтернатива. Это хвост "скользящего окна" на основе awk. Я включу его в предыдущую функцию, которую я написал, чтобы вы могли проверить ее, если хотите.

randline() {
  local lines c r _

  # Line count cache, per the first version of this function...
  lines="/tmp/${1//\//-}.lines"
  if [ -h "$lines" ] && [ "$lines" -nt "${1}" ]; then
    c=$(ls -l "$lines" | sed 's/.* //')
  else
    read c _ < <(wc -l $1)
    ln -sfn "$c" "$lines"
  fi

  r=$[ $c * ($RANDOM * 32768 + $RANDOM) / (32768 * 32768) ]

  echo "start=$r" >&2

  # This simply pipes the functionality of the `head | tail` combo above
  # through a single invocation of awk.
  # It should handle any size of input file with the same load/impact.
  awk -v lines=${2:-1} -v count=0 -v start=$r '
    NR < start { next; }
    { out[NR]=$0; count++; }
    count > lines { delete out[start++]; count--; }
    END {
      for(i=start;i<start+lines;i++) {
        print out[i];
      }
    }
  ' "$1"
}

Встроенный скрипт awk заменяет head ... | tail ... конвейер в предыдущей версии функции. Это работает следующим образом:

Он пропускает строки до начала, как определено ранней рандомизацией.
Записывает текущую строку в массив.
Если массив превышает количество строк, которые мы хотим сохранить, он удаляет первую запись.
В конце файла он печатает записанные данные.

В результате процесс awk не должен увеличивать объем памяти, поскольку выходной массив обрезается так же быстро, как и создается.

ПРИМЕЧАНИЕ: я на самом деле не проверял это с вашими данными.

ОБНОВЛЕНИЕ № 2:

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

randlines() {
  local lines c r _

  # Line count cache...
  lines="/tmp/${1//\//-}.lines"
  if [ -h "$lines" ] && [ "$lines" -nt "${1}" ]; then
    c=$(ls -l "$lines" | sed 's/.* //')
  else
    read c _ < <(wc -l $1)
    ln -sfn "$c" "$lines"
  fi

  # Create a LIST of random numbers, from 1 to the size of the file ($c)
  for (( i=0; i<$2; i++ )); do
    echo $[ $c * ($RANDOM * 32768 + $RANDOM) / (32768 * 32768) + 1 ]
  done | awk '
    # And here inside awk, build an array of those random numbers, and
    NR==FNR { lines[$1]; next; }
    # display lines from the input file that match the numbers.
    FNR in lines
  ' - "$1"
}

Это работает путем подачи списка случайных номеров строк в awk в качестве "первого" файла, а затем с помощью awk печатаются строки из "второго" файла, номера строк которых были включены в "первый" файл. Оно использует wc определить верхний предел случайных чисел для генерации. Это означает, что вы будете читать этот файл дважды. Если у вас есть другой источник для количества строк в файле (например, база данных), подключите его здесь.:)

Ограничивающим фактором может быть размер этого первого файла, который должен быть загружен в память. Я считаю, что 30000 случайных чисел должны занимать всего около 170 КБ памяти, но то, как массив будет представлен в ОЗУ, зависит от реализации используемого вами awk. (Хотя, как правило, реализации awk (включая Gawk в Ubuntu) довольно хорошо сводят к минимуму потери памяти.)

Это работает для вас?

user632407 17 мар '15 в 16:46 2015-03-17 16:46 · Answer 3 · 2015-03-17 16:46

Простое (но медленное) решение

n=15 #number of random lines
filter_before | sort -R | head -$n | filter_after

#or, if you could have duplicate lines
filter_before | nl | sort -R | cut -f2- | head -$n | filter_after
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

или, если хотите, сохраните следующее в randlines скрипт

#!/bin/bash
nl | sort -R | cut -f2 | head -"${1:-10}"

и использовать его как:

filter_before | randlines 55 | filter_after   #for 55 lines

Как это устроено:

sort -R сортирует файл по вычисленным случайным хэшам для каждой строки, поэтому вы получите случайный порядок строк, поэтому первые N строк - это случайные строки.

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

пример:

seq -f 'some line %g' 500 | nl | sort -R | cut -f2- | head -3

печатает в последующих прогонах:

some line 65
some line 420
some line 290

some line 470
some line 226
some line 132

some line 433
some line 424
some line 196

демо с повторяющимися строками:

yes 'one
two' | head -10 | nl | sort -R | cut -f2- | head -3

в последующих прогонах выведите:

one
two
two

one
two
one

one
one
two

Наконец, если хотите, можете использовать вместо cutsed тоже:

sed -r 's/^\s*[0-9][0-9]*\t//'

user1342199 17 мар '15 в 15:03 2015-03-17 15:03 · Answer 4 · 2015-03-17 15:03

#!/bin/bash
#contents of bashScript.sh

file="$1";
lineCnt=$2;
filter="$3";
nfilter="$4";
echo "getting $lineCnt lines from $file matching '$filter' and not matching '$nfilter'" 1>&2;

totalLineCnt=$(cat "$file" | grep "$filter" | grep -v "$nfilter" | wc -l | grep -o '^[0-9]\+');
echo "filtered count : $totalLineCnt" 1>&2;

chances=$( echo "$lineCnt/$totalLineCnt" | bc -l );
echo "chances : $chances" 1>&2;

cat "$file" | awk 'BEGIN { srand() } rand() <= $chances { print; }' | grep "$filter" | grep -v "$nfilter" | head -"$lineCnt";

использование:

получить 1000 случайных выборок

bashScript.sh /path/to/largefile.txt 1000

строка имеет номера

bashScript.sh /path/to/largefile.txt 1000 "[0-9]"

не Майк и Джейн

bashScript.sh /path/to/largefile.txt 1000 "[0-9]" "mike|jane"

user399026 18 мар '15 в 15:24 2015-03-18 15:24 · Answer 5 · 2015-03-18 15:24

Я использовал rlдля рандомизации линии и обнаружил, что он выполняет довольно хорошо. Не уверен, как это масштабируется в вашем случае (вы бы просто сделать, например, rl FILE | head -n NUM). Вы можете получить его здесь: http://arthurdejong.org/rl/

0

Источник

user399026 18 мар '15 в 15:24