たにしきんぐダム

プログラミングやったりゲームしてます

空間インデックス(R-tree)入門

R-treeとは空間データを効率良く検索するためのインデックス構造。R-tree について調べたのまとめておく。

目次

  • 目次
  • 参考資料
  • ナイーブな例
  • R-tree の概要
  • 参照処理
    • 点検索
    • 範囲検索
  • データの挿入・削除
    • 挿入処理
    • ノードの分割
      • Exhaustive Algorithm
      • Quadratic-Cost Algorithm
      • Linear-Cost Algorithm
    • 削除
    • 更新処理
  • まとめ

参考資料

続きを読む

Scala でジェネレータを作ったり、遅延評価してみる

メリークリスマス!!!!!!
この記事は CAMPHOR- Advent Calendar 2015 の25日目の記事です.

Scala はまだ始めたばかりですがとりあえずジェネレータ作ったり遅延評価してみようと思います.

これまでの流れ

ジェネレータ

とりあえず1から順番に無限に数字を生成するジェネレータを作ってみます.
Scalaではクロージャを使うことで割と簡単に実現することができます.

クロージャは評価可能な局所変数と評価する関数をまとめたもので、以上の例のように状態を保持する、関数を返す関数のようなものを定義することができます.

上の例の無名関数は実行されるたびに局所変数numの値を増やしてからnum:Intを返します.

遅延評価

クロージャを使ったジェネレータでも遅延評価が実現できていることが分かると思いますが、Stream を使うことによって遅延評価を簡単に実現することもできます.

まずは Stream の簡単な例を見てみましょう. Stream は List によく似ています.

Stream(1, ?) とはどういうことでしょうか?
Stream は先ほど述べたように List に似ているのですが、List の tail には残りの List へのポインタが入っているのに対して
Stream の tail には lazy val (? の正体) が入っています. lazy val はもちろん実際に計算に値が必要になるまで評価されることはないため、Streamの要素は遅延評価され無限の長さを持つことができます.

以下の例はStreamを使って同様のことを実現したものです.

range は Stream型を返すので以上のように再帰的に定義することができます.

フィボナッチ数列を無限に返すストリーム

それでは Stream を使って無限にフィボナッチ数を返すストリームを作ってみましょう.
コードは以下のような感じになります.

何故これが無限にフィボナッチ数を返すストリームになるかを解説していきます.

以下のような表を見てみると分かりやすいかもしれません.
これはfibGenfibGen.tail などの Stream を正格コレクションに直した場合の数字列です.

1 2 3 4 5 #
1 1 2 3 5 fibGen.tail
0 1 1 2 3 fibGen
(0,1) (1,1) (1,2) (2,3) (3,5) fibGen.zip(fibGen.tail)
1 2 3 5 8 fibGen.zip(fibGen.tail).map(n => n._1 + n._2)

このようにfibGenをひとつシフトしてその和を足せば 残りのストリームを定義することができます.

追記

View

scala にはコレクションを仮想的に遅延評価するためにビューという機能があります.
Stream以外のコレクションはすべて正格評価されるのですが、任意のコレクションをビューという遅延評価される仮想的なコレクションに変換し、forceメソッドで正格評価されるコレクションに戻すことができます. 例えば以下のような感じです

Stream と違って無限リストを生成することは出来ませんが、異常に巨大なコレクションの一部のみを取得したい場合などは気軽に遅延評価をすることができて便利だと思います. 詳しくは Collections - ビュー - Scala Documentation を参照お願いします


CAMPHOR- Advent Calendar は延長します!!!
明日は@ryota-kaです. お楽しみに!

参考

pixivインターンに参加して中学生から使ってるpixivのコード見た

12/12(土), 12/13(日) の二日間で pixiv株式会社の短期インターンに参加してきました.

ssl.pixiv.net

pixivはほぼROM専ながらも中学生の頃からよく使っているサイトで(ちなみに今は大学3回生) その中身を触らせてもらっただけでなく、まだ新鮮なバグにも取り組まさせてもらえて最高だった!

f:id:tanishiking24:20151215165007j:plain:w300

はしゃいでいる様子

エントリー

