kazurof weblog

技術ネタのメモを並べます

POH lite をfor文無しでやってみた。

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」|paizaオンラインハッカソンLite について、for文の代わりにStreamを使ってやってみました。 前々回の焼き直しです。 POH lite 天才火消しエンジニア霧島をやってみた。 - kazurof weblog

プログラム

sample code for https://paiza.jp/poh/kirishima

実行結果

kazurofさんの採点結果[100点] 完璧ぃぃ!|paizaオンラインハッカソンLite

実行時間は 0.22 秒から0.36 秒の範囲です。前々回より遅くなっています。 stream導入だけでなく、クラスを増やしたのも原因かもしれません。

stream導入について簡単なコメント

一番簡単なのは、75行目かと。0から配列の長さまで NOT_ASSIGNED を代入するだけです。

35行目は以前はtry節のループを内の処理でした。company.membersの総和を取る処理なのでこれだけを抜出してstreamで処理しました。

31行目は元々の IntStream を、List へと変換するような処理です。mapToObj を使います。(このメソッドを見つけ出すのに時間がかかった。とほほ。) 変数 i が、未使用であると、NetBeansに警告出されているのですが、解消の仕方がわかりません。(とほほ2)これは追々調べるとして。

40行目から50行目は、mapとforEachとありますが、一緒にしてしまっても良いのでは?とも思っています。(この修正はNetBeansが提示してきた。)小さい処理に分割するのが良いことなのかもしれません。

この中の41行目でもstreamを使っています。IntStream を降順にするため、map(i -> numOfMemberIfUseAll - i + company.members - 1) などと小細工しています。標準機能にないかな。

105行目はnumOfMember以降での -1 以外の最小値を取る処理です。修正前はfor文の外のローカル変数に代入する処理でしたが、min()メソッドで streamから直接算出するようになりました。以前よりも処理が簡素になったと思います。

まとめ

for文をstreamに入れ替えて、全体的にソースが簡素になったような気がします。配列を処理するケースが多かったので、 IntStream s = IntStream.range(start , end); の、パラメータの与え方がキモだった感じです。 stream は慣れというか初期学習コストが必要なのは否めませんが、できるようになったらコードが綺麗に書けるかもです。普及が進めば否応なしに読み書きせざるを得なくなるでしょう。 速度については、paizaの範囲では期待できないかも知れません。

(ネタ)火村氏についての考察

https://paiza.jp/poh/kirishima

ここの、火村氏のコードがヘボいのは言うまでもないと思います。

が、彼が書いたJavaのコードでは java.io.BufferedReaderではなく、java.util.Scannerが使われててこれは意外とすごい?ような気がしました。 

火村氏は42歳。java.util.ScannerはJDK5で登場してて、リリース日は 2004年9月30日 概ね10年前。 彼は32歳。確か、Java 1.4 とJDK5の差は大きく、実環境投入がスムーズにやれたかとは限らないと思います。コンテナが対応してないとか。

それでも java.io.BufferedReader よりも java.util.Scannerを使うほうが書きやすいとわかってるからこそ書いたはずで、その点は火村氏は(少なくともその頃は)ちゃんとキャッチアップしてたんだなと思われるわけです。

他にも、いろいろな言語でサンプルコードを書けていて(ヘボいですが)、ゼネラリストっぽいなーという感じです。COBOL VB Objective-Cを知らないのは、オンラインハッカソンとしての都合でしょうね。きっと。

色々書きましたが、値出力のサンプルコードhttp://paiza.jp/guide/samplecode よりも新しいAPIで、火村氏にコードを書かせた運営さんの意図が気になります。何かの演出上の意図があった?特に何もなくて僕が勝手に深読みしすぎているだけ?

そういうのがもうちょっと整理してあったらもっと楽しく遊べたかもしれません。 私からは以上です。

POH lite 天才火消しエンジニア霧島をやってみた。

https://paiza.jp/poh/kirishima をやってみました。

自分の理解のため、解法の説明をしながらコードを晒します。

アルゴリズム概要

簡単に言えば、ナップサック問題の変形を動的計画法で解くアルゴリズムです。

