blogJCUnitの開発日誌(ログ)です。"その時点での"JCUnit作者の理解や考え、開発状況を日本語で書きます。この広告は、90日以上更新していないブログに表示しています。今回の話はレポートで組み合わせとか順列の列挙をするプログラムを作る課題をやってる学生さんには面白い話かもしれない。JCUnitは内部的にcombinatoradix(旧称enumerator)と呼ばれる私が作ったライブラリを使っている。github.comJCUnitは性質上、かなりヘビーに組み合わせや順列や直積の列挙を行う。そこで、専用の組み合わせ列挙の仕組みを持っている。誰かが作ったライブラリを利用してもいいのだがそうしなかった理由は2つある。そもそも外部への依存関係は最小にする必要がある。外部ライブラリを利用すると、そのライブラリ自体のテストにJCUnitが使えなくなるのはもとより、そのライブラリを使用した製品のテストの際にライブラリバージョンによる挙動の違いにより、テスト結果が変化する虞がある。組み合わせを列挙してくれるライブラリは多くあるが、その際に「どのような順番で列挙するか」が明確なものは見つけられなかった。あるかもしれないが、列挙される要素の集合にa.equals(b)になるような組があった場合の挙動がどうなるか?など不安が多い。JCUnitの場合、どんな順番で列挙がされるかは非常に重要で、これがないとテストの再現性が損なわれる。combinatoradixは、「階乗進数」という特殊な記数法を使って、順列の列挙を行う。5個の要素から3個を選んで並べるとき、そのやり方は5P3=60通りだ。この時、下からひと桁目は0-4(5進数)、二桁目は0-3(4進数)、三桁目は0-2(3進数)にすると0-234までで60通りの数を表現できる。234記号[A,B,C,D,E]から3個を取る順列をこの60個の数字に割り当てる。割り当て方だが、下から順に、その桁の数字に対応する要素を取りさってゆけば良い。(残り:[A,D])つまり[B,C,E]が対応する値となる。似た様な(しかしもう少し複雑な)記数法を考えると、組み合わせや重複を許す組み合わせについて同じことができる。この方法は数の計算と要素の対応付けを行うので、可能な組み合わせをすべて列挙するだけなら、再起やループを使ったほうがずっと早いはずだ。「AからZの文字のうち異なる10文字からなる単語を作り、それらを辞書順にならべたときに30億22番目にある単語はなにか?」という問に答えるのは1マイクロ秒くらいでできる。最初からじゅんじゅんにたどっていく必要がないので。この性質は大量の組み合わせを分散処理や並列処理で高速化して処理したい場合に有効なはずだ。10億通りの組み合わせがあることがわかっていて(100P3とか1000C4とか簡単に公式で求まる)それぞれについて何らかの処理を行いたいのなら、各ノードはその組み合わせの総数(100P3とか1000C4とか)までの数のうち、ノード数で割った余りが自分のノード番号に等しいものだけを処理すればよいのだ。偉そうに書いてしまったが、この方法を考えついたあとに誰かがすでにやってそうなもんだと思い調べてみてこういう名前が付いているの知った。1.7.0_79以前でコンパイルできない。1.7.0_80より古いjavacを使っている場合、JCUnit及びそれを...2016-03-14(第三回)JCUnitで2次方程式を解くプログラムをテストする。2017でJCUnitの発表をすることになりました。joinedプログラミングはてなブログをはじめよう!dakusuiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。