2日間だけだし、面接もなく事前課題に対して出したプルリクの内容で決めるということらしかったのでかなり気軽にエントリーしたのを覚えてる.

事前課題

事前課題として与えられたのは脆弱性が含まれているという小さなウェブアプリケーション. その中から脆弱性を発見してそれを改善するプルリクを出すことで事前課題提出ということになった.(先進的っぽい!)

直せたのは一つだけだったけれど、ほかにもたくさん脆弱性はあったっぽいし もっと頑張りたかった...!

インターン開始

インターンが始まってみると まさかのpixiv本体のインターン1日前のスナップショットと その時点で本体に残ってたissue(社員もまだ手をつけてない?)から適当にメンター陣が選んだissue(15個くらい)をインターン生たちでつぶすという感じでした. 現場感あってすごい.

インターン生の開発環境として開発サーバーが与えられます. 開発環境のセットアップはほとんど自動化されてたりREADMEに詳しく書かれていたりしたのでサクサクっとストレスなく開発環境を整えることができて体験が良かった.

開発中

Github上でも現実でもメンターさんが手厚くフォローしてくれます.

f:id:tanishiking24:20151215163745j:plain 様子です

バグを直すのにpixivの重厚なコードに目を通す必要があったのですが、10年前からあるサービスなのにきちんと設計されていたので全然読みやすかった.

オフィス

すごい楽しげだった.

色使い凄いし集中できるのかなぁと思ってたけど 開発中は画面しか見てないから気にならないし、ふと周りを見回したら自分の好きな物(フィギュアとかイラストとか)が視界に入って幸せでした. 椅子も座り心地最高だった

f:id:tanishiking24:20151215171414j:plain:w400

絵馬凄い

総評

最終的には2日間で6つくらいのissueに対してプルリクを投げてOKをもらった(割と簡単めなissueにばかり手を出していたけど)

早めに作られたプルリクで良さそうなコードが本体に取り込まれるという感じで、結局僕の提出したプルリクでとりこまれることになったのは 1つで社内フレームワークに対するバグフィックスでした. 社会貢献できてよかった.

感想

楽しかったし勉強になった!

やはり自分はセキュリティまわりの知識が乏しいなぁという印象も受けたのでこれから勉強すべきことも分かった.(とりあえず徳丸本読みます)

pixivのエンジニアさんのレベルは非常に高く、会社の雰囲気も凄く楽しげで、こういう会社で働くのはとても楽しいだろうなぁ

懇切丁寧に指導してくれたメンターさんも二日間ながらも一緒にした皆もありがとうございました!

readコマンドで 矢印キー や Ctrl+x などの入力を読み取る

この記事は CAMPHOR- Advent Calendar 2015 の2日目の記事です.

シェルで標準入力を読み取るコマンドといったらreadコマンドがあります.

readの概要

read Man Page | Bash | SS64.com

readコマンドはシェルの組み込みコマンドで 標準入力を読み取り 改行文字までまたはEOFまで読み込み、 引数に変数が指定されていた場合は入力値をその変数に格納します.

readコマンドの区切り文字はシェル変数である$IFSに格納されている文字が利用され、引数に複数の変数が指定されていた場合は指定された区切り文字で区切って変数に格納されます.(デフォルトでは$' \t\n' スペース・タブ・改行文字)

ちなみに入力の区切り文字は\を頭につけることでエスケープすることができます. 便利っちゃ便利だけど\がエスケープ文字として解釈されてしまうので不便だったりする(これは後述の-rオプションで解決します)

readオプション

上記のman pageを読めば分かりますがよく使うオプションとしては以下のようなものがあります.

  • -n<nchars>
    • 普通は改行文字もしくはEOFを読むまで入力を読み取りますが、このオプションをつけることでnchars文字数だけ入力読み取ったらRET入力を自動的に読み取り、入力待ちを終了させます.
  • -r
    • 上記で述べたように区切り文字は\でエスケープできますが-rオプションをつけると、\はエスケープ文字として機能しなくなりそのまま読み取られるようになります.
  • -s
    • 通常はreadコマンドで入力を読み取るとき ユーザーが入力した文字は画面に表示されますが-sオプションをつけることで入力は表示されなくなります.パスワードの入力を要求するときとかに便利です.
  • -t<timeout>

