okkyの日記： 【緩募】同じタグを持った行がなるべく隣接しないようにする方法…

<タグ>,<値>

のように、タグと値がカンマで分割されている行が沢山並んでいるファイルがある。タグも値も、実際にはただのテキストである。同じタグを持つ異なる値/行は沢山ある。同じ値を持つ行は1つとしてない。

タグは数種類から数百種類しか無い。コレに対して行全体は100万行位ある場合がありえる。個数は不明である。

タグごとに行の個数は若干異なるものの、だいたい同じぐらいの行数だと思ってもらっていい。

以上のようなときに。

なるべく同じタグが隣接した行にならないように全体を並び替えたい。
乱暴な話、タグが T1, T2, T3, T4 と4つの場合は、
T1⇒T2⇒T3⇒T4⇒T1⇒T2⇒T3⇒T4…
のようにタグが1行毎に循環して欲しい。

値は全部違うが、値のHASHとかで並べ替える、というランダム性を期待するアルゴリズムは、とりあえず使いたくない(というか値でソートするのはやめたい。それはそれで変な規則性が出てしまうのだ)。

で、最後の厄介な条件としてなるべくbashと、通常の外部コマンドだけでやりたい。

----

乱暴な話、Perlでやれば簡単だ。

while ( <STDIN> ) {
　　　　m/^([^,]+),(.*)$/;
          $tag = $1;
          $value = $2;
          chomp $value;
 
         push ( @{$table{$tag}} ,$value );
}
 
while ( 1 ) {
        foreach $tag ( keys %table ) {
              $value   = pop (  @{ $table{$tag}} );
              if ( defined( $value )) {
                      undef $table{$tag};
              } else {
                      print $tag . "," . $value;
              }
        }
}

これでいい(たぶん)。

でもその前後にある部分が面倒くさすぎて、perl を巻き込みたくないのだ。つーか perl の
SIGCHLDをたまに取りこぼすバグ
で悩まされたくないのだ。

さて…なにかよい方法はないだろうか…

解答例

[WindVoice (14680)]

個人的には、bashにこれをさせるのか、とは思いますがそれはさておき。

(1) 入力(data)を1行ずつ読み、タグをチェック。
(2) 前回の出力のタグ(以下prekey)と現在行のタグが違う場合は、そのまま出力。
(3) 前回の出力のタグ(以下prekey)と現在行のタグが同じ場合は、出力せずバッファに保存(nextdata)。
(4) dataの処理が終わって、nextdataにデータが残っていれば、(1)～(3)をnextdataに対して再実行。
(5) もし(1)～(3)の処理で一度も出力できなかったのにnextdataがある場合(これは同じタグばかり残った場合)は諦めてまとめて出力して終了。

#!/bin/bash

inputfile=data.txt
outputfile=result.txt

nextdata=`cat $inputfile`

while [ 1 ]
do
    data=$nextdata
    nextdata=
    nextflag=0
    outputexists=0
    for var in $data
    do
        key=`echo $var | awk -F'[,]' '{print $1}'`
        if [ x$key != x$prekey ]; then
            echo $var >> $outputfile
            prekey=$key
            outputexists=1
        else
            if [ $nextflag = 1 ]; then
                printf -v nextdata "%s\n%s" "$nextdata" "$var"
            else
                nextdata=$var
            fi
            nextflag=1
        fi
    done
    if [ $outputexists = 0 ]; then
        echo -e "$nextdata" >> $outputfile
        exit
    fi
    if [ $nextflag = 0 ]; then
        exit
    fi
done

[例:data.txt]
aaa,data1
bbb,data2
aaa,data12
aaa,data123
bbb,datad1
ccc,data3
aaa,data123
aaa,data124
aaa,data125
ccc,data31

[例:result.txt]
aaa,data1
bbb,data2
aaa,data12
bbb,datad1
ccc,data3
aaa,data123
ccc,data31
aaa,data123
aaa,data124
aaa,data125

■　懸念

bashはGBサイズのデータに耐えられるのかな……
データがタグでソートされているような場合、処理効率が悪く耐えられないくらい時間がかかるかも。

--
人生は七転び八起き、一日は早寝早起き

Re:解答例

[WindVoice (14680)]

最後に諦めてどばっと出力してしまうのはツメを誤ったなと思い直しました。
たぶん出力のあたまから探していって、どこか挿入できるところに1行ずつ挿入してゆけば、完全に条件を満たす出力が作れる可能性がありますね。
（でも実現するコードは書いていませんが）

--
人生は七転び八起き、一日は早寝早起き

Re:解答例

[okky (2487)]

あぁ、なるほど…

それなら別の手がありますね。

1) まず key が先頭にあるんだから、それに基づいて sort (同じ key が集まる)
2) 1行づつ読んで、keyが同じ間は、先頭に番号を１づつ増やしながら振る。
        結果はテンポラリファイルに保存。
　　key が変わったら番号を1に戻してそこから振り直す
3) 行頭に割り振った「番号」にもとづいて numerical sort をかける
4) 行頭の「番号」を外す

aaa, d001
bbb, d001
aaa, d003
bbb, d002
ccc, d010
          :
    　⇒
aaa.d001
aaa.d003
bbb.d001
bbb,d002
ccc,d010
          :
    　⇒
1,aaa,d001
2,aaa,d003
1,bbb,d001
2,bbb,d002
1,ccc,d010
          :
    　⇒
1,aaa,d001
1,bbb,d001
1,ccc,d010
2,aaa,d003
2,bbb,d002
          :
    　⇒
aaa,d001
bbb,d001
ccc,d010
aaa,d003
bbb,d002

これなら明示的な一時ファイルが1つ、sortが自前で用意する一時ファイルがいくつかあれば、どうにかなるな…

--
fjの教祖様

実装してみた

[okky (2487)]

   cat data |\   ←実際はここは別のプログラムがデータを流し込んでくると思いねぇ
   sort |\          ← まずは key でソート
   gawk 'BEGIN{ FS="," } (key !=$1){ key = $1; count=1 }{ print count "," $0 ;count++ }' |\　← 頭に key ごとの番号ふり
   sort --field-separator="," --key=1 -n |\    ← さっきつけた番号でソート
   sed -r 's/^[0-9]+,//g'                                ←行等につけた番号を取り外し

動いた動いた(上記が動かないとしたら、コピペの途中で失敗したという事)

--
fjの教祖様