無差別に技術をついばむ鳥

情報処理技術全般を気まぐれにつつくゆるいブログです

ネタつつき52−並列的にFizzBuzzを実装して遊ぶ♪

今日お昼休みにFizzBuzzで遊びました♪それが面白かったので記事としてUPします。
FizzBuzzというのは言葉遊びで、プログラマ採用試験になるケースがあるそうです(詳しくは ウイキペディアを参照)最近これが流行っていますので私もやってみたというわけです。
ひとまず素直に直列アルゴリズムを実装すると・・・


import java.util.*;

//直列処理でFizzBuzzを行う。
public class Main {
    public static void main(String[] args) {
        int count = 2000000;
        String[] numbers = new String[ count ];
        List target = Arrays.asList( numbers );
        long start = System.nanoTime();
        for( int i = 0; i < count; i++ ) {
            int flag = 1;
            int flag1 = 1;
            int number = i + 1;
            if ( ( flag  = number % 3 ) == 0 )
                target.set( i, "Fizz" );
            if ( ( flag1 = number % 5 ) == 0 )
                target.set( i, flag == 0 ? "Fizz Buzz" : "Buzz" );
            if ( flag != 0 && flag1 != 0 )
               target.set( i, ( ( Integer ) number ).toString() );
        }
        long stop = System.nanoTime();
        System.out.println("実行にかかった時間は " + 
            (stop - start) + " ナノ秒です。");
    }
}
※用意した文字列を画面に出力すると時間がかかるので省略しています。

いちいちListインタフェースを使っているのは、なるべくコンテナを抽象化し柔軟にしたかったからです。お遊びにこんなことする必要はないのとも思うのですがひとまず思いついたので素直に実装しました。
次に並列アルゴリズムを実装しました♪


import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
    public static void main(String[] args) {
        String[] numbers = new String[ 2000000 ];
        long start = System.nanoTime();
        ParalleManager manager = new ParalleManager();
        try {
            manager.start(Arrays.asList(numbers));
        } catch (ArithmeticException ex) {
           System.out.print( ex.toString() );
        } catch (InterruptedException ex) {
            System.out.print( ex.toString() );
        }
        long end = System.nanoTime();
        System.out.println("実行にかかった時間は " +
                (end - start) + "ナノ秒です。");
    }
}


//並列的にFizzBuzz用の出力文字を用意するオブジェクト
public class ParalleManager {
    //フィールド
    static int coefficient = 20;
    int threadCount;

    //コンストラクタ
    public ParalleManager() {
        //作成するスレッド数を算出
        Runtime env = Runtime.getRuntime();
        int cpuCount = env.availableProcessors();
        this.threadCount = cpuCount * coefficient;
    }

    //複数のスレッドを使用して並列的にFizzBuzz用の文字を用意する
    
    public void start( List target )
            throws ArithmeticException, InterruptedException
    {
        //エラーチェック
        if (target.size() < this.threadCount )
            throw new ArithmeticException(
                "対象の要素数が少ないので並列的に実行出来ません。");
        //各種変数を準備
        int number = target.size() / this.threadCount;
        int startIndex = 0;
        int endIndex = 0;
        ExecutorService ex =
               Executors.newFixedThreadPool(this.threadCount + 1 );
        //同じ数の仕事をスレッドに割り振る
        for ( int i = 0; i < this.threadCount; i++ ) {
            endIndex = startIndex + number;
            ex.execute( 
                new FizzBuzzThread( startIndex, endIndex, target ) );
            startIndex = endIndex;
        }
        //剰余な範囲に対応
        if ( endIndex != target.size()  ) {
            ex.execute( new FizzBuzzThread(
                    endIndex, target.size(), target ) );
        }
        //スレッドが完了するのを待つ
        ex.shutdown();
    }
}


//FizzBuzz専用のスレッドオブジェクト
public class FizzBuzzThread extends Thread {
    //フィールド
    private int startIndex;
    private int endIndex;
    private List target;

    //コンストラクタ
    public FizzBuzzThread( int start, int end, List strs ) {
        this.startIndex = start;
        this.endIndex = end;
        this.target = strs;
    }

    //FizzBuzzのルールに従って数値を文字列に変換する
    public void run() {
        StringBuilder str = new StringBuilder();
        for( int i = startIndex; i < endIndex; i++ ) {
            int flag = 1;
            int flag1 = 1;
            int number = i + 1;
            if ( ( flag  = number % 3 ) == 0 )
                this.target.set( i, "Fizz" );
            if ( ( flag1 = number % 5 ) == 0 )
                this.target.set( i,
                        flag == 0 ? "Fizz Buzz" : "Buzz" );
            if ( flag != 0 && flag1 != 0 )
               this.target.set( i,
                       ( ( Integer ) number ).toString() );
        }
    }
}
※20分ぐらいで作ったものだから動作保証はしないで注意。

