AtCoder Beginner Contest 123
4 問中 3 問解いて、1000 点中 600 点獲得した。
400 点の問題はコードを書ききるところまでは行ったが、一部の答えが合わずに残念ながら失点した。 開始前はとりあえず 3 問はとこうと思っていたので、まあ良しとしたい。 次回は全問解くのを目指そう
良かった点
- 前回よりは C++ の機能を使えてた
- 他の参加者のコードを参考にしたのが良かった
- とりあえずソートしてみたのは良かった
- 遅いかと思ったが、それでもテストケースは通った。
- ここらへんの感覚は掴んでおきたい
反省点:
- 簡単な部分でつまずきがある
- まだ C++ のソートを使いこなせてない
- なぜかセグメンテーションフォルトが起きたが、対処できずにタイムアップした
解答方法はわかっているが、まだコードに落とすのがぎこちない感じ。 とりあえず一通りのコードはかけたのでそこら辺は評価したい。
また他の参加者のコードを読んでおこう。
JJUGナイトセミナー GraalVM とその要素技術
2/27 に行われた 【東京】 JJUGナイトセミナー「JVM言語を作ろう! GraalVMで遊ぼう!」 - 日本Javaユーザーグループ/Japan Java User Group | Doorkeeper に参加してきた。
以下メモ。
JVM 言語の動き方・動かし方 by @miyakawa_taku
言語処理系の基礎知識の話。 JVM 言語の話としてまとまっているので良い資料になっている。
インタプリタの種類としては次が紹介されていた。
Meta-cricular インタプリタは名前を知らなかったが、AST などの木構造を再帰的に手繰って計算する方式らしい。 ホスト言語の制御構造を利用できると同時にその制約も受けてしまうとのこと。
Kink の紹介
引き続き自前の JVM 言語処理系の話。
Kink 言語の特徴としては:
- 継承なしのオブジェクトシステム
- trait 付きのプロトタイプベースのような感じ?
- 限定継続(限定=範囲付きの継続)
- Qcode というバイトコードを用意して JVM の上のインタプリタで実行
- GC は JVM のものを利用
性能は現状ではいまいちだが、次のような性能改善が考えられるとrのこと:
GraalVM で使われている、他言語をJVMに実装する仕組みを学ぼう by @jyukutyo
www.slideshare.net
GraalVM は Hostspot VM を基にしたもので、次のものから構成されている:
- Graal -- Jit コンパイラ
- Truffle -- 言語実装のフレームワーク
- JVM CI -- JVM compiler interface
- Substrate VM -- java AOIT のランタイムライブラリ
GraalVM でできることはたくさんあって、 すでに JavaScript,Ruby,R,LLVM,sulong は GraalVM で動かせるようになっている。 かつ R はかなり早くなっているらしい。
Truffle で言語実装入門 @kis
後半は Truffle の話。 Truffle は動的なプログラミング言語を作るライブラリで、AST のインタプリタ。 一度 AST ができれば、後は Graal と JVM に任せられ、ランタイムを構築する必要はない。
Truffleのメリット:
- 言語が高速に実行できる
- Truffle には Interoperability 相互呼び出しができる
- JavaScript から Ruby を「高速」に呼び出せる
- Chrome 上でデバッグができたり
Truffle での言語実装は次のように行う。
- Truffle の言語実装に必須のクラスを実装
parseSource()
で字句解析、構文解析を実装するなど
- 入出力の準備
- 要するに Truffle を呼び出す部分も作る
現状 Truffle を学ぶには、現状コードを読むしかない。 なかでは SimpleLanguage がおすすめ、というかそのための言語になっている。
Truffle + PHPぽい言語 by @kis
Truffle で php っぽい言語を作った話。
パーサは jparsec(https://github.com/jparsec/jparsec) を利用して、php の一部だけを実装している。
Truffle のコンセプトは「動的な値だけ受け取るインタプリタ」で静的な部分は前もって取り込んでおく。 Truffle がやることは Specialization
- 最適な評価方法を選んでくれる
- メソッド呼び出しの最適化
Truffle で書いた言語は書いたとおりには動かず、かなり最適化されるとのこと。 例外、オブジェクト生成も最適化され、jmp になったり、そもそも生成されなかったりする。
おすすめの Truffle 学習方法:
- SimpleLanguage からコピペ
- gitter で聞く
- Writing a Launguage in Truffle(http://cesquivias.github.io/blog/2014/10/13/writing-a-language-in-truffle-part-1-a-simple-slow-interpreter/) を読む
感想etc
この話を聞いてから自分でも SimpleLanguage のコードを見てみたがなかなか分かりづらい。 いわれてたようにコピペから始めたほうが良さそう。
話を聞く前はもうちょっと簡単にできるんだろうかと思ったが、コンパイラフロントエンド相当の部分はがっつり書く必要がありそうだ。 それとそもそも Java がつらい部分はある。
あと Java だとパーサーは Antlr 使うことになりそうなので、やるんだったら Antlr も抑えておいたほうが良さそうだなあ。
AtCoder Beginner Contest 121
久しぶりにプログラミングコンテストやってみたが、ビギナーで 1000 点中 300 点しかとれなかった。雑魚い。
反省点:
前者については解答方法はわかっていながら全然手が追いついてない状態なので、 C++ でのプログラミングコンテストに慣れれば少しはマシになるはず。
後者は経験の他、柔軟さが足りてない感じがする。
とりあえず他の参加者のコードを読んで見るところから練習し直しする。
C++ Mix #2
C++ Mix の第2回に参加してきたメモ。
iOS パズル「パズモナ」の秘密, @5mingame2
C++ でゲーム作った話。
フレームワークとして CINDER というものを採用してる。
また方針として new と delete は使わず、
包含やスマートポインタでどうにかしている。
また UI は boost::any
を使用して書きやすくしている。
UI 周りは詳しくないが、や利用あるもんなんだろうか?
Qt x Reactive Extensions, @tetsurom
Reactive Extensions と Qt の話。
Rx の説明として「values-distributed-in-time」というのは初めて聞いた。 あとオブザーバパターン、イテレータパターン、関数型プログラミングのいいとこ取りというのも。
C++ でも RxCpp があるのは意外だったが、run loop は自分で仕込む必要があるらしい。 あと Qt と RxCpp をつなぐライブラリを作ったとのこと。うまく Qt の難しい部分を解決できているらしい。
C++のパッケージマネージャ「poac」を開発した話 @matken11235
poac は C++ 向けのパッケージマネージャ。 以前に聞いたときは「開発している」話だったので、結構進歩あったっぽい。 この発表を見てインストールしてみたがなかなか使えそうな感じ。
公式のドキュメント(https://docs.poac.io/ja/)を見ながら実行するとこんな感じになる。 これから対応パッケージが増えることに期待。
% poac new hello Your "hello" project was created successfully. Go into your project by running: $ cd hello Start your project with: $ poac run % cd hello % poac install hello_world ==> Resolving packages... ==> Resolving dependencies... ==> Fetching... ● hello_world 0.1.0 (from: poac) ==> Done. % vim main.cpp % poac run ==> hello Compiled: Output to `_build/bin/hello` Running: `_build/bin/hello` Hello, world!
雑談タイム
なんというかここが本番だった気がする。
基礎勉強会#6 アルゴリズム
社内で行った基礎勉強会の第 6 回。アルゴリズムの話。
アルゴリズムの話といいつつ、メインは競技プログラミングの話をしている。
アルゴリズムを勉強するご利益についても書いてみたが、これはちょっと強引だった気がする。 仕事によっては非常によく考えるし使いもするが、 アルゴリズムをまったく考えないで済むような作業があるのも確かなので、一般的にあてはまるとは言いづらい。
基礎的なアルゴリズムとしてはソートとグラフアルゴリズムから2,3個紹介するにとどめている。 ココらへんはもう実装はたくさんあるはずだし。
アルゴリズムの設計手法も競技プログラミングでよく使われるものを紹介した。 競技プログラミングについては、これのおかげでプログラミングの腕をあげた気がしているので、初心者ほどやってみるといいと思っている。
競技プログラミングサイトとしては TopCoder の他、AtCoder と AOJ を紹介した。日本語対応しているし。 過去問を解いているところを実演しようとしたが、焦ってコンパイルが通らず残念な結果に。 まあ雰囲気はわかってもらったはず。
基礎勉強会としてはとりあえずこれで終わりにするつもり。 資料作るのにかなり時間を使ってしまって、あまり自分の勉強ができていないのは良くない。 最初は他の人にも発表してもらうつもりだったが、人があつまらないんじゃなあ。 とまれ最後まで参加してくれた人には感謝したい。
基礎勉強会#5 データ構造
社内で行った基礎勉強会の第 5 回。データ構造の話。
基礎的なデータ構造としてリスト、ハッシュテーブル、ツリーを取り上げた。 データ構造の比較のために計算量の話が必要になるので、計算量も合わせて取り上げている。
資料作成に当たってはみんなのデータ構造を非常に参考にしている。良い本なので買って読もう。