天才プログラマーと自分との実力差をカンタンに測定する方法
天才プログラマーと自分との実力差をカンタンに測定する方法を発見しましたよ、という話。
結論から言うと、いろんなところで過去に開催されたプログラミングコンテストの入賞者の結果を見て、その問題を同じ条件で解いてみること。
あるウェブサイトに２０１５年に開催されたプログラミング・コンテストの結果が載っていた。（本記事の末尾にそのプログラミング問題の日本語訳を載せた）
入賞者は１位の人が１５分、２位が２２分、３位が２４分、となっていた。
プログラミングの問題をザッと眺めていたら、実装すべきアルゴリズムがパッと思いついた。「これはひょっとして１位の人は超えられなくても３位入賞ぐらいはいけそうじゃね？」などと考えてしまった。
それでそのウェブサイトが用意しているエディタを使って、コードを書きだした。
１５分経過：「あれ？もう１５分も経った？まー１位にはなれなくてもトップ集団には入るわ」
２０分経過：「うーん。もう２０分か。３位内にはなれなくてもまだまだトップ集団には入れる。。。はず」
３０分経過：最初に考えたアルゴリズムに欠陥があることを発見する。
４０分経過：「なんか最初の目論見とはかなり違う。。。これ完成するのか？」
１時間経過：「それなりのはできたしもう提出してまえ！なんかイヤになってきた」と、自暴自棄気味にウェブサイトのSubmitボタンを押すとB判定が出た。
B判定の理由は一般的なケースでは正しい答えが返ってくるが、特殊なケースにおいては対応できていないのと、計算量にまだ改良の余地があるとのこと。
ヘコんだ。
１時間かけてB判定の私と１５分で完璧にスキが無く、計算量が最小限で済むコードを実装した人との差は歴然だった。
問題を読んだだけでは分からなかったが、実際に手を動かしてコードを書いた後では１位の人がどれほどすごいかが分かった。たった１５分で完璧に実装してしまうのは天才的。この問題を読んでパッと思いついただけの解法にはきっとヌケがある。そこをしっかり埋めるのが難しい。誰でも時間をかければできる。しかし１５分というのはもう天才の技としか言いようがない。
天才プログラマーとの実力差を見せつけられて、実はかなりヘコんだ。それでもこれは挑戦してとても良かったと考えている。
その世界でトップクラスの人と自分との差を把握することは、どんな職業においても重要だと思う。
例えばサッカー選手の場合、その選手がどこのリーグのどんなレベルの選手であったとしても世界最高峰との差異が把握できている選手とできていない選手とではその後の成長性が変わってくる。メッシやC・ロナウドらと対戦した経験があって、ハッキリとそれらの最高峰の選手と自分がどう違うのかを分かっている選手なら、その差異を意識して自分なりの方向性を考え、日々のトレーニングを積むことができる。
ただサッカー選手はその職業から世界最高峰との差を把握するにはやはりバルセロナやイギリスのリーグのチームに入って、真剣試合で対戦する必要がある。サッカー選手の真の実力なんてテレビで眺めているだけとか、たとえ対戦しても親善試合ではきっと分からないからだ。
それに引き換えソフトウェアエンジニアやプログラマーにとってはトップとの実力差の測定はとてもカンタン。ただプログラミングコンテストのページを開けて、その問題をやってみればいいだけ。トップクラスの人がやっていることと条件はほとんど変わらない。
しかもその差異はかなりの精度で数値化もしくはO記法などで数式化される。
こんなカンタンに世界のトップクラスとの差異が測定できる職業ってあまり無いのじゃないだろうか。
ということでご興味があればやってみてはいかがでしょうか？
私がやってみたのはこのサイトのコンテスト。
Argon 2015 challenge - Codility
プログラミング言語は以下の１６言語に対応しており、なにかのプログラミング知識を持つ人なら誰でも参加できるようになっている。
C、C++、C#、Go、Java、JavaScript、Lua、Objective-C、Pascal、PHP、Perl、Python、Ruby、Scala、Swift、VB.NET
一応、私なりの日本語訳をここに掲載した。「我こそは１５分以内に解いて１位以上の成績を叩きだしてやるぜ！」とお考えの方はぜひ挑戦して、見事に成功したら教えていただきたい。こんな問題を１５分足らずで解いてしまう人は一体どんな人なのか本当に興味がある。
Argon 2015 プログラミングコンテスト問題
あなたは次の休暇をポーランドで過ごそうと考えています。ポーランドは大国とは言えないかもしれませんが、北のバルト海から南のタトラ山脈まで様々な自然を楽しむことができる国です。海で泳いだり、山で山登りを楽しむことができます。ところがポーランドの気候はとても変化が激しく、休暇を過ごすにはその天候を考慮に入れる必要があります。
あなたの今年の夏の休暇は連続したN日分があります。あなたはそのN日分の中でどこからでも休暇を始めることができて、N日内のどこでも休暇を終えることができます。あなたの休暇の前半は海で、後半は山で過ごすことにします。山と海の休暇期間は正の整数とし、あなたは休暇期間を最大化したいと計画しています。
あなたにはN日分の天気予報があります。奇妙なことにその天気予報によると海に行くのにパーフェクトな日は山に行くには不可能な日になっています。逆も同じ。山にとって絶好の天気の日は、海では遊べません。当然ながらあなたの計画は海や山での休暇先を最良な天気の下で過ごしたいと考えています。したがって休暇の前半（海で過ごす休暇）の半分以上の日程は海で泳ぐのに適した天候で、後半（山で過ごす休暇）の半分以上の日程は登山に適した天候にしてください。
天気予報は０からはじまる配列Aで示されます。K (0 ≤ K < N), A[K]が０の時、それはK日目の天候が海に適した天候であることを示します。A[K]が１の時はK日目が登山の天候です。
次のメソッドを書いてください。
Rubyの場合: def solution(A)
Javaの場合: class Solution { public int solution(int[] A); }
JavaScriptの場合: function solution(A);
Objective-Cの場合: int solution(NSMutableArray *A);
Pythonの場合: def solution(A)
このメソッドに配列Aとして天気予報を入れると、あなたが取れる休暇の最大日数が返ってくるようにしてください。
例えば配列Aが以下のような場合。
A[0] = 1
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 0
A[5] = 0
A[6] = 1
A[7] = 1
あなたは８日の休暇があります。２日目、４日目、５日目が海に適した天気。その他が山になります。あなたは１日目（A[1]）から休暇をスタートし、５日間を海で過ごします。A[2], A[4], A[5] の３日間が海に適した日になるので「半分以上の日程」という条件に合います。その後の２日間を山で過ごします。２日とも山に適した天候になります。すなわち７日間が上記の天候条件下で最大の休暇日数になります。したがって７を返します。
例えば配列Aが以下のような場合。
A[0] = 1
A[1] = 0
あなたは上記の条件に合う休暇を取ることができません。したがって０を返します。
計算量はO(n)となるようにしてください。
１時間かけて書いたコードがB判定を食らった後、「CODE COMPLETE」を読み返した。人間は決まった特定の人の輪の中だけを見ていると「オレってコード書くことに関してはまーまーイケてんじゃね？」などと考えてしまいがち。このプログラミングコンテストの試し参加はそういう傲慢な姿勢を正し、基礎に戻ってしっかり勉強することを気付かせてくれた。
オススメです。機会があればぜひ。
あとGoogle codejamとやらが有名らしい。
Google Code Jam
＜追記＞
コメントで「１５分がトップとかレベルが低いな」とかいただいて、「えええ？？？」となった。しかしいろいろ調べると競技プログラマーなる人達が居る、と。chokudaiさんという方がなぜそんなに速く問題が解けるのか、のタネあかしをこちらの動画で解説されている。なるほど。知らなかった。
ワンランク上に行くプロコン講座 - YouTube
CODE COMPLETE 第2版 上 完全なプログラミングを目指して
- 作者: スティーブマコネル,Steve McConnell,クイープ
- 出版社/メーカー: 日経BP社
- 発売日: 2005/03/26
- メディア: 単行本
- 購入: 44人 クリック: 1,166回
- この商品を含むブログ (288件) を見る
オブジェクト指向設計実践ガイド 「Practical Object-Oriented Design in Ruby」待望の日本語版がついに発売
本ブログで絶賛オススメしていた 「Practical Object-Oriented Design in Ruby」の日本語版がついに発売された。
こちらの記事でオススメを書いたのだが、アクセスはたくさんあってもアマゾンのアソシエイトプログラムを通して購入にいたるケースは少なかった。
tango-ruby.hatenablog.com
英語の本になるので、その内容に気になっていた方でも「英語はイヤだな」と保留されていたように思う。しかしついに日本語版が発売された。
英語版が刊行されたのが2012年で日本語版がその４年後ってIT系の技術本としては英語版と翻訳版の発刊時期のズレがやけに大きいと感じる。本書は最新の技術紹介とかではなく、オブジェクト思考を深く解説しているのでオススメ記事に「おそらく５年後もこの本は読まれ続けている」と書いた。それにしても４年も経過してから、翻訳本が出るってのはいかに内容が普遍的で、本書の発売に自信があったことがうかがい知れる。並の本だったら４年も経ってから翻訳版なんてきっと出さない。瞬間的な流行りみたいにパッと売れるのではなく、ジワーっと長期間売れ続ける本になる予感がする。
私はさすがに何度も読み込んでキンドル版と紙の本と２つも買ったので、もう日本語版まで購入する予定はないが、英語本の内容がとても良かったので日本語版もオススメです。
オブジェクト指向設計実践ガイド ~Rubyでわかる 進化しつづける柔軟なアプリケーションの育て方
- 作者: Sandi Metz,?山泰基
- 出版社/メーカー: 技術評論社
- 発売日: 2016/09/02
- メディア: 大型本
- この商品を含むブログを見る
Practical Object-Oriented Design in Ruby: An Agile Primer (Addison-Wesley Professional Ruby)
- 作者: Sandi Metz
- 出版社/メーカー: Addison-Wesley Professional
- 発売日: 2012/09/05
- メディア: Kindle版
- この商品を含むブログを見る
翻訳された方のブログと紹介記事。「日本語版があったらいいのになー」とブログに一言書くのはカンタン。でもその本を翻訳して出版するのはとても大変なこと。ご苦労様です。価値のあるお仕事を達成されたと思っております。
tech.misoca.jp
RubyのEnumeratorとEnumerator::怠惰(Lazy)の使い所とベンチマーク
RubyのEnumeratorとEnumerator::Lazyの使い所とベンチマークをまとめた。使うと意外と便利なのがEnumerator。
Enumeratorの基礎動作
irbを起動して配列のeachの後にブロックを渡さないでおくと、それはそのままEnumeratorオブジェクトにして返される。
~ $ irb irb(main):001:0> e = [1,2,3].each => #<Enumerator: [1, 2, 3]:each>
Enumeratorにnextとやれば、順番に中の要素を出す。便利。
irb(main):002:0> e.next => 1 irb(main):003:0> e.next => 2 irb(main):004:0> e.next => 3
念のために言っておくとArrayにnextはない。
irb(main):001:0> array = [1,2,3] => [1, 2, 3] irb(main):002:0> array.next NoMethodError: undefined method `next' for [1, 2, 3]:Array
[1,2,3]と３つしかないEnumeratorで最後まで来てさらにnextすると、こうなる。
irb(main):005:0> e.next
StopIteration: iteration reached an end
from (irb):5:in `next'
from (irb):5
from /.rbenv/versions/2.3.1/bin/irb:11:in `<main>'
その際にはrewindとすればまた最初に戻せる。
irb(main):006:0> e.rewind
=> #<Enumerator: [1, 2, 3]:each>
irb(main):007:0> loop { puts e.next }
1
2
3
=> [1, 2, 3]
e = [1,2,3].eachとして作ったEnumeratorは to_enum でもEnumerator.newでも作成可能。
irb(main):008:0> e = [1,2,3].to_enum => #<Enumerator: [1, 2, 3]:each> irb(main):009:0> e.next => 1 irb(main):010:0> e.next => 2 irb(main):011:0> e.next => 3 irb(main):013:0> e = Enumerator.new([1,2,3], :each) (irb):13: warning: Enumerator.new without a block is deprecated; use Object#to_enum => #<Enumerator: [1, 2, 3]:each> irb(main):014:0> e.next => 1 irb(main):015:0> e.next => 2 irb(main):016:0> e.next => 3
peekで中をのぞける。
irb(main):020:0> e.peek => 1 irb(main):021:0> e.peek => 1 irb(main):022:0> e.next => 1 irb(main):023:0> e.peek => 2 irb(main):024:0> e.peek => 2 irb(main):025:0> e.next => 2 irb(main):026:0> e.next => 3
each.with_indexのEnumeratorを作ればindex が入る。
irb(main):027:0> e = %w{this is a test}.each.with_index
=> #<Enumerator: #<Enumerator: ["this", "is", "a", "test"]:each>:with_index>
irb(main):028:0> e.next
=> ["this", 0]
irb(main):029:0> e.next
=> ["is", 1]
irb(main):030:0> e.next
=> ["a", 2]
irb(main):031:0> e.next
=> ["test", 3]
Enumerator::Lazyの基礎動作
Enumeratorとの違いは必要になってから準備しますよ、という怠惰な方法。
例えば１から果てしなくデカい数字までの範囲をinfinite_rangeとして、そのEnumeratorを作る。
irb(main):032:0> infinite_range = (1..Float::INFINITY) => 1..Infinity irb(main):033:0> e = infinite_range.each => #<Enumerator: 1..Infinity:each> irb(main):034:0> e.next => 1 irb(main):035:0> e.next => 2 irb(main):036:0> e.next => 3
もしこの果てしなく続く範囲の数字の中から３と５で割り切れる数を取り出す、となると果てしなくある数字から取り出すのでずっと終わらず、強制終了しないと止まらない。
irb(main):038:0> infinite_range.select {|n| n % 3 == 0 && n % 5 ==0 }
^X^CIRB::Abort: abort then interrupt!
from (irb):38:in `block in irb_binding'
from (irb):38:in `each'
from (irb):38:in `select'
from (irb):38
from .rbenv/versions/2.3.1/bin/irb:11:in `<main>'
Lazyを使うと、とりあえずEnumeratorの用意はするが、数字を出すのは必要になってからになる。なので無限ループには入らない。
irb(main):040:0> e = infinite_range.lazy.select {|n| n % 3 == 0 && n % 5 ==0 }
=> #<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:select>
irb(main):041:0> e.next
=> 15
irb(main):042:0> e.next
=> 30
irb(main):043:0> e.next
=> 45
irb(main):044:0> e.next
=> 60
irb(main):045:0> e.next
=> 75これは巨大なデータを扱う際にいっきにメモリーを確保しなくても動く。少ないメモリ消費量で巨大なデータを扱う際に使える技になる。
EnumeratorとEnumerator::Lazyのベンチマーク
1から10000000までの偶数だけ取り出して全部足す作業をする際のEnumeratorとEnumerator::Lazyの違いをとった。
ベンチマークのコード
require 'benchmark' Benchmark.bm(10) do |b| b.report "eager load" do (1..10000000).select {|n| n % 2 == 0 }.inject(:+) end b.report "lazy load" do (1..10000000).lazy.select {|n| n % 2 == 0 }.inject(:+) end end
ベンチマークの結果
user system total real eager load 1.310000 0.020000 1.330000 ( 1.348951) lazy load 2.060000 0.000000 2.060000 ( 2.070888)
lazyを使うと使う時になってからちょこちょことメモリを割り当てているので少し遅くなる。しかしメモリ領域をいっきに消費しないというメリットを考慮に入れれば、交換条件として悪くはない結果。
tango-ruby.hatenablog.com
