SWEet

A Software Engineer Is Eating Technologies

アナグラム判定メソッドの実行速度を比較してみた

今回は前回の続きといいますか、似たような問題に対する実装を複数パターンあったのでその速度を比較してみました。

問題

二つの文字列が与えられた時、片方がもう片方の並び替えになっているかどうかを決定するメソッドを書いてください。

前提条件:空白や大文字小文字も区別する。文字コードはASCIIコードだけで構わない。

というわけで書いてみました。

実装コード

static boolean MyisAnagram(String word1,String word2){
        int sumCode_1=0;
        int sumCode_2=0;
        
        if(word1.length()!=word2.length())
            return false;
        
        for(int i=0;i<word1.length();i++){
            sumCode_1 += word1.charAt(i);
        }
        for(int i=0;i<word2.length();i++){
            sumCode_2 += word2.charAt(i);
        }
        
        if(sumCode_1 == sumCode_2){
            return true;
        }
        else{
            return false;
        }
        
    }

あ、今回はjavaです。Eclipseで書いているので書いてる途中に間違えがすぐわかるので便利です。

上記のコードは自分が完全に0から考えたメソッドです。

文字列の文字コードを全て足し合わせて一致しているならアナグラムであると言えます。

中々スマートに書けたかなとは思います。

次に解答例としてあった二つの実装パターンをご紹介します。

static String sort(String s){
        char[] content = s.toCharArray();
        java.util.Arrays.sort(content);
        return new String(content);
    }
    
    static boolean permutation(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        return sort(s).equals(sort(t));
    }
static boolean permutation_2(String s,String t){
        if(s.length() != t.length()){
            return false;
        }
        
        int[] letters = new int[256]; //文字コードの仮定;
        
        char[] s_array = s.toCharArray();  
        for(char c:s_array){
            letters[c]++;
        }
        
        for(int i=0;i<t.length();i++){
            int c = (int)t.charAt(i);
            if(--letters[c] < 0){
                return false;
            }
        }
        return true;
    }

1個目はsortメソッドを作成し、二つの文字列を整列してから比較しています

2個目のメソッドは文字コードのリストをboolで作って出現したら1に、二個目の文字列を判定して、存在したら-1して0より小さくなったらその時点でfalseというのは面白いですね。

比較結果

メインメソッドを以下のように実装し実行時間を計ってみました。

public static void main(String[] args){
        long start = System.nanoTime();
        MyisAnagram("word","wo rd");
        MyisAnagram("word","fugafuga");
        MyisAnagram("word","rdow");
        long end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation("word","wo rd");
        permutation("word","fugafuga");
        permutation("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
        
        start = System.nanoTime();
        permutation_2("word","wo rd");
        permutation_2("word","fugafuga");
        permutation_2("word","rdow");
        end = System.nanoTime();
        System.out.println("Processing time:" + (end - start) + "ns");
    }

結果は以下のとおりになりました

MyisAnagram(自分の実装) permutation(解答例1) permutation_2(解答例2)
13927ns 226304ns 5590ns

自分のは2位でしたね。悔しい。やはり全て足し合わせてから比較して結果を返すのと、比較しつつ結果を返すので差がついてしまったのでしょうか。 解答例1の方はコードもスマートでしたがやはり関数呼び出しが入る分遅くなってしまったのでしょうか。

文字列操作を弄るのは楽しいですね。 次回もまた何かプログラムを載せると思います。なにか御指摘ありましたら是非お願いします。

今月はまさかの2回更新できました。すごい