[アルゴリズム] マージソートのプログラミング(AWK編)

2017/03/18

AWK テクノロジー プログラミング 特集

t f B! P L
やはりこの言語、ハマりまくりでした。 AWK言語が便利だと思うのはLinuxOSにデフォルトで存在する事と、ディスクIOの扱いと、コマンドラインのワンライナーが便利すぎる点でしょう。 今回のようにアルゴリズムを関数化するのは、あまり得意な言語出ないことは100も承知ですが、ここはTRYする場なので、そうしたセオリーは無視して挑戦してみます。

ソースコード

BEGIN{ FS=","; } function midPoint(strs){ split(strs , nums); return int(length(nums) / 2 + 0.5); } function setMerge(s1 , s2){ split(s1 , mergeArr1); split(s2 , mergeArr2); split("" , mergeArr); while(length(mergeArr1) || length(mergeArr2)){ if(length(mergeArr1) == 0){ mergeArr[length(mergeArr)+1] = mergeArr2[1]; tmp=""; if(length(mergeArr2)>=2){ tmp = mergeArr2[2]; for(i=3; i<=length(mergeArr2); i++){ tmp = tmp","mergeArr2[i]; } } split(tmp , mergeArr2); } else if(length(mergeArr2) == 0){ mergeArr[length(mergeArr)+1] = mergeArr1[1]; tmp=""; if(length(mergeArr1)>=2){ tmp = mergeArr1[2]; for(i=3; i<=length(mergeArr1); i++){ tmp = tmp","mergeArr1[i]; } } split(tmp , mergeArr1); } else if(mergeArr1[1] > mergeArr2[1]){ mergeArr[length(mergeArr)+1] = mergeArr2[1]; tmp=""; if(length(mergeArr2)>=2){ tmp = mergeArr2[2]; for(i=3; i<=length(mergeArr2); i++){ tmp = tmp","mergeArr2[i]; } } split(tmp , mergeArr2); } else{ mergeArr[length(mergeArr)+1] = mergeArr1[1]; tmp=""; if(length(mergeArr1)>=2){ tmp = mergeArr1[2]; for(i=3; i<=length(mergeArr1); i++){ tmp = tmp","mergeArr1[i]; } } split(tmp , mergeArr1); } } res = mergeArr[1]; for(i=2; i<=length(mergeArr); i++){ res = res","mergeArr[i]; } return res; } function mergeSort(strs, str1, str2){ split(strs , numbers); if(length(numbers) == 0){ return ""; } else if(length(numbers) == 1){ return numbers[1]; } else if(length(numbers) == 2){ if(numbers[1] > numbers[2]){ tmp = numbers[1]; numbers[1] = numbers[2]; numbers[2] = tmp; } return numbers[1]","numbers[2]; } else{ midNum = midPoint(strs); str1 = numbers[1]; for(i=2; i<=midNum; i++){ str1 = str1","numbers[i]; } str2 = numbers[midNum+1]; for(i=midNum+2; i<=length(numbers); i++){ str2 = str2","numbers[i]; } str1 = mergeSort(str1); str2 = mergeSort(str2); return setMerge(str1 , str2); } } { print mergeSort($0); }

実行

$ echo "10,2,12,7,16,8,13" | awk -f mergeSort.awk 2,7,8,10,12,13,16 今回から配列は、カンマ区切りのCSV方式の文字列として受け渡すようにしてます。 本当はもっと配列っぽい見え方にしたかったんだけどね。

解説

ローカル変数の扱い

AWKは基本的に全てグローバル変数になるという事を認識した上で、特定の関数内でのみ対応したいローカル変数を扱いたい場合は、関数の引数に、定義してあげることでローカル扱いになるようです。 そして、awk言語を使う人の暗黙の了解であるルールが存在するらしく、ローカル変数を明示的に定義する場合は、変数の前にスペースを入れて見た目分かるようにするらしいです。 もちろん、スペース入れなくてもローカル変数扱いされますよ。 function mergeSort(strs, str1, str2){

配列の扱い

shellでも同様の処理を行ったんですが、関数に配列を受け渡す事はできても、returnする事ができないので、受け渡しも受け取りも、全て文字列に戻して行うようにルール化してみました。 なので、少し長いプログラムになってますが、今後進めていく上で簡素化されていくでしょう。 ちなみに、関数化する方式は全て統一していて下記のようにしています。 res = arr[1]; for(i=2; i<=length(arr); i++){ res = res","arr[i]; } return res; arrが配列でresがカンマ区切りの文字列です。

配列操作(追加)※push

awk言語には配列の便利な関数が存在しないので、全て手作業で行います。 arr[length(arr)+1] = string; 上記の書き方で、配列の後ろに値を追加することができます。

配列の先頭を除外する※shift

これが一番困った処理なのですが、やり方としては、配列の先頭を無視して2番目以降を繰り返し文で追加していくやり方です。 ただし、配列の数が少ないとエラーが出るので、if文を入れてます。 str=""; if(length(arr)>=2){ str = arr[2]; for(i=3; i<=length(arr); i++){ str = str","arr[i]; } } split(tmp , arr);

関連記事

たくさんのプログラム言語でアルゴリズム学習

人気の投稿

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。

ブログ アーカイブ