Rust で ProjectEuler のレポジトリを github で公開しました
レポジトリ作った。ソースは適宜修正していく予定ですので、最新版はこちらを参照してください。
Rust で ProjectEuler #1 ~ #3
放置状態になっていたProject Eulerを再開してみることにしました。以前はHaskellでProb. 133まで解いてHaskellに慣れることができたので、今回はRustで書いてみようと思います。Haskellは最後まで使いこなせてる感は出なかったのですが、遅延評価ではないRustなら直感的に計算量とか理解できてやりやすいはず…？
というわけで、解いていきます
Problem 1
1000以下の数字で3か5で割り切れるものの和を求める問題。最初なので素直に書いた。
use std; fn main() { let sum = 0u; uint::range(0u, 1000u) { |n| if n % 3u == 0u || n % 5u == 0u { sum += n; } } std::io::println(#fmt("%u", sum)); }
特に特筆事項は無い。
Problem 2
400万以下で偶数のフィボナッチ数の和を求める問題。
use std; pure fn fib(prev: uint, cur: uint) -> (uint, uint) { ret (cur, prev + cur); } fn main() { const MAX: uint = 4000000u; let (prev, cur) = (1u, 1u); let sum = 0u; while cur < MAX { if (cur % 2u == 0u) { sum += cur; } let (prev2, cur2) = fib(prev, cur); prev = prev2; cur = cur2; } std::io::println(#fmt("%u", sum)); }
これも普通ですね。本当は
(prev, cur) = fib(prev, cur);
って書きたかったんですが、少なくとも現時点では、この方法では分割代入はできないみたいです。
Problem 3
600851475143 の最大の素因数を求める問題。
use std; fn gen_prime(primes: [mutable u64]) -> [mutable u64] { let num = alt vec::last(primes) { none { ret [mutable 2u64] } some(2u64) { ret primes + [mutable 3u64] } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { ret primes + [mutable num]; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn main() { let primes = gen_prime([mutable]); let num = 600851475143u64; while num != 1u64 { check vec::is_not_empty(primes); let p = vec::last_total(primes); while num % p == 0u64 { num /= p; std::io::println(#fmt("%u", p)); } primes = gen_prime(primes); } }
エラトステネスの篩で素数リストを作って、先頭から割っていっています。
二分探索がうまく動かなくて何度も書き直したのはここだけの秘密。境界条件はちゃんと考えてから書かないとだめですね。
とりあえず、最初のエントリはここまで。これからどんどんエントリ立てて行く予定。専用ブログ作ってもいいのかも。
Rust で Generic な数値型を作る
ちまたで話題(？) の Rust 言語。昨年末くらいから「日本語情報が全然無い、先駆者になるチャンス！」とか思いながらのろのろしてたら、先日の0.1版発表で一気に知名度が上がってしまい(´・ω・`)としているgifnksmです。
0.1リリースでいろいろ変わりましたね。tag が enum になったり、alt で列挙型の値で分岐するときに末尾にどっと(.) をつけなくてもよくなったり。実装する予定の機能(Proposals · graydon/rust Wiki · GitHub) もまだまだたくさんあり、今後にますます期待です。
さてさて、そんなRust言語で、 Generic な整数型を作ってみました。
なぜ作ったかと言いますと、以下のようなコードを普通にコンパイルした場合、
fn add<T>(a: T, b: T) -> T { a + b }
以下のようなエラーでコンパイルが通らなくなってしまうからです。
main.rs:17:29: 17:34 error: binary operation + cannot be applied to type `'a`
main.rs:17 fn add<T>(a: T, b: T) -> T { a + b }T型には + 演算子が定義されてねーよ！というエラーです。C++やDのTemplateとは違い、Rust は Generics によってポリモーフィズムを実現していますので、Generic 関数を呼び出した時点では無く、書いた時点で関数本体がコンパイルされ、コンパイルエラーになっているようです。
では、どうするか。Genericな数値を表すインターフェースを書いてやって、そのインターフェースに対する各数値型の実装を書いてやればよさそうです。関数を呼び出す側ではTではなくGenericな数値型を指定してやります。具体的には、以下の通り。
use std; import std::io; // Generic な数値型の定義 iface num<T> { fn val() -> T; fn zero() -> num<T>; fn add(++num<T>) -> num<T>; fn sub(++num<T>) -> num<T>; } // 実装 (uint) impl of num<uint> for uint { fn val() -> uint { self } fn zero() -> num<uint> { 0u as (num<uint>) } fn add(a: num<uint>) -> num<uint> { (self + a.val()) as (num<uint>) } fn sub(a: num<uint>) -> num<uint> { (self - a.val()) as (num<uint>) } } // 実装 (int) impl of num<int> for int { fn val() -> int { self } fn zero() -> num<int> { 0 as (num<int>) } fn add(a: num<int>) -> num<int> { (self + a.val()) as (num<int>) } fn sub(a: num<int>) -> num<int> { (self - a.val()) as (num<int>) } } // Generic な数値型を使った関数 (要素数が0の時は死ぬ) fn sum<T>(vals: [num<T>]) -> num<T> { vec::foldl(vals[0].zero(), vals) { |s, t| s.add(t) } } fn main() { // [int] の和を求める std::io::println(#fmt("%d", sum(vec::map([1, 2, 3]) { |v| v as (num<int>) }).val())); // [uint] の和を求める std::io::println(#fmt("%u", sum(vec::map([1u, 2u, 3u]) { |v| v as (num<uint>) }).val())); }
addで引数にとる数値型が自分と同じ型であることを保証するために、Tを型パラメータとしてnumに追加しています。また、num<T>型の"0"を取得する方法がわからなかったので、配列の0番目の要素に対して.zero()を呼び出すという格好悪い実装になっています(これは、ifaceが定数を持てるようになれば解決する、かも？)
上記のように、自分で実装したら不格好になりました。Language Proposal のProposals for interfacesのOperator overloadingの節によれば、
iface num { fn +(self, self) -> self; fn -(self, self) -> self; /* etc */ }
のようなnumが組み込み型に対して定義されるようになるらしいので、ユーザー側でわざわざ不格好な定義をしなくてもよくなるかもしれません。
しかし、ユーザーが後付けで型に対する操作を追加できたり、限られたスコープでオープンクラス的に操作を追加できるあたり、Haskellの型クラスを思い出させます。後発言語なだけあって、インターフェースの仕様が洗練されてて良い感じだなー、と思います。
システムプログラミング言語、Rustの今後に期待ですね！！
2012/9/27 追記
最近の Rust では、コアライブラリにNumトレイトが標準で組み込まれています (以下は、2012/9/27 時点での incoming ブランチから持ってきた定義です)
trait Num { // FIXME: Trait composition. (#2616) pure fn add(other: &self) -> self; pure fn sub(other: &self) -> self; pure fn mul(other: &self) -> self; pure fn div(other: &self) -> self; pure fn modulo(other: &self) -> self; pure fn neg() -> self; pure fn to_int() -> int; static pure fn from_int(n: int) -> self; }
こんな感じ実装＆使用できます。
// bigint::add などは別途定義しておく impl BigInt : Num { pure fn add(other: &BigInt) -> BigInt { bigint::add(&self, other) } pure fn sub(other: &BigInt) -> BigInt { bigint::sub(&self, other) } ... static pure fn from_int(n: int) -> BigInt { bigint::from_int(n) } } fn factorial(n: uint) { let mut prod: BigInt = from_int(1); for uint::range(2, n + 1) |i| { prod *= from_int(i); // 左辺の prod から型推論可能 } }
Num トレイトを実装した型については、演算子もオーバーロードされたものが使われます。Rustの演算子オーバーロードは core::ops の Addトレイトなど、各演算子毎に定義されたオーバーロード用トレイトを実装するのが本来のやり方ですが、どうやらNumトレイトは特別扱いされているようです。
fn main() { let n: BigInt = from_int(1); let m = n + from_int(2); let k = n * m - from_int(10); }
Titech Portal Auto Loginの更新とメンテナー募集のお知らせ
Titech Portal Auto Loginを更新しました。更新内容は，ソースコードの整理です。
作者修了につき，多分これが最後の更新になります。東工大ポータルの仕様が変わらない限り現在のスクリプトは動き続けると思いますが，将来的に正しく動き続けるかどうかは分かりません。
というわけで，スクリプトを更新してくれるメンテナーさん募集です。MITライセンスにしたので，黙ってフォークしてくれても全然構わないのですが，名乗り出て頂けると現在のユーザーさんに告知できるので何かとありがたいです。バグフィックスのみならず，新機能をどんどんつけちゃうぜーってのも歓迎です。JavaScript分かるぜーという東工大生さんは是非。
2010/2/22 02:28追記
id:eagletmtさんがGoogle ChromeのUserScriptに移植してくださいました！ titech_portal_auto_login.user.js
あと，Firefox版もForkしやすいようにgistにアップロードしておきました。titech_portal_auto_login.user.js
2011/12/25 16:34 追記
@keisukefukuda さんがメンテナーに名乗り出てくださいました！ありがとうございます！！
今後東工大ポータルのログインページになにか変更があった場合、こちらのgistをご参照ください。
https://gist.github.com/1216571
ご紹介が遅くなって申し訳ありませんでした。。。
ニコニコ動画で watch ページにタグの履歴を表示する Greasemonkey スクリプト: NicoTag Tab を作った
- インストールはこちら
- NicoTag Tab for Greasemonkey
機能
- データグリッド状にタグを表示します
- グリッドの列毎にソートすることができます
- 表示する要素をフィルタリングすることができます
- XUL/Migemoがインストールされていると，ローマ字から日本語のタグをフィルタリングできます。
ニコニコ動画でコメントを取得する方法のメモ
動画再生ページ上で動作するGreasemonkeyスクリプトから，動画についたコメントを取得する方法は主に2通りある。それぞれについてメモ。
新プレイヤーのAPIを使う方法
javascript: function hoge(data)alert(uneval(data)); void(document.getElementById("flvplayer").ext_getThreads('hoge'));以下のような応答が得られる。
[{type:"main", id:0}, {type:"local", id:1}]
ここで得られたスレッドID?を使って，以下を呼び出す。
javascript: alert(JSON.stringify(document.getElementById("flvplayer").ext_getComments(1)));
以下のような応答が得られる。コメント番号降順で得られるっぽい。
[ {"message": "mohrmohr", "resNo": 13, "vpos": 14970, "date": "Sun Nov 21 2010", "command": "184"}, {"message": "ahogeahoge", "resNo": 12, "vpos": 7340, "date": "Sun Nov 21 2010", "command": "184"}, {"message": "mohrmohr", "resNo": 11, "vpos": 3160, "date": "Sun Nov 21 2010", "command": "184"} ]
得られるコメントは，動画上で表示されているものと同じよう。10分超の動画なら1000件だし，短ければ得られるコメントも少なくなる。
メッセージサーバにアクセスしてXMLを取得する場合と比較したメリット・デメリットは以下の通り。
メリット
- 通信が発生しない
- 即座にコメントを取得できる
- 複数のGreasemonkeyスクリプトからコメントを取得してもアクセス制限されない
- JSのオブジェクトとして直接取得できる
- パース処理が不要
デメリット
- 動画に表示されているコメントしか取得できない
- ユーザID，プレミアムか否か，コマンド等が取得できない
- 投稿者コメントが取得できない？
コメント中のURLを抽出するなどの用途なら十分使い物になりそうですね。
メッセージサーバにアクセスする方法
昔からある方法。404 Not Foundを参考にすれば良さそう。
リクエストの<thread>要素の属性として，whenとwaybackkeyを与えれば過去ログも取得できる？
LaTeXのOTFパッケージ＋新jsドキュメントクラスでredeffont
これまで
\usepackage[deluxe, expert]{otf} \usepackage{redeffont}
を使っていて，見出しのフォントが太字にならないことに悩んでいた．今回，太字にならない原因と，その対策が分かったのでそれをまとめる．
そもそもredeffont.styが新ドキュメントクラスに対応していなかった
このことはredeffont.styのソースを読んでみれば当然な挙動であることが分かった．以下，redeffont.styの冒頭部分抜粋
\newif\if@asciiclasses \@asciiclassesfalse \newif\if@articleclass \@articleclassfalse \newif\if@bookclass \@bookclassfalse \@ifclassloaded{jarticle}{\@asciiclassestrue\@articleclasstrue}{} \@ifclassloaded{jbook}{\@asciiclassestrue\@bookclasstrue}{} \@ifclassloaded{jreport}{\@asciiclassestrue}{} \@ifclassloaded{tarticle}{\@asciiclassestrue\@articleclasstrue}{} \@ifclassloaded{tbook}{\@asciiclassestrue\@bookclasstrue}{} \@ifclassloaded{treport}{\@asciiclassestrue}{} \if@asciiclasses \else \endinput\fi
\endinputは，これ以上のファイルの読み込みを停止するという命令．すなわち，jarticleやjbookなどの，旧ドキュメントクラスの場合のみredeffontの定義が読み込まれることになる．見出しのフォントが置き換えられないのも当然だ．
redeffont.styが不要だった
redeffontが使えない，それでは自分で定義を書くしかない．そう思い，jsarticle.clsの\section定義部分を見てみたら以下のようになっていた．
\if@twocolumn \newcommand{\section}{% \@startsection{section}{1}{\z@}% {0.6\Cvs}{0.4\Cvs}% {\normalfont\large\headfont\raggedright}} \else \newcommand{\section}{% \if@slide\clearpage\fi \@startsection{section}{1}{\z@}% {\Cvs \@plus.5\Cdp \@minus.2\Cdp}% 前アキ {.5\Cvs \@plus.3\Cdp}% 後アキ {\normalfont\Large\headfont\raggedright}} \fi
なんと，\headfontというコマンドが定義されているではないか．定義は以下のようになっていた．
\newcommand{\headfont}{\gtfamily\sffamily}
なるほど．こいつを置き換えてやればよさそうだ．"jsarticle redeffont"でググっても情報が出てこなかったわけだ．
結局どうしたか
今後はredeffontの代わりに，以下のように宣言してやることにする．
\usepackage[deluxe, expert]{otf} \renewcommand{\headfont}{\gtfamily\sffamily\bfseries}
