In a Bash script, I want to pick out N random lines from input file and output to another file.
How can this be done?
Use shuf
with the -n
option as shown below, to get N
random lines:
shuf -n N input > output
shuf file.txt
outputs randomly the lines to standard output. ----- shuf -r -n 5 file.txt
- The flag -r
allows the command to yield repeated lines; Don't forget to set the number of lines you want to be printed using the -n
flag, otherwise it will output forever. ------ sort -R
will shuffle, but it will also group identical keys. So if you have repeated lines but you don't want repeated values, pipe it with the uniq
command. e.g. sort -R file.txt | uniq
Sort the file randomly and pick first 100
lines:
lines=100
input_file=/usr/share/dict/words
# This is the basic selection method
<$input_file sort -R | head -n $lines
# If the file has duplicates that must never cause duplicate results
<$input_file sort | uniq | sort -R | head -n $lines
# If the file has blank lines that must be filtered, use sed
<$input_file sed $'/^[ \t]*$/d' | sort -R | head -n $lines
Of course <$input_file
can be replaced with any piped standard input. This (sort -R
and $'...\t...'
to get sed
to match tab chars) works with GNU/Linux and BSD/macOS.
sort
actually sorts identical lines together, so if you may have duplicate lines and you have shuf
(a gnu tool) installed, it's better to use it for this.
shuf -n
acts quite instantaneously.
sort -R
is probably GNU option, install GNU coreutils. btw, shuf
is also part of coreutils.
sort -R input | head -n <num_lines>
. The input file was 279GB, with 2bi+ lines. Can't share it, though. Anyway, the point is you can keep some lines in memory with shuffle to do the random selection of what to output. Sort is going to sort the entire file, regardless of what your needs are.
Well According to a comment on the shuf answer he shuffed 78 000 000 000 lines in under a minute.
Challenge accepted...
EDIT: I beat my own record
$ time ./powershuf.py -n 10 --file lines_78000000000.txt > /dev/null
./powershuf.py -n 10 --file lines_78000000000.txt > /dev/null 0.02s user 0.01s system 80% cpu 0.047 total
The reason it is so fast, well I don't read the whole file and just move the file pointer 10 times and print the line after the pointer.
First I needed a file of 78.000.000.000 lines:
seq 1 78 | xargs -n 1 -P 16 -I% seq 1 1000 | xargs -n 1 -P 16 -I% echo "" > lines_78000.txt
seq 1 1000 | xargs -n 1 -P 16 -I% cat lines_78000.txt > lines_78000000.txt
seq 1 1000 | xargs -n 1 -P 16 -I% cat lines_78000000.txt > lines_78000000000.txt
This gives me a a file with 78 Billion newlines ;-)
Now for the shuf part:
$ time shuf -n 10 lines_78000000000.txt
shuf -n 10 lines_78000000000.txt 2171.20s user 22.17s system 99% cpu 36:35.80 total
The bottleneck was CPU and not using multiple threads, it pinned 1 core at 100% the other 15 were not used.
Python is what I regularly use so that's what I'll use to make this faster:
#!/bin/python3
import random
f = open("lines_78000000000.txt", "rt")
count = 0
while 1:
buffer = f.read(65536)
if not buffer: break
count += buffer.count('\n')
for i in range(10):
f.readline(random.randint(1, count))
This got me just under a minute:
$ time ./shuf.py
./shuf.py 42.57s user 16.19s system 98% cpu 59.752 total
I did this on a Lenovo X1 extreme 2nd gen with the i9 and Samsung NVMe which gives me plenty read and write speed.
I know it can get faster but I'll leave some room to give others a try.
Line counter source: Luther Blissett
-r
option, shuf doesn't output the same line twice, and of course this takes additional processing time.
My preferred option is very fast, I sampled a tab-delimited data file with 13 columns, 23.1M rows, 2.0GB uncompressed.
# randomly sample select 5% of lines in file
# including header row, exclude blank lines, new seed
time \
awk 'BEGIN {srand()}
!/^$/ { if (rand() <= .05 || FNR==1) print > "data-sample.txt"}' data.txt
# awk tsv004 3.76s user 1.46s system 91% cpu 5.716 total
seq 1 100 | python3 -c 'print(__import__("random").choice(__import__("sys").stdin.readlines()))'
Here is an "incremental random sampler" that picks exactly N samples from any number of lines in one pass, never storing more than N lines in memory.
It works as follows:
I did a proof to make sure that this gives each line an equal probability of being included in the final sample. I also did some large empirical experiments to demonstrate the same thing.
I came up with this algorithm when I needed to get a random sample of 10,000 messages from a log with unknown millions of entries over a variable amount of time. Using this approach, I didn't need to store more than N messages at once, nor guess in advance what fraction of the messages to keep in order to end up with the desired N samples.
Here is a python implementation. You can call it from the command line via:
`cat <inputFile> | python incremental_sampler.py [#samples=1000] > <outputFile>`
or call it from your own python program. It is simple enough that I have found it trivial to port to other languages.
import random
import sys
# Incremental random sampler.
# Author: Randy Wilson, Ph.D.
# Date: 14 February 2007
# Generates a random sample of all the values passed to it,
# without ever having to store more than the number of samples
# being taken ('max_samples').
# Stores the first 'max_samples' values.
# Then chooses a random index from 0..num_samples-1.
# If the random index is within the first max_samples,
# then that array element is replaced.
# Otherwise, the new value is ignored.
# This gives every incoming sample the same probability of
# max_samples/num_samples of being included.
#
# For example, if max_samples=1000, and 50,000 values are
# passed to add_sample(), then the first 1000 samples are all kept.
# After that, there is a 1000/1001, 1000/1002, etc., chance
# of each sample replacing one selected earlier.
# After adding all 50,000 samples, get_samples() will shuffle the
# 1000 samples that were kept and return them.
# Never were more than 1000 samples stored during the entire process.
# This means you could get a sample from billions of values
# without blowing out memory.
class IncrementalSampler:
def __init__(self, sample_size):
# Number of samples desired in the end
self.sample_size = sample_size
# Number of samples added via add_sample so far
self.num_samples = 0
# Values included in the random sample so far. These may be replaced by values added later.
self.samples = []
def add_sample(self, value):
if self.num_samples < self.sample_size:
self.samples.append(value)
else:
position = random.randint(0, self.num_samples)
if position < self.sample_size:
self.samples[position] = value
self.num_samples += 1
def get_samples(self):
random.shuffle(self.samples)
return self.samples
# Command-line interface.
# Usage: cat <file> | incremental_sampler.py [#samples] > <outputFile>
sample_size = 1000
if len(sys.argv) > 1:
sample_size = int(sys.argv[1])
sampler = IncrementalSampler(sample_size)
for line in sys.stdin:
sampler.add_sample(line.rstrip('\r\n'))
for line in sampler.get_samples():
print(line)
Just for completeness's sake and because it's available from Arch's community repos: there's also a tool called shuffle
, but it doesn't have any command line switches to limit the number of lines and warns in its man page: "Since shuffle reads the input into memory, it may fail on very large files."
# Function to sample N lines randomly from a file
# Parameter $1: Name of the original file
# Parameter $2: N lines to be sampled
rand_line_sampler() {
N_t=$(awk '{print $1}' $1 | wc -l) # Number of total lines
N_t_m_d=$(( $N_t - $2 - 1 )) # Number oftotal lines minus desired number of lines
N_d_m_1=$(( $2 - 1)) # Number of desired lines minus 1
# vector to have the 0 (fail) with size of N_t_m_d
echo '0' > vector_0.temp
for i in $(seq 1 1 $N_t_m_d); do
echo "0" >> vector_0.temp
done
# vector to have the 1 (success) with size of desired number of lines
echo '1' > vector_1.temp
for i in $(seq 1 1 $N_d_m_1); do
echo "1" >> vector_1.temp
done
cat vector_1.temp vector_0.temp | shuf > rand_vector.temp
paste -d" " rand_vector.temp $1 |
awk '$1 != 0 {$1=""; print}' |
sed 's/^ *//' > sampled_file.txt # file with the sampled lines
rm vector_0.temp vector_1.temp rand_vector.temp
}
rand_line_sampler "parameter_1" "parameter_2"
In the below 'c' is the number of lines to select from the input. Modify as needed:
#!/bin/sh
gawk '
BEGIN { srand(); c = 5 }
c/NR >= rand() { lines[x++ % c] = $0 }
END { for (i in lines) print lines[i] }
' "$@"
c
lines are selected. At best you can say that the average number of lines being selected is c
.
Commented
Jun 14, 2022 at 5:44
c/NR
will be guaranteed to be larger than any value produced from rand
for the first c lines. After that, it may or may not be larger than rand
. Therefore we can say that lines
in the end contains at least c entries, and in general more than that, i.e. not exactly c entries. Furthermore, the first c lines of the file are always picked, so the whole selection is not what could be called a random pick.
Commented
Jun 15, 2022 at 6:00
sort -R
as it does a lot of excess work, particularly for long files. You can use$RANDOM
,% wc -l
,jot
,sed -n
(à la stackoverflow.com/a/6022431/563329), and bash functionality (arrays, command redirects, etc) to define your ownpeek
function which will actually run on 5,000,000-line files.