Archive for the ‘自由研究’ Category
大学図書館の自動化書庫に潜入してきた
3月 24th, 2013 | 
Author: 某北海道にある旧帝国大学の図書館が新しくなったそうです。新しくといっても、ずいぶん前だそうなのですが。
私が入学した当時（8年前ぐらい）は、ずいぶん建物が古かったと記憶していて、
一年生のときに数度のぞいてみて「自分は使わないな」と思って以来、ずっと入ったことがなかったのです。
行ってみると思った以上にできることが増えていて、もっと早く興味を持っていたらよかったなと思う次第です。
その新しくなった図書館の一番の目玉は意外なことに「書庫」だそうで、その名も「自動化書庫」。
某北海道にある旧帝国大学の図書館（しつこい？）には、
30万冊（と説明で言っていた気がする）の蔵書が眠っているそうですが、
これを一か所に集めて、人が入ってとってこれるように書棚をレイアウトしようと思うと、かなり広い空間が必要になるそうで、
広さは体育館1つ分ぐらい高さは一般的な建物の3階分ぐらいになるそうです。
その広い書庫から本を取り出してこようとすると大変です。
また、本を詰め込むために、一階と二階の間に中二階にしてその間にも本を詰め込むような構造になっていたようで、耐震上もあまりよろしくなかったようです。
そこで、本を効率的に格納し、また取り出す際も短時間で取り出すことができるように、
書庫を自動化し情報システムで管理し、ロボットによってピッキングする近未来的な書庫が作られたのでした。
普段は関係者以外立ち入り禁止のところ、今回、特別に見学させてもらいました。
これは、本の取り出しを要求する情報端末です(右下の警告を見る限り、OSはWindowsで動いているようです（笑）)。ここに、取り出したい本を指定すると、
こっちからベルトコンベア式に運ばれて出てきます。
この時点でもう、テンションが上がってしまいますよね！
さあ、中に入っていきましょう。
立ち入り禁止ですよ、奥さん。
怪しげな地下室実験室とかに連れてかれたらどうしよう、とか考えながら進んでいくと・・・
そこには、柵で囲われた書庫空間が広がっていました。
あまり奥まで入れないので、どこまで先があるのかわかりませんが、すごい量の本がありそうです。
説明もついていました。539000冊も収容できるようです！
こちらは操作盤
ラックに近づいてみました。雑誌は複数の部を一冊にまとめているようです。
こんな角度からも。
書庫が地下に移ったわけですが、
元の場所はどうなったかというと・・・
こうなりました。
北大の図書館に限らない話ですが、
大きな大学図書館は、単なる本の貸し出しとしての役割のみならず、
文化的、歴史的な資料の保管場所としての役割も果たしているらしく（北大の場合、アイヌ民族とか札幌農学校のとか）、
簡単に使わないものは捨てて使うものだけとっておく、というわけにもいかないようです。
かといって、まったく使わない資料ばかりではないので、たくさんの蔵書の中から効率的に取り出してこなければいけません。
さすがに30万冊となると、効率化していかないと取り出すのに時間がかかりそうです。
私の周囲の研究室にこんな研究（↓）をやっているところがあるのですが、
http://eprints.lib.hokudai.ac.jp/dspace/handle/2115/51243
まさにこの研究の対象としているような、膨大な倉庫の効率的なピッキング問題ですよね。
研究発表を聞いていた時は、「こんなの最適化してどうするんだ」と内心思っていたのですが、意外と応用場所はあるようですね。
ハイテクなものを見れて興奮したのと、研究の面白い応用先を見つけてしまって興奮したので、このブログを書こうと思い立ったのでした。
北大図書館には、facebookのページなどもあるようなので、このエントリを見て興味を持ってくれた方がいらっしゃればぜひ見ていってください。
http://www.facebook.com/hokudailibrary
Posted in 
さくらスタンダードでRubyのCGIを動かすための注意
こんな感じのコードをCGIとしてサーバー上で動かしたいとします。
# test.rb
#!/usr/local/bin/ruby # # -*- encoding: utf-8 -*- # print "Content-Type: text/plain\n\n" print "テスト"
私はさくらサーバーのスタンダードを使っているのですが、 このサーバーは初期設定でRubyが使えるのですね。 サーバーコントロールの「サーバー情報」から確認できます。 Ruby のバージョンと実行パスは次の通りでした。
Ruby 1.8.7 /usr/local/bin/ruby
これならCGIから使うのは簡単だと思い、上記のコードを置いて実行してみたのですが、早速トラブルが。 次のいずれかの状況になった場合は、私と同じですので、解決策を残しておきます。
問題1: Rubyが実行されずにソースコードテキストが表示される。
問題2: Internal Server Error
1. の場合は、解決策1, 解決策2 あたりを、 2. の場合は、解決策3 あたりを試してみてください。私の環境ではこれで解決しました。
解決策1: ファイルパーミッションは「755」または「705」
Rubyファイルがapacheから実行可能になっていなければなりません。
解決策2: .htaccess に下記を追加 (.rb を CGI で使用可能にする)
AddHandler cgi-script .rb
解決策3: 改行コードを CR+LF から LF に変更する
サーバー上のVIM で開いたときに ^M がついていたら、このケースです。
Windows上で作成されたファイルのため、改行コードが CR+LF になっているのです。 Linux用の改行コードである LF に変更しましょう。
（私は秀丸エディタを使っているのですが、このエディタではWindows上で改行コードを LF に変えられます。）
実は問題3として次のような問題が起きているのですが、いまだ解決せず。。。
問題3: 文字化ける
print "テスト"
の部分が文字化けて表示されます。 次のサイトが参考になりそうなのですが。
さくらサーバーは EUC がデフォルトとのことですが、UTF-8はだめなのかしら。いやそんなことは・・・
追記: 文字化けの件ですが、なんのことはない。 下記を付け忘れただけでした。 （前回、あれだけ偉そうに語っておいて・・・）
print "Content-Type: text/plain; charset=utf-8\n\n"
JSONPで悩むある程度の人々へ
JSONPって、クロスドメインでデータをとってこれて、Web APIとかはこれで実装されているんでしょ。
なんとなくわかる気がするんだけど、自分で作ってみるとなんかうまく動かない。
あるいはその手前で、どういう風に実装していいかわからない。
とくに自分がAPIを提供する側になると、よけいよくわからない。
Wikipediaの解説なんか、わけがわからないよ。
こんな感じの方はいませんか。
というか、ちょっと前の自分はこんな感じでした。
いろんなサイトを調べまくって、ある程度わかってきた気がしますので、後のためにここに残しておきます。
ああ、あのころの自分に教えてあげたかった。
まずJSONって何さ？
JSONPにたどり着いた人はJSONのことは知っていると思いますから、簡単に。
こんな感じの「テキスト」のことですよね。
{
"key1": "value1",
"key2": "value2"
}
cgi等で出力するときのちょっとした注意としては、
content-type: application/json; charset=utf-8
{
"key1": "value1",
"key2": "value2"
}
とすることぐらいでしょうか。
Content-Typeをつけないと、ajaxで受け取れない場合があります。
ブラウザによっては、charsetを付けないとうまく動作しなことも（OperaとかOperaとかOperaとか・・・）
このあたりの事情はこのサイトが詳しいです。
「JSONのContent-Typeは「 text/javascript 」でなく「application/json」で」
で、これをJavascriptで受け取るための関数がjQueryとかで用意されているわけですね。
たとえば、$.getJSONなんかいかがでしょう。使い方は次の通り。
// 同じドメインの test.cgi から JSONデータを取得して表示
$.getJSON("test.cgi",
function(data){
alert("key1:" + data.key1);
alert("key2:" + data.key1);
});
これで alert が 2つ現れるはずです。
getJSONの引数に入る無名関数 function() は、コールバック関数と言って、
ajaxのレスポンスを受け取ると、呼び出される関数です。
この関数には、基本的になんでも入れられるのですが、一つ注意があるとすればクラスオブジェクトのメンバ関数はいれることができません。
（メンバ関数を無理やり入れたい時は、thisポインタごとグローバル変数にしてしまって、無理やり入れる方法があります。）
GETのパラメータを渡したい時は、2番目の引数を入れて次のようにすればよいでしょう。
// 同じドメインの test.cgi に test.cgi?param1=value1¶m2=value2 としてリクエストをかけ、
// JSONデータを取得して表示
$.getJSON("test.cgi",
{
param1: "value1",
param2: "value2"
},
function(data){
alert("key1:" + data.key1);
alert("key2:" + data.key1);
});
じゃあ、JSONPって？
おまたせしました、ようやくJSONPです。
JSONPはJSON with Paddingの略称で、次の形式で書くことが出来ます。
callback({
"key1": "value1",
"key2": "value2"
})
callbackで挟んだ以外は、ぱっと見て先ほどと変わりないですね。 読み込むときは次のようにすればよいでしょう。
// クロスドメインの http://hoge.com/test.cgi からJSONPを取得
$.getJSON("http://hoge.com/test.cgi?callback=?",
function(data){
alert("key1:" + data.key1);
alert("key2:" + data.key1);
});
callback=?ってなんだそら？ってのは後で説明するとして、 ここで疑問になるのは、何でJSONPだとクロスドメインで読めるの？って話です。
まず、勘違いしやすいのは（というより私が勘違いしていたのは）、JSONPを「JSON『テキスト』に毛が生えたもの」、と思ってしまうこと。
断言しましょう！JSONPはテキストではなく「script」です！
そもそも、JSONはどうやって読んでいたのでしょう。
jQueryだと中身をラップしていてわからないので、中の仕組みに戻ってみましょう。
JSONを取得するときはXmlHttpRequestというメソッドで取得していました。
正確ではありませんが、ざっくりと書くと次のようです。
// 同じドメインの test.cgi から JSONデータを取得して表示
var req = new XMLHttpRequest();
req.open('GET', 'test.cgi', false);
req.send(null);
if(req.status == 200)
{
var json = req.responseText;
var data = eval(json);
alert("key1:" + data.key1);
alert("key2:" + data.key1);
}
この場合だと、XmlHttpRequestの制約でドメインの異なる場所からはデータを取得することが出来ません。 （一種の安全策ですね。） 一方でJSONPの場合は、取得方法が全く異なります！
// クロスドメインの http://hoge.com/test.cgi からJSONPを取得
var hoge = function(data) {
alert("key1:" + data.key1);
alert("key2:" + data.key1);
}
var script = document.createElement('script');
script.src = 'http://hoge.com/test.cgi?callback=hoge';
document.head.appendChild(script);
え！！wwww
ぜんぜんちゃうやん。。。
どういう仕組かというと、Javascriptのコードはクロスドメインから読むことが出来ますよね。
たとえば、jQueryの1.8.3を読むときなんかに、google (クロスドメイン) からこんなコードで読んできたりしますよね。
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.3/jquery.min.js"></script>
で、スクリプトが読み込まれると、そのスクリプトが自動で実行されるわけです。
さらに、javascriptには、動的にスクリプトをロードする機能があります。
これらの特徴を生かしてデータをクロスドメインから受け取る手法がJSONPです。
事前にこちらのスクリプトで、コールバック関数を用意しておき、
そのコールバック関数と同名の関数の引数にJSONをつっこんだ（Padding）したスクリプトを返すようクロスドメインのサーバーに要求し、
動的にそのスクリプトを読み込んだ瞬間にこちらのコールバック関数が引数にJSONをつっこんだ状態で呼び出される。
そのコールバック関数内でJSONのデータを使って好きな処理をしてあげれば一丁上がり！
これがJSONPの仕組みです。
参考: 「セミコロンが必要ない: jsonp」
http://blog.livedoor.jp/tempdog/archives/482314.html
「気になったもの JSONP他」
http://fukenkoh.blog.shinobi.jp/Entry/12/
これがわかってくると、$.getJSON()の処理もわかってきます。
// クロスドメインの http://hoge.com/test.cgi からJSONPを取得 (再掲)
$.getJSON("http://hoge.com/test.cgi?callback=?",
function(data){
alert("key1:" + data.key1);
alert("key2:" + data.key1);
});
これはjQueryの仕様なので覚えるしかありませんが、
callback=?という部分の?にjQueryの独自の関数名を埋め込んで呼び出されます。
そして同名の関数をサーバーからロードし、function(data)が実行されます。
実際、通信の様子を見てみると、
http://hoge.com/test.cgi?callback=jQuery183002421796810813248_1357198175025
のようなリクエストをかけていることがわかります。
参考 「jQueryとJSONPと$.ajax()と無名関数」
http://d.hatena.ne.jp/littlebuddha/20100223/1266928860
jQueryのバージョンにも注意！
jQueryが1.4とかだと、XmlHttpRequestしか対応していなかったりします。
そのせいで、クロスドメインで呼んだらだめよ～、ってエラーが出ます。
cgi側でも注意。
content-type: application/json; charset=utf-8
ではなく、
content-type: application/javascript; charset=utf-8
とすること。
あくまで「スクリプト」なのです。
参考
「JSONとJSONPのContent-typeに書くMIMEタイプ」
http://d.hatena.ne.jp/kanonji/20110406/1302065168
「JSONとJSONPの違い」
http://taiju.hatenablog.com/entry/20090902/1251851867
「jQuery.getJSON(url, [data], [handler])」
もう１つは、クエリパラメータとしてcallback=functionNameが与えられたとき、
functionName({
"key1": "value1",
"key2": "value2"
})
とコレスポンスのスクリプトでコールバック関数の名称を合わせてあげる必要があります。
関数名が固定だと困るのです。
たとえば、jQueryの例でいうと、先ほどあげたように、
callback=jQuery183002421796810813248_1357198175025
のような謎の文字列でコールバック関数を要求してきます。
これに対応できないと、データを受け取ってもコールバックが実行されないのです。
細かいことですが、JSONPのデータにセミコロンはいりません！
こんなにも落とし穴がたくさんあるのにもかかわらず、
なんでちゃんとした解説がほとんどないのよ！！
というわけで、
あのころの自分に解説してあげたかった解説を同じような境遇の何人かの方に贈ります。
ちょっと関係ないけど
「Content-type:text/htmlのcharset指定はUTF-8,utf-8,utf8どれが正しいの？調べてみた。」
http://dqn.sakusakutto.jp/2011/08/content-type-texthtml-charset-utf8.html
国際宇宙ステーション(ISS)の座標を取得するAPIを作ろう
とある事情で（ http://tsujimotter.info/2013/01/01/hackathon-20121231/ )、
現在時刻におけるISSの座標（緯度・経度）を取得するAPIがほしくなったのです。
APIの用途ですが、「なんとなくこの辺にいるんだなあ」
と眺めれればいいので、精度はそこまで正確じゃなくていい。
JAXAとかNASAとか、なくても有志で誰か作っているだろう、と思ったのですが、これが、どこ探してもないのですね。
こんなの（ http://www.lizard-tail.com/isana/tracking/ ）はありますけど、Ajaxで座標データをとってきたりはできません。
実際こんなAPIがあればみんな使うんじゃないですかね。
宇宙に対する興味は専門家だけのものではないはずです！！
「ないなら作ってしまえばいいじゃない」
ということで、制作に向けて調べていたことをまとめます。
そもそも前提条件として、
１．私自身は衛星の専門家ではない。
２．ましてやJAXAとかそこら辺の関係者でも、宇宙クラスタでもない
知識がまるで足りない。宇宙兄弟で初めてISSの存在を知った程度。
調べている中思ったのは、宇宙関係の専門用語が多すぎてよくわからん。
というわけで、まず、状況を整理しましょう。
（専門家でない私が軽く調べた程度ですので、合っているかどうかは保証しかねます。）
・TLE (2行軌道要素形式)
初期値のようなもの、データ取得時点での軌道のパラメータをまとめたものです。
http://ja.wikipedia.org/wiki/2%E8%A1%8C%E8%BB%8C%E9%81%93%E8%A6%81%E7%B4%A0%E5%BD%A2%E5%BC%8F
SpaceTrack.com や celestrak.com で取得できるそうです。
SpaceTrack.com の方が精度がよいそうなのですが、は残念ながら再配布禁止とのこと。。。ただし例外あり（参考： http://www.lizard-tail.com/isana/diary/?date=20110417 ）
追記：
ISSに関してはNASAのページがPublic domainで公開しているそうです。
（データ取得先は、 http://spaceflight.nasa.gov/realdata/sightings/SSapplications/Post/JavaSSOP/orbit/ISS/SVPOST.html ）
（上記ページのパラメータ解説はここ http://spaceflight.nasa.gov/realdata/elements/index.html ）
参考：
http://www.lizard-tail.com/isana/tle/?set=watch
spaceflight.nasa.govで提供されているデータはアメリカ合衆国著作権法によりPublic Domainとなっています。
・SGP4, SDP4
TLEを基に軌道情報を計算する手法
http://ja.wikipedia.org/wiki/SGP4
どちらの方式もOrbitToolsというC++のライブラリで計算可能です。
http://www.zeptomoby.com/satellites/
これらを使ってサンプルコードをGitHubに上げました。
https://github.com/junpeitsuji/OrbitToolsWebAPI (URL変更しました)
https://github.com/junpeitsuji/SateliteTracker
さあ、これを使ってWEBサービスを作ろうか、と思ったのですが、
計算しているうちにいろいろと発見があったので先にまとめてしまいます。
・勘違いその１: 衛星は常に同じ軌道を通る
SPG4で計算した衛星の軌道
このデータは、GitHubのコードを使って(OrbitTools C++)、
SGP4で計算したものです。横軸は緯度、縦軸は経度です。
計算に使ったTLEは下記のもので、TLE取得時刻から1440分の衛星軌道を1分おきにプロットしたものです。
ISS
1 25544U 98067A 13001.52012361 .00016717 00000-0 10270-3 0 9002
2 25544 51.6441 216.2888 0015668 109.9671 250.3170 15.51850049 8742
実際はこんな感じの軌跡となり、毎回違う経路を通るのです。
・勘違いその２: 一定の規則で通るから、その式がわかればずっと先まで計算できる
前半部分はあっています。
グラフからみておよそ法則性のある動きをしていますから、おそらくこのまま計算し続ければよいのでしょう、と思いました。
そこで、この先のデータまでこの式の通りに計算してみるとエラーが出てしまいました。
デバッグしてみるとライブラリの内部で時刻の積を計算しているときに停止しているようです。
これがこのライブラリのバグなのか、原理的なものなのかはわかりません。
たしかにWikipediaによるとSGP4方式は「周回周期が225分以上の衛星には向かない」とか制約があるそうなのです。
「まあそんなの正確さに目をつむれば大したことない」と思っていたのですが、計算できないのであれば事情は変わりますね。
ということで、TLEは定期的に更新する必要がありそうです。
APIの仕様としては、次のようなものでしょうか。
TLEを入力すると、現在時刻の緯度、経度を返す。
入力（リクエスト）: 最新のTLEのURI
出力（レスポンス）: 現在の衛星の座標（緯度・経度)
別途TLEを更新できる機能がほしい所です。
JSONのレスポンスのイメージはこんな感じです。
http://tsujimotter.info/webgl/json/orbit.json (URL変更しました)
http://tsujimotter.info/webgl/orbitjsonp.cgi (下記に変更しました)
肝心の作業ですが、gccが自由に動くlinuxサーバーを持っていないので、ちょっと手が止まっています。。。
お時間のあるハッカーさんがいましたら、
私のコードを使って勝手に作ってくださってもよろしくってよ。 笑
追記：
サーバー上でAPIが動くところまで作りました。
2013/1/4現在、下記URLで動かしています。
よろしければ使ってみてください。
http://tsujimotter.info/iss/orbitjsonp.cgi?callback=jsonp (下記に変更しました)
http://tsujimotter.info/api/SateliteTracker/orbitjsonp.cgi?callback=jsonp
（このページは予告なく変更することがあります。）
仕様はGitHubの README.txt に記載しています。
当然ですが、ソースコードをforkして使っていただいて構いません。むしろ修正して、よくしてくれたりしたら、泣いて喜びます。
https://github.com/junpeitsuji/SateliteTracker
40-32÷2=4!の一般解 (4) 巨大因数の探索
[latexpage]
前回から続いて、${(w-1)!-1}$ が合成数である場合を考えましょう。
基本的な考え方は素数の場合と同じです。
解を持つ $z$ の条件は、
\[
\begin{equation}
z < (w-1)! \tag{5}
\end{equation}
\]
\[
\begin{equation}
(z-1) | \left(w ((w-1)! – 1)\right)\tag{6}
\end{equation}
\]
です。
(6)より、$w$の素因数と、${(w-1)! – 1}$の素因数をそれぞれ求めて、 その組合せから${w ((w-1)! – 1)}$のすべての約数を求めればよいでしょう。そのときは、(5)の条件も考慮して不必要な要素を省いていきます。
さて、ここまで、最初の問題の解のパターンを、すべて導出するという目的で議論してきましたが、これらの問題はある種のパターンの合成数に対する素因数分解の問題に深くかかわっていることがわかってきました。
とても残念ですが、素因数分解の問題を一般性を残したまま扱うのは、そろそろ限界かもしれません。
40-32÷2=4!の一般解 (3) 階乗素数との関係
さて、前回までに分かったことを一旦まとめてみましょう。
まず問題ですが、
\[
\begin{equation}
x-\frac{y}{z} = w!
\end{equation}
\]
\[
\begin{equation}
\frac{x-y}{z} = w
\end{equation}
\]
を満たすような$1$以上の正整数$x$, $y$, $z$, $w$を求めよという問題でした。
これに対し、これまでの議論から、適当な$z$, $w$を選ぶと
\[
\begin{equation}
x = \frac{z w ((w-1)!-1)}{z-1}
\end{equation}
\]
\[
\begin{equation}
y = x – z w
\end{equation}
\]
と解が得られることがわかっています。
ただし、$w$に対する$z$において、解が得られるための下記の制約条件がありました。
\[
\begin{equation}
z < (w-1)!
\end{equation}
\]
\[
\begin{equation}
(z-1) | (w ((w-1)! – 1))
\end{equation}
\]
条件(5) は 式 (4) に対し $y > 0$ から得られます。一方、条件(6)は式(3)の$x$が整数であることから導かれました。
40-32÷2=4!の一般解 (2) zの条件
まだもう少し続けられそうなので、解なしの部分に関して
${w=4, z=4}$のとき、
\[x=\frac{4\cdot 20}{3}\]
を満たす解はありませんで
$4$は$3$で割れませんから、$20$を$3$が割り切るか考
40-32÷2=4!の一般解 (1) 問題提起
40-32÷2=4!
が流行ってるようなので、暇つぶしにこのパ
まずこの問題は、下記の二式を満たす4つの整数$x,y,z,w$を
\[
\begin{equation}
x-\frac{y}{z}=w! \tag{1}
\end{equation}
\]
\[
\begin{equation}
\frac{x-y}{z}=w \tag{2}
\end{equation}
\]
ここで、式2つに対して、変数4つなので、自由度は2です。2つ変数を決めれば
式変形して議論しやすい形に持って行きます。