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

2017年3月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);

マージソート記事

解説 JavaScript PHP Python Shell AWK

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

このブログを検索

プロフィール

自分の写真
町田市, 東京都, Japan
プログラミングとサーバーを心の底から楽しむクリエーターです。 経営者であり、開発者でもありますが、得意としているのは、アイデア創出です。

ブログ アーカイブ

QooQ