0501: Data Conversion - 配列とHashMap

あけましておめでとうございます。

今年一個目のAOJどす。

問題

与えられた変換表にもとづき，データを変換するプログラムを作成しなさい．

データに使われている文字は英字か数字で，英字は大文字と小文字を区別する．変換表に現れる文字の順序に規則性はない．

変換表は空白をはさんで前と後ろの 2 つの文字がある(文字列ではない)．変換方法は，変換表のある行の前の文字がデータに現れたら，そのたびにその文字を後ろの文字に変換し出力する．変換は 1 度だけで，変換した文字がまた変換対象の文字になっても変換しない．変換表に現れない文字は変換せず，そのまま出力する．

入力ファイルには，変換表（最初の n + 1 行）に続き変換するデータ（n + 2 行目以降）が書いてある． 1 行目に変換表の行数 n，続く n 行の各行は，空白をはさんで 2 つの文字，さらに続けて， n + 2 行目に変換するデータの行数 m，続く m 行の各行は 1 文字である． m ＜ 108 とする．出力は，出力例のように途中に空白や改行は入れず 1 行とせよ．

回答１（配列で作る）

変換表の”変換前”と”変換後”でそれぞれ配列を用意し、線形探索で変換する文字列に該当するか探索します。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
    public static void main(String[] a)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String str = null;
        int stackNum;
        int transNum;
        String[] transBefore;
        String[] transAfter;
        
        while((str = in.readLine()) != null){
            if(str.equals("0")){
                System.exit(0);
            }else{
                transNum = Integer.parseInt(str);
                
                transBefore = new String[transNum];
                transAfter = new String[transNum];
                
                for(int i=0; i<transNum; i++){
                    str = in.readLine();
                    transBefore[i] = str.split(" ")[0];
                    transAfter[i] = str.split(" ")[1];                   
                }
                
                stackNum = Integer.parseInt(in.readLine());
                
                for(int i=0; i<stackNum; i++){
                    str = in.readLine();
                    for(int j=0; j<transNum; j++){
                        if(transBefore[j].equals(str)){
                            str = transAfter[j];
                            break;
                        }
                    }
                    System.out.print(str);
                }
                System.out.println();
            }
        }
    }
}

回答２（HashMapで作る）※抜粋

HashMapのkeyを”変換前”、valueを”変換後”として変換表の管理をします。

    	while((str = in.readLine()) != null){
            if(str.equals("0")){
                System.exit(0);
            }else{
                transNum = Integer.parseInt(str);
                transMap.clear();
                
                for(int i=0; i<transNum; i++){
                    str = in.readLine();
                    transMap.put(str.split(" ")[0],str.split(" ")[1]);
                }
                
                stackNum = Integer.parseInt(in.readLine());
                
                for(int i=0; i<stackNum; i++){
                    str = in.readLine();
                    for(int j=0; j<transNum; j++){
                        if(transMap.containsKey(str)){
                            str = transMap.get(str);
                            break;
                        }
                    }
                    System.out.print(str);
                }
                System.out.println();
            }
        }

実行時間の比較

復習がてら配列とHashMapの比較を。

配列

HashMap

ほとんど変わらず、といった所ですがHashMapの方がやや時間がかかっている。

今回は変換表の最大サイズが４０組と小さいので線形探索の方がやや実行時間が短い結果となってるけども、変換表のサイズが数万と大きくなってくる場合にはハッシュの方が早くなってくるのでは。
（その場合には線形探索ではなく二分探索や他の探索方法した方がよいですが。。。）

「配列　HashMap　速度」でググルといろいろな説が出てくるけども、参照速度に関しては（要素数が十分に多い場合）ハッシュの方が早いです。

ハッシュの方が遅いって記事も見たよ、なんで！？

ハッシュは初期容量が設定されていて、要素の挿入によってこの容量を超える場合には確保している領域の拡張が行われるので、ハッシュの方が遅いと言われる所以はデータの挿入が頻繁に行われる（領域の拡張など参照以外の処理が多い）プログラムでの検証をしているのでしょう、多分（不安）

ただ予め要素数が推定でき、初期容量をうまく操れればデータの挿入が多いプログラムでもハッシュ兄貴も良い結果を残してくれるのでは

今回の問題だと最初に変換表を作成し、あとは参照のみといった内容なので（変換表のサイズが十分大きい場合には）ハッシュの方が有効策です。

結論としてはケースバイケースです（強気）

iOSアプリ開発について

実は裏でしこしことiOSアプリのお勉強もしております。

「C＋＋なら大学の授業でやったからObjective-Cもいけるやろ」

くらいの強気だったけども、情報弱者の私には難しいです(ﾟДﾟ)ｸﾞﾜｰ

ただこちらは”アプリとして一つのサービスをとりあえず最後まで作ってみる”のが目的なので、処理内容を深くは追わずに実装することを優先で進める方針です

こちらも要所要所で更新したいと思いますー。

参考：

ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較） - プログラマはサイコロを振らない