IFS=

区切り文字に空文字を代入しています.これにより スペース・タブ・改行といった特殊文字が区切り文字として機能しなくなるため空白文字などをそのまま入力値として読み取ることができるようになります.

これで\なんかで区切り文字をエスケープしなくてもそのまま受け取ることができるようになります.

注意 $IFSの値をいじくるのはIFS= read xxxという感じにコマンドの直前につけてコマンドと一緒に実行したり、書き換えたら後で元に戻すなりするようにしましょう. 環境変数書き換えることになるので大変なことになりそう.

一文字ずつ読み取って逐一処理する

RETの入力なしに一文字入力を読み取って その入力値に沿って処理を行うというプログラムが書きたい場合、以下のような感じになります.

例えばキー入力でのカーソル移動、vimっぽくj,k,h,lの入力を読み取ってtput cuu1とかでカーソルを移動させたいときに使います.

while IFS= read -r -n1 -s char; do
  case $char in
    j)...;;
    ...
  esac
done

一文字しか入力しないのでIFS=とか-rは要らない気もしますがこんな感じでいけます.

特殊文字の検知

通常の文字は上記のようなやり方で入力を読み取ることができます. では特殊文字などはどうやって読みよればいいのだろうか...

man bashを見ると以下のような記述が有ります. $'string' のstring部分に以下に指定されているような文字を入力すると ANSI C standardの文字に変換されるようです.

Words of the form $'string' are treated specially.  The word expands to
string, with backslash-escaped characters replaced as specified by  the
ANSI  C  standard.  Backslash escape sequences, if present, are decoded
as follows:
       \a     alert (bell)
       \b     backspace
       \e     an escape character
       \f     form feed
       \n     new line
       \r     carriage return
       \t     horizontal tab
       \v     vertical tab
       \\     backslash
       \'     single quote
       \nnn   the eight-bit character whose value is  the  octal  value
              nnn (one to three digits)
       \xHH   the  eight-bit  character  whose value is the hexadecimal
              value HH (one or two hex digits)
       \cx    a control-x character

\xHH the eight-bit character whose value is the hexadecimal value HH (one or two hex digits)

とあるようにascii codeの16進数表記で特殊文字なんかも検知できそう.

(例えばaのasciiコード16進数は61なので$'x61'aの入力を読み取ることができる.)

Extended ASCII in ANSI C

standard ASCII CODE はそもそも7ビットコードでありコード表を見てもCtrl+xArrow keyなどは見当たりません.

あとで8ビット文字コードが主流になってきたとき 8bit を使って残りの128文字にみんな好き勝手な文字を当てはめていきASCIIを拡張してきたっぽい

そのようないろんな拡張ASCIIのうち有名なのがOEM Extended ASCIIANSI Extended ASCII らしい

(参考: Ascii Codes - C++ Tutorials)

bashでは ANSI Extended ASCII のほうに変換されるっぽいですね.

Ctrl+xなどの入力

\cx a control-x character とあるようにCtrl+x などの入力は$'\cx'などで読み取ることが出来ます.

せっかくなので先ほどの拡張ASCIIを使って読み取ってみると,Ctrl+xascii code 16進数表記は24なので$'\x24'で読み取ることができます.

  case $char in
    $'\cx'|$'\x24')...;;
    ...
  esac

矢印キー(Arrow key)の読み取り

矢印キーの ascii code

先ほどの拡張ASCIIコード表の上矢印(Up Arrow)をみてみると0;72とあります.なんだこれ???

よくわからないので矢印キーの asciiコード16進数表記を調べてみましょう. 入力の16進数変換にはxxdhexdumpコマンドが便利

Arrow keyの入力値をreadで読み取りその入力値を16進数変換して表示してみます.

read key; echo "$key" | hexdump

このコマンドを入力したあとにUp Arrow(上矢印)を入力すると1b 5b 41というような結果が得られます. どういうことかというとUp Arrow(上矢印)の入力は1b 5b 41という3つのascii codeの入力によって実現されてるっぽいです.