この2つのプログラムを実行すると・・・
直列アルゴリズム= 580275249ナノ秒(数回のうち悪い値を使用)
並列アルゴリズム= 10668348ナノ秒(数回のうち良い値を使用)
なんと処理効率52.4倍!
嘘っぽい数字ですね。多分ちゃんと測定できていないのだと思います(笑)
もしくは処理が間違っているかも(笑)
別窓 | ネタ | コメント:4 | トラックバック:0 | ∧top | under∨
| 無差別に技術をついばむ鳥 | ネタつつき51−分散並列処理についての考察。>>

この記事のコメント

質問があります。

直列処理

1. 直列アルゴリズム、直列処理とはそもそもどのようなものを言うのでしょうか?
2. countにfinalを付けないのは何か深い理由があるのでしょうか?
3. Listに型パラメータを指定しないのは何故でしょうか?
4. Listを使う理由として、柔軟にしたかったとありますが、具体的にどこが柔軟になるのでしょうか?
5. numbersは初期化後使っていないので、Arrays.asList(new String[count])の方がいいのではないでしょうか?
6. flagやflag1という名前の変数名を使っているのは何故でしょうか?
7. if-else if-elseを使わないのは何故でしょうか?
8. List.setを使っているせいで、ランダムアクセス出来ないListでの効率が悪いように思いますが、そんなことはないのでしょうか?
9. 用意した文字列を画面に出すと時間がかかるとありますが、計測後に先頭100要素だけ出力、という方法を取らなかったのは何故ですか?

並列処理

1. 一回でも動作の確認を取りましたか?

それと最後に、処理効率の話ですが、52.4倍とあります。
インドリさんの使っているPCは、64コアマシンでも使っているのでしょうか?
とてもうらやましく思います。
2009-10-17 Sat 21:28 | URL | zozo #u2mjjqPU[ 内容変更]
> 質問があります。
>
> 直列処理
>
> 1. 直列アルゴリズム、直列処理とはそもそもどのようなものを言うのでしょうか?
単一プロセッサを前提とした従来のアルゴリズムや処理の事です。

> 2. countにfinalを付けないのは何か深い理由があるのでしょうか?
ありません。
これは、問題を見てすぐ見て思いついた事を戯れで実装したものです。
なんせ、お昼休憩の20分間で作ったものですから。

> 3. Listに型パラメータを指定しないのは何故でしょうか?
いい加減に作っているからです。

> 4. Listを使う理由として、柔軟にしたかったとありますが、具体的にどこが柔軟になるのでしょうか?
インタフェースを扱う事によりコンテナが変更しやすくなります。

> 5. numbersは初期化後使っていないので、Arrays.asList(new String[count])の方がいいのではないでしょうか?
そうかもね。

> 6. flagやflag1という名前の変数名を使っているのは何故でしょうか?
理由なんてありません。
戯れに実装したものですから・・・

> 7. if-else if-elseを使わないのは何故でしょうか?
好みの問題です。

> 8. List.setを使っているせいで、ランダムアクセス出来ないListでの効率が悪いように思いますが、そんなことはないのでしょうか?
ランダムアクセスする必要性がありません。

> 9. 用意した文字列を画面に出すと時間がかかるとありますが、計測後に先頭100要素だけ出力、という方法を取らなかったのは何故ですか?
そんな事をせずともデバッガで見れば済む話だからです。


> 並列処理
>
> 1. 一回でも動作の確認を取りましたか?
>
ひとまずデバッガで止めて適切な文字列がセットされているのを見ました。

> それと最後に、処理効率の話ですが、52.4倍とあります。
> インドリさんの使っているPCは、64コアマシンでも使っているのでしょうか?
> とてもうらやましく思います。
2コアですが、何故か52倍と出ています。
予想では1.6倍ぐらいだったので、52倍が出た時はびっくりしました。
そして、大受けしました。
それで、この記事を書いたのです。
それがこの記事の主旨です。
この記事を一言で言うと「52倍なんてありえねー」です。
2009-10-17 Sat 22:51 | URL | インドリ #-[ 内容変更]
お手元の最新版とブログ上のコードが違っていませんか?
startIndex と endIndex が初期値 0 のままでされないため、
これだと 0 から 0 の範囲のFizzBuzzスレッドを
多数生成し、最後剰余とコメントがついているスレッドで
0 から 2000000 の範囲を計算することになってしまいます。
2009-10-18 Sun 12:26 | URL | 通りすがり #-[ 内容変更]
> お手元の最新版とブログ上のコードが違っていませんか?
> startIndex と endIndex が初期値 0 のままでされないため、
> これだと 0 から 0 の範囲のFizzBuzzスレッドを
> 多数生成し、最後剰余とコメントがついているスレッドで
> 0 から 2000000 の範囲を計算することになってしまいます。

あれ?確かにUPしているプログラム足りませんね(笑)
有難う。追加しておきます。
2009-10-18 Sun 15:40 | URL | インドリ #-[ 内容変更]
∧top | under∨

コメントの投稿

 

管理者だけに閲覧
 

この記事のトラックバック

∧top | under∨
| 無差別に技術をついばむ鳥 |