処理を進めるにあたり、下請け会社の組み合わせで取りうる合計人数とその場合の合計コストを算出します。 その情報を costByNumOfMember なる配列(ソース10行目)に保存します。 配列添字が合計人数です。値がコストです。

そして、それぞれの下請け会社毎にこの配列の情報を更新します。 つまり、ある下請け会社についてこれを使ったほうが安くなるような組み合わせ(=合計人数)があるならば その下請け会社で更新します。

すべての下請け会社をチェックした後、必要な人数以上の範囲でコストの最小値を求めます。 それが本問の回答です。

プログラム

gist4865fa5ab62c8aae09af

プログラムの解説

30行目から38行目は入力データの読み込みです。 同時に全ての会社を選択した場合の人数も足し上げて保存しています。

40行目から43行目は costByNumOfMember の生成と初期化です。 合計人数は1始まりなので、この配列もそのように使うべく長さを +1 しています。 添字0番目は使っていません。

45行目は、会社のリストでループを回します。 この内部は会社ごとの処理です。

46行目のループは、costByNumOfMemberについて特定した会社を考慮する時の処理です。 配列costByNumOfMemberのそれぞれの要素(=取りうる人数とコスト)について、 特定した会社(変数名 company)を含めた組み合わせのほうがコストが安い場合これを更新します。

ループについて、開始は「全ての会社を選択した場合の人数」です。 終了は「特定した会社の人数」です。大きい方から小さい方へ処理している理由は後述します。 ループ変数は i です。

このループ内部では、costByNumOfMember[i] を特定した会社の情報で更新できるならしたいです。 どうやってやりましょうか?どんな条件で?どんな値で?

実は、costByNumOfMember[i]を更新してよいかの判定には、 costByNumOfMember[i - company.members]を検査することが必要になります。

もしも、costByNumOfMember[i - company.members]に何らかの値が設定されていたら、 そのような下請け会社の組み合わせが存在することになります。 この値にcompanyを加味して新たな組み合わせを検討してみましょう。

0 < costByNumOfMember[i - company.members] であるならば、以前のループの処理で 組み合わせとコストが確定していた事になります。 この値と company.cost の和は costByNumOfMember[i]の候補になります。

未設定ならば新規に値を設定するべきです、 未設定でなくても現在のcostByNumOfMember[i]よりも少ないならばやはり更新するべきです。 新たな組み合わせがあり得てしかも安いということですから。 この処理は、updateCostByNumOfMemberメソッドに切り出してあります。

ループを大きい方から小さい方へ処理している理由は、costByNumOfMember[i - company.members] の値をもって costByNumOfMember[i]を更新しているからです。若い方の値から古い方を更新しています。 もしループを小さい方へ大きい方へ回したら、同じ company で以前処理した costByNumOfMember[i - company.members]の 値をもって、costByNumOfMember[i]を更新することになります。companyを2重に評価することになります。

また、内部のループでの処理に加え、companyだけを選択した場合についても 考慮する必要があります。同様に updateCostByNumOfMemberを実行する。(53行目の処理)

56行目からの処理は requiedNumOfMember 以上の範囲で一番安いコストを検索する処理です。 端から走査するだけですね。

取得した結果を表示して終わりです。

実行結果

http://paiza.jp/poh/kirishima/result/2bbd184057c0ee7da43c9d0f4384eb9c

100 点はとれてますが実行時間は 0.11 秒から0.18 秒の範囲です。 当然ながら最速のコードよりは大きく離れていますね。 

その他雑駁な話

言い訳

このコードはしえるさんのコードをコピペして、自分がわかりやすいように 直して(でもアルゴリズムの本質は変えていない)記事にしているものです。 http://qiita.com/cielavenir/items/d07e62d1dc61c2915003

他人の褌で相撲を取っているようなもので、申し訳ありません。 しえるさん。もしこの記事に問題ありましたらどうぞお知らせください。 削除する準備はいつでも出来ています。

感想など

競技プログラミングということを考えたら、しえるさんが書いたような方向になるべきでしょうね。

