2

さまざまな長さの数百行を含むテキストファイルがあります。ここで、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

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 に答える
3

すべてのオフセットを生成してから、ファイルを 1 回パスします。必要な数のオフセットoffsets(1 行に 1 つの数値)があると仮定すると、次のsedような単一のスクリプトを生成できます。

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

出力はsedスクリプトで、一時ファイルに保存するか、(方言がサポートしている場合) 2 番目のインスタンス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-10T15:39:57.763 に答える
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 を使用した興味深い 2 パス オプションです。 

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-10T16:50:00.437 に答える
-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 に答える