2

我有一个包含 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++ 代码来做这件事吗？

4

7 回答 7

6

一个简单的 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-10T15:38:36.457 回答
3

Generate all your offsets, then make a single pass through the file. Assuming you have the desired number of offsets in offsets (one number per line) you can generate a single sed script like this:

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

The output is a sed script which you can save to a temporary file, or (if your sed dialect supports it) pipe to a second sed instance:

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

Generating the offsets file left as an exercise.

Given that you have the Linux tag, this should work right off the bat. The default sed on some other platforms may not understand \n and/or accept -f - to read the script from standard input.

Here is a complete script, updated to use shuf (thanks @Thor!) to avoid possible duplicate random numbers.

#!/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-10T15:39:57.763 回答
3

[我已经更新了每个解决方案以从输入中删除选定的行，但我不肯定这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-10T15:54:17.533 回答
1

这是一个完整的 Go 程序：

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])
    }
}

如果你把 go 文件放在一个名为randomlines你的目录中GOPATH，你可以像这样构建它：

go build randomlines

然后这样称呼它：

  ./randomlines "path_to_my_file"

这将在您的文件中打印 N（此处为 10）随机行，但不会更改顺序。当然，即使是大文件，它也几乎是瞬时的。

于 2012-09-10T15:38:23.537 回答
0

这是一个使用 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

一个随机数列表被传递给 sed，它会生成一个 awk 脚本。如果 awk 从上面的管道中删除，这将是输出：

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

所以随机行保存在rndlines，其余的保存在leftover.

于 2012-09-10T16:50:00.437 回答
0

提到的“10 百”行排序应该很快，所以这是 Decorate、Sort、Undecorate 模式的一个很好的例子。它实际上创建了两个新文件，从原始文件中删除行可以通过重命名来模拟。

注意：不能使用 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-30T15:34:26.883 回答
-1

这可能对你有用（GNU sed、sort 和 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-11T06:14:48.820 回答