やはりこの言語、ハマりまくりでした。
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);
関連記事
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