矢印キーの読み取り

  case $char in
    $'\x1b\x5b\x41')...;;
    ...
  esac

という感じで読み取ることができる.

1文字ずつ読み取ってる場合はどうするんだよ!というのがありますが、僕は以下のような感じで一文字目が$'\x1n'(エスケープ文字)だった場合はあと2文字くらい入力が起こってそうだから追加で2文字読み取って$charに追加するみたいな感じでいきました.

  while IFS= read -r -n1 -s char; do
    if [[ $char == $'\x1b' ]]; then
      read -r -n2 -s rest
      char+="$rest"
    fi

最後に

こんな感じのことを使ってニコニコ動画をターミナルから検索できるnicotermとかいうCLIクライアントを作りました.

使い方は簡単でコマンドの引数に検索クエリを入力するだけ オプションつければソート順も変更できるし カーソル位置でoとかでサクッとブラウザで動画開けたりして便利

github.com

https://gyazo.com/8334764edfb2c1ec9e9beca21d64b2af

まとめ

今回bashでの解決策について記事を書きましたがbashじゃなかったらどんな感じになるんだろう...

readでの読み取り以外でも役に立つことも多いかと思う...のでキー入力読み取りについてこの記事が助けになればという感じです.

この記事は CAMPHOR- Advent Calendar 2015 の2日目の記事です.

明日はyaitaimoです!

参考

はてな×ドワンゴ合同ハッカソン@京都 に参加してきました!

先日開催された はてな×ドワンゴ合同ハッカソン@京都 に参加してきた!

dwangohatena.connpass.com

お弁当もお菓子も飲み物も懇親会も無料だし 楽しかったし最高な感じでした

作ったもの

github.com

ニコニコ動画の検索をターミナルから出来る nicoterm というものを作ってみました.

(シェルスクリプトをがっつり(?)書くの初めてでだいぶアレな感じ...)

この nicoterm まだプロトタイプ程度の完成度で色々と追加したい機能があるので そこらへん整備したらまた改めて発表しようかと思っています. (コードもリファクタリングしないと見せられたものじゃないので...)

作るものを決める

ニコニコの検索APIを使って コマンドラインからニコニコ動画を検索できるCLIクライアントでも作るかぁという感じにしました. (クソザコなのではてなの認証をコマンドラインからうまいこと行うやり方が分からなかった...)

コンテンツ検索APIドキュメント

使う道具を決める

コマンドラインツールを作るのだから golang とか使えれば良かったのですが golang 全然触ったことなかった & そんなに難しいコードにはならないかなと思ってシェルスクリプトで書いてみることにしました.

シェルスクリプトは ループの仕方や関数宣言も怪しい感じでしたがググれば何とかなるやろという感じでした. 結果的には勉強になって良い体験になった気がします.

実際に作る

周りでは結構チーム開発したりしてたけど 僕は特に友達と参加というわけでも無かったのでボッチでやりつつ 同じテーブルになった人とかに進捗聞いたりしてワイワイ開発してました.

隣のチームがドローン飛ばしたりしてて激しい感じだった(結局ドローンは使ってなかった)

発表

5分程度で成果物を発表しました.

「ターミナルからニコニコ動画検索したいですよね」という出だしで適当に発表した. あんまり人前で成果物を発表するのに慣れてなかったのですごく簡単な紹介しかできなかったのですが もっと準備して詳しく説明できれば良かった...

他の人の発表

  • はてなブックマークの未読を無くすアプリケーション
  • はてぶのコメントを画面上に流すアプリ
  • ニコニコのコメントのみからその動画を当てるクイズアプリ
  • ニコニコ静画から機会学習を使って俺の嫁探しできるアプリ
  • ツイッターの友達のはてなブックマークから友達がどんな記事を読んでるか分かる便利アプリ

などなどありました. 皆ユーモアも技術力もある作品作ってて面白い! 自分ももっと面白いものを作りたい!

まとめ

他の参加者の方だけでなく はてなドワンゴのエンジニアの方ともかなり交流できて凄く楽しかったです! またこういうハッカソンがあったら是非参加したいです.

主催である はてなさん・ドワンゴさん ありがとうございました!