Выбрать N случайных строк из файла общедоступными инструментами *nix

#php #linux #bash #unix #reservoirsampling

Файл текстовый, UTF-8, 500 тысяч строк, длинной от 5 до 185 байт каждая.

Интересует в первую очередь оптимальное по времени решение.

Под общедоступными должно понимать инструменты, которые можно найти на любом *nix
VDS из коробки, включая Linux, FreeBSD, OpenBSD и так далее.

Сейчас используется PHP и время устраивает, но бытует мнение, что можно быстрее:


Ответы
Ответ 1

можно использовать sort -R input | head -n N, но скорость работы будет значительнее
ниже, чем того же shuf ,но лучше сравнить результаты. 

На моем ноутбуке с SSD дискоим, 16 Гб ОЗУ 2133 MHz, Intel Core i7-7700HQ  2,8 GHz
слудующие результаты: 

У меня есть файл размером 2.6G и с 13,9 млн строк данных

➜  /tmp wc -l test.log
 13904430 test.log

➜  /tmp time awk 'rand() <0.001' < test.log |wc
   13945   32795 2774781
awk 'rand() <0.001' < test.log  124.15s user 1.18s system 99% cpu 2:05.68 total
wc  0.01s user 0.00s system 0% cpu 2:05.68 total


➜  /tmp time sort -R test.log | head -n 10000 >/dev/null
^C^C (тут я не дождался и отменил процесс)
sort -R test.log  751.22s user 72.00s system 54% cpu 25:02.76 total
head -n 10000 > /dev/null  0.00s user 0.00s system 0% cpu 25:01.63 total


➜  /tmp time shuf -n 10000 test.log |wc
   10000   23637 1986699
shuf -n 10000 test.log  4.59s user 0.66s system 98% cpu 5.326 total
wc  0.01s user 0.00s system 0% cpu 5.325 total

 ➜  /tmp time perl -ne 'print if (rand() < 0.001)' test.log | wc
   13872   32644 2755088
perl -ne 'print if (rand() < 0.001)' test.log  1.74s user 0.70s system 99% cpu 2.454
total
wc  0.01s user 0.00s system 0% cpu 2.453 total


также написал ради эксперимента вот такую функцию, но не дождался результата больше
20 минут

➜  /tmp function rread() { while read line; do
    if ((RANDOM%1390)); then
        echo $line;
    fi;
done < $1  }
➜  /tmp time rread test.log > /dev/null


итоговый результат таков:


perl за 2.453 
shuf за 5.325
awk  за 2:05.68
sort -R больше, чем 25:01.63
read думаю больше, чем в 4 пункте


p.s. 
также решил пропробовать через sed выдернуть строку. 
написал вот такой скрипт 

#!/bin/bash

RANGE=$(wc -l < $2)
for i in `seq 1 $1`
{
  number=$(echo $RANDOM % $RANGE + 1 | bc)
  sed -n ''${number}'p' $2 
}


результат удручающий 

➜  /tmp time ./custom.sh 10 test.log | wc
      10      22    1567
./custom.sh 10 test.log  35.91s user 6.76s system 99% cpu 42.872 total
wc  0.00s user 0.00s system 0% cpu 42.871 total

➜  /tmp time ./custom.sh 100 test.log | wc
     100     197   16407
./custom.sh 100 test.log  362.07s user 70.14s system 99% cpu 7:15.37 total
wc  0.00s user 0.00s system 0% cpu 7:15.37 total


UPDATE

cat <<'EOT' >> p.php 

EOT
➜ php -f p.php
12.23668194, 0.00460792


хочу заметить, что весь процесс от запуска и до завершения скрипта больше на 2-3
секунды. Я думаю, было бы правильно и это время учитывать. 

UPDATE2


#include 
#include 
#include 
using namespace std;


unsigned int rand_interval(unsigned int min, unsigned int max);

int main(){
 ifstream is("test.log");

 char c;
 string line;
 int count=13000;
 while (!is.eof() && count-->0){
  while (c != '\n'){
   unsigned int rand = rand_interval(0, 13900000);
   is.seekg(rand);
   c = is.get();
  }
  getline(is,line);
  cout << line << endl;
  c = '0';
 }


 return 0;
}

unsigned int rand_interval(unsigned int min, unsigned int max)
{
    int r;
    const unsigned int range = 1 + max - min;
    const unsigned int buckets = RAND_MAX / range;
    const unsigned int limit = buckets * range;
    do
    {
        r = rand();
    } while (r >= limit);

    return min + (r / buckets);
}


и результат 

➜  /tmp time ./a.out | wc
   13000   29103 2209950
./a.out  4.54s user 7.00s system 98% cpu 11.672 total
wc  0.02s user 0.07s system 0% cpu 11.671 total


Ответ 2

shuf file.txt -n5


file.txt - ваш файл

5 - количество строк(любое число)

Описание команды на сайте GNU (к вопросу о "стандартности")