実行速度が全てに優先する。余計なことはしない。それが標準APIであったとしても。 使いまわせる変数は使いまわす。読みやすさ、アルゴリズムのわかりやすさは目指さない。

ですので競技プログラミングの目指すところはいわゆるシステム開発とは異なるものであるなと。

ただ、アルゴリズムがわからないのではコードに責任が持てないので、 勉強よろしく書き直しながらやってみました。下請け会社の組み合わせについての情報は全く捨てるというのが ちょっと新鮮でした。学部の頃やっていたような気もするのですが、思い出しながらということで。

さらなる修正について。

costByNumOfMember は今のところ int[] ですが、 これをクラスにする方向もあって良いかなと思いました。今回のプログラムはcostByNumOfMemberに対する処理が そこかしこに散在しています。mainメソッドの一部として置くよりもオブジェクト指向プログラミング的には そのほうが適切かもしれません。もっとプログラムが大規模になって処理の散在具合が大きくなったら 実施すべきかと思います。

変数名の長さ加減でいかにもおっさんが書きそうなJavaコードっぽさが演出されたかもしれません。 今のデザインでは横幅制限が厳しいので次回できれば改善したいと思います。

oracleのjavacとEclipseのJavaコンパイラの挙動の相違点

結論

アノテーションの要素を変数で設定するときの変数(あるいはフィールド)名と、メソッドのパラメータ名は別のものにしましょう。

以下のコードはEclipseではコンパイル・実行ともに可能。

gistb407368a712f4006ecea

しかし、javacコンパイラではエラーになる。 *1

Java7の場合

>javac -version ECJProblem.java  
javac 1.7.0_55    
ECJProblem.java:7: エラー: 属性の値は定数である必要があります  
  public String doSomething(@TestAnnotation(nantoka) String nantoka) {  
                                            ^
エラー1個

Java8の場合

>javac -version ECJProblem.java
javac 1.8.0
ECJProblem.java:7: エラー: 要素値は定数式である必要があります
  public String doSomething(@TestAnnotation(nantoka) String nantoka) {
                                            ^
エラー1個

原因(と思われるもの)

doSomethingメソッドにおいて、要素値をフィールドnantokaを使って設定しようとしていますが、 同時にメソッドパラメータにも同じ名前が使われています。 Eclipseの場合、要素値への設定はクラスのフィールドからされているとみなされるようですが、 javacの場合、メソッドパラメータからなされているとみなされるようです。

この違いで問題になる(と思われる)パターン

いつもEclipseを使ってビルドしていたが、緊急にエラーを直さなくてはならない。いつもの手順でEclipseでシステム全体をビルドするのではなくjavacコマンドで必要なファイルをコンパイルしてclassファイルだけ差し替えたい。しかし実際にそれを行うと、本現象にてjavacではコンパイルできないのでシステムの修正ができない。

予防的にとれる対策

アノテーションの要素値に設定する変数名とメソッドのパラメータ名は別にしましょう。

検証した環境など

  • Eclipse Version: Kepler Service Release 2 Build id: 20140224-0627
  • Windows7
  • Java7 Java8

*1:Java7とJava8でエラーメッセージ文言が微妙に異なるのでググられることを意図して両方載せてみる。

ヒカルのgo (hikarie.go) に行ってきました。

Javaばっかりというのもどうかと思い、やるなら新し目の言語を見てみようかと思って行ってきました。ハローワールドすら読んだことはありません。

ヒカルのgo (hikarie.go) http://connpass.com/event/6579/

主催者さんによれば、質実go研 Go研 - connpass よりも低く、A Tour of Goよりも上ぐらいの初中級者向けにやりたいとのことです。

雑駁な感想

A Tour of Go という動かせるチュートリアルがある。(72ページ!) http://go-tour-jp.appspot.com/

CUIについての発表が多い。というかGUIをどうこうするようなことは無いみたい。(今後は違う?) プラットフォームに依存しないGUIは鬼門といえば鬼門だからだろうけど。

定番のライブラリというものがない。いろんな人がいろんなライブラリ書いてる。 まあこれはrebuild.fmでも言われてたような。

個人的に渋いと思ったLT http://www.slideshare.net/takuyaueda967/gopher5

そもそもgoを何に使うか、という観点では決定打はない感じなのかな? エンジニアが言語の進化を試験するということぐらいは意味があるかもしれない。 プラットフォームをiOSOS Xに絞ったSwiftとは違うかも。 Googleの人はこれを何に使って欲しかったのかな?勉強しているエンジニア、新しいことを追求している・ついてこれるエンジニアの洗い出し、というのも目的の一つなのかもしれない。ところで懇親会のごちそうはたくさん出た。(毎回は続かないだろうけど) そういう意味でもDeNAはGoに投資しているって私の中で勝手に想像が湧いた。

次回は7月にあるそうです。Goに興味ある人は行って損なしでは。

JJUG ナイトセミナー 「6.11 ドメイン駆動設計特集!」に行ってきました。

ドメイン駆動設計と言うのはなんとなく聞いたことがあったかな?という程度の認識でした。実際上は予備知識ゼロです。 けれどなんとなく興味がわいたので行ってきました。この記事は、大嘘・勘違いあると思います。ご容赦を。

【東京】JJUG ナイトセミナー 「6.11 ドメイン駆動設計特集! 」 - 日本Javaユーザーグループ | Doorkeeper

簡単な感想

「お客さんの業務の把握して、客でもエンジニアでも理解を共有できるようにして、開発を進めましょう」ということであるとなんとなく理解しました。元の本が2004年出版ということで、新しいようで古くもあるテーマなのだなと。単なるウォーターフォール型でもなくイテレーティブに行きましょうというのが少し新し目な感じでしょうか。

こういうのはSIerがやる業務アプリの受託開発という要素が多くて地味といえば地味かもしれません。けれどプロジェクトを進める上での根幹に関わる物事ということですね。

加藤さんの話からは、DDDは素晴らしく良いものであるという印象は受けなかったけど部分部分使えるところをつまむ工夫があれば格好がつくかもしれませんね。実プロジェクトへ適用する上での工夫とか取捨選択とか。プロジェクトの進め方とか意思決定は判断間違えた時のリスクを考えると怖いものでもあるけど、何らかでも背景となる根拠や知識があれば自信がつくかも。

twitterのタイムラインからはすぐ読めそうな文書へのリンクが見えたので、概要ぐらいは知っておいても損はないかもしれません。後で読んでみよう。 Domain Driven Design(ドメイン駆動設計) Quickly 日本語版

個人的にはコーバーンさんのユースケース分類について言及されてたのがちょっと嬉しかった。あれってまだobsoleteではなかったのですね。思い入れがあるものなので、よかったよかった。

自分向けメモ - よく使うmavenコマンドについて

mvn package

そのプロジェクトでの成果物を生成する。jarとかwarとか。これでwarを作ってtomcatなどにデプロイするという流れ。

mvn versions:display-dependency-updates

利用可能な最新ライブラリの調査。現在pom.xmlに登録されている依存関係を全部調べてより新しい版が公開されていたらそれを教えてくれる。僕はやってないけど、cronか何かに仕込んでおいて、Struts2の新しいバージョンを検知するのにも良いかもしれない。

mvn dependency:copy-dependencies

依存するjarファイルを/target/dependencyに出力。例えば「現在のプロジェクトは、mavenを使っていない。けれどmavenの依存関係管理の機能は使いたい。」ということもあろうかと思います。

そういう場合とりあえず、pom.xmlだけ作ってしまってこのコマンドを叩くと必要なjarファイルをすべて出力してくれます。出力されたjarファイルを手動で /WEB-INF/lib などにコピーして使うのです。今は無理だがいつかプロジェクトをmavenizeしたい時に重宝します。

コマンド例

providedスコープのjar(servlet-api.jarなど)を除外して出力する。

mvn dependency:copy-dependencies -DexcludeScope=provided

mvn dependency:tree

依存関係ツリーをコンソール上でグラフィカルに表示する。 なんとなく依存関係ツリーを把握するのに便利です。でもこの用途なら Eclipseで見たほうが良いかもしれません。