如何从文件中选择随机行

我有一个文本文件，其中包含10数百行，长度不同。现在我想随机选择N行，将它们保存在另一个文件中，并将它们从原始文件中删除。我发现这个问题的一些答案，但他们大多数使用一个简单的想法：排序文件，并选择第一或最后N行。不幸的是，这个想法对我不起作用，因为我想保留行的顺序。我试过这段代码，但它非常慢，需要数小时。如何从文件中选择随机行

FILEsrc=$1; 
FILEtrg=$2; 
MaxLines=$3; 
let LineIndex=1; 
while [ "$LineIndex" -le "$MaxLines" ] 
do 
# count number of lines 
NUM=$(wc -l $FILEsrc | sed 's/[ \r\t].*$//g'); 
let X=(${RANDOM} % ${NUM} + 1); 
echo $X; 
sed -n ${X}p ${FILEsrc}>>$FILEtrg; #write selected line into target file 
sed -i -e ${X}d ${FILEsrc};  #remove selected line from source file 
LineIndex=`expr $LineIndex + 1`; 
done

我发现这行最耗时的一个代码：

sed -i -e ${X}d ${FILEsrc};

有没有什么办法来克服这个问题，使代码更快吗？因为我很匆忙，请问您可以给我发送完整的c/C++代码吗？

来源

2012-09-10 Hakim

这可以在真正的编程语言中非常快地完成，而不仅仅是一个shell。 –

“快速方法”包括将适当的内容读入内存，操作和写入一次或读取行偏移量，执行增量计算以及一次性写入......在其他环境中都更简单，并且都利用一次写入。 – 2012-09-10 15:27:20

@dystroy：定义“真正的编程语言”。 –

这里有一个完整的围棋程序：

package main 

import (
    "bufio" 
    "fmt" 
    "log" 
    "math/rand" 
    "os" 
    "sort" 
    "time" 
) 

func main() { 
    N := 10 
    rand.Seed(time.Now().UTC().UnixNano()) 
    f, err := os.Open(os.Args[1]) // open the file 
    if err!=nil { // and tell the user if the file wasn't found or readable 
     log.Fatal(err) 
    } 
    r := bufio.NewReader(f) 
    var lines []string // this will contain all the lines of the file 
    for { 
     if line, err := r.ReadString('\n'); err == nil { 
      lines = append(lines, line) 
     } else { 
      break 
     } 
    } 
    nums := make([]int, N) // creates the array of desired line indexes 
    for i, _ := range nums { // fills the array with random numbers (lower than the number of lines) 
     nums[i] = rand.Intn(len(lines)) 
    } 
    sort.Ints(nums) // sorts this array 
    for _, n := range nums { // let's print the line 
     fmt.Println(lines[n]) 
    } 
}

只要你把旅途中的文件在您的GOPATH命名randomlines目录，你可以建立这样的：

go build randomlines

然后调用它像这样：

./randomlines "path_to_my_file"

这将打印N（这里是10）随机线在你的文件中，但不改变顺序。当然，即使在大文件的情况下，它也是即时的。

来源

2012-09-10 15:38:23

你能告诉更多关于你使用的算法吗？尤其对于不熟悉的读者？ –

+1不是因为我赞成这种做法，而是为了对付莫名其妙的倒退。选民，请解释一下？ – tripleee

它只是提取行，在0和行号之间建立一个整数数组，对它进行排序，并使用这个数组来打印行。避免寻找shell黑客的一点是，你可以很容易地改变它，如你所愿。你最喜欢的语言会很容易（java，python等）。 –

一个简单的O（n）的算法中描述：

http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done

来源

2012-09-10 15:38:36 freestyler

这里是相同的[Python中的算法R（'reservoir_sample（）'函数）]（http://stackoverflow.com/a/32792504/4279） – jfs

生成所有的偏移量，则会使整个文件一次通过。假设你有偏移在offsets（每行一个号码）的所需数目可以生成单个sed脚本这样的：

sed "s!.*!&{w $FILEtrg\nd;}!" offsets

输出是sed脚本可以保存到临时文件时，或（如果您sed方言支持它）管材第二sed实例：

... | sed -i -f - "$FILEsrc"

生成offsets文件留作练习。

鉴于你有Linux标签，这应该马上工作。某些其他平台上的默认sed可能不理解\n和/或接受-f -以从标准输入读取脚本。

这里是一个完整的脚本，更新为使用shuf（谢谢@Thor！）来避免可能的重复随机数。

#!/bin/sh 

FILEsrc=$1 
FILEtrg=$2 
MaxLines=$3 

# Add a line number to each input line 
nl -ba "$FILEsrc" | 
# Rearrange lines 
shuf | 
# Pick out the line number from the first $MaxLines ones into sed script 
sed "1,${MaxLines}s!^ *\([1-9][0-9]*\).*!\1{w $FILEtrg\nd;}!;t;D;q" | 
# Run the generated sed script on the original input file 
sed -i -f - "$FILEsrc"

来源

2012-09-10 15:39:57 tripleee

因为我很着急，请问你给我完整的c/C++代码这样做？ – Hakim

你在开玩笑吗？ “sed”的源代码可以在http://savannah.gnu.org/projects/sed – tripleee

我的意思是代码的C++实现，这是我想要的，而不是sed的源代码。 – Hakim

[我已经更新了每个解决方案从输入删除选定的线，但我不是正面的awk是正确的。我自己偏爱bash解决方案，所以我不打算花时间调试它。随意编辑任何错误]

下面是一个简单awk脚本（概率是简单的浮点数，不很好地bash混合管理）：

tmp=$(mktemp /tmp/XXXXXXXX) 
awk -v total=$(wc -l < "$FILEsrc") -v maxLines=$MaxLines ' 
    BEGIN { srand(); } 
    maxLines==0 { exit; } 
    { if (rand() < maxLines/total--) { 
     print; maxLines--; 
     } else { 
     print $0 > /dev/fd/3 
     } 
    }' "$FILEsrc" > "$FILEtrg" 3> $tmp 
mv $tmp "$FILEsrc"

当你打印行到输出，您将递减maxLines以降低选择更多行的概率。但是当你消耗输入时，你减少total以增加概率。极端情况下，当maxLines确实可能性为零时，您可以停止处理输入。在另一个极端，概率命中1次total小于或等于maxLines，你会接受所有其它线路。

这是同样的算法，在（几乎）纯bash使用整数运算来实现：

FILEsrc=$1 
FILEtrg=$2 
MaxLines=$3 

tmp=$(mktemp /tmp/XXXXXXXX) 

total=$(wc -l < "$FILEsrc") 
while read -r line && ((MaxLines > 0)); do 
    ((MaxLines * 32768 > RANDOM * total--)) || { printf >&3 "$line\n"; continue; } 
    ((MaxLines--)) 
    printf "$line\n" 
done < "$FILEsrc" > "$FILEtrg" 3> $tmp 
mv $tmp "$FILEsrc"

来源

2012-09-10 15:54:17 chepner

您仍然需要从源文件中删除所选行。如果它们都是唯一的，那么它就是一个简单的'fgrep -vxf“$ FILEtrg”“$ FILEsrc”'，或者你可以嵌入到脚本中。 – tripleee

你是对的;我错过了这部分问题。 – chepner

下面是用的coreutils，sed和awk一个有趣的双通道选项：

n=5 
total=$(wc -l < infile) 

seq 1 $total | shuf | head -n $n           \ 
| sed 's/^/NR == /; $! s/$/ ||/'           \ 
| tr '\n' ' '                \ 
| sed 's/.*/ & { print >> "rndlines" }\n!(&) { print >> "leftover" }/' \ 
| awk -f - infile

将随机数列表传递给生成awk脚本的sed。如果AWK从上面的管线上拆下，这将是输出：

{ if(NR == 14 || NR == 1 || NR == 11 || NR == 20 || NR == 21) print > "rndlines"; else print > "leftover" }

所以随机行都会被保存在rndlines和leftover休息。

来源

2012-09-10 16:50:00 Thor

+1的'seq | shuf'技巧。但是，使用'head'而不是'tail'是否合理？ – tripleee

你说得对，那么它会更快完成。 – Thor

-1

这可能会为你工作（GNU sed的，排序和seq）：

n=10 
seq 1 $(sed '$=;d' input_file) | 
sort -R | 
sed $nq | 
sed 's/.*/&{w output_file\nd}/' | 
sed -i -f - input_file

哪里$n是行提取的数目。

来源

2012-09-11 06:14:48 potong

提到的“10个数百名”行应排得相当快，所以这是为装饰，排序，去除装饰图案漂亮的情况下。它实际上创建了两个新文件，从原始文件删除行可以通过重命名来模拟。

注意：head和tail不能用来代替awk，因为它们会在给定的行数后关闭文件描述符，从而导致tee退出，从而导致.rest文件中丢失数据。

FILE=input.txt 
SAMPLE=10 
SEP=$'\t' 

<$FILE nl -s $"SEP" -nln -w1 | 
    sort -R | 
    tee \ 
    >(awk "NR > $SAMPLE" | sort -t"$SEP" -k1n,1 | cut -d"$SEP" -f2- > $FILE.rest) \ 
    >(awk "NR <= $SAMPLE" | sort -t"$SEP" -k1n,1 | cut -d"$SEP" -f2- > $FILE.sample) \ 
>/dev/null 

# check the results 
wc -l $FILE* 

# 'remove' the lines, if needed 
mv $FILE.rest $FILE

来源

2014-10-30 15:34:26 liborm

如何从文件中选择随机行

回答

相关问题