読者です 読者をやめる 読者になる 読者になる

私が歌川です

@utgwkk が書いている

THE IDOLM@STER CINDERELLA GIRLS 5thLIVE TOUR Serendipity Parade!!! 石川公演に行った

物販ですが,森久保セットが売り切れたのでTシャツを買いました.

http://idolmaster.jp/event/cinderella5th/information.php

いろんな感想があった.光る棒を振り回しながら叫ぶのは楽しいですね.

声優の顔と名前が一致しないので心配だったが,歌ってるところを見たらだいたい分かるようにはなっていたのでよかった.

次回予告

THE IDOLM@STER CINDERELLA GIRLS 5thLIVE TOUR Serendipity Parade!!! 静岡公演に行きます*1

おわりに

風邪ひいた.

*1:kebus せんせーにそそのかされた.乙倉くんがいるので見に行きます

「Twitter で流れてきた画像付きツイートにいいねをすること」雑感

部員向け情報

2015年の例会講座の「PythonQOLを向上させる方法」みたいなタイトルのスライドを見てください.

utgwkk.hateblo.jp

Twitter で流れてきた画像付きツイートにいいねをする行為を,まだ「いいね」が星だった頃から数えると,もう5年以上やりつづけていることになる.

表明としての「いいね」

さて,いろいろな意見があるがそうはいってもやはり,人は数字につられるし,数字が大きいとうれしくなる*1. いいものがいいものであると表明できる場があるとよいし,数字をインクリメントさせるという行為が手軽にできるサービスほど,表明をやりやすい. 我々はしばしば表明がしたい.それはあらゆる形をとって出現しうるだろう.

隠れファンとして機能していた「いいね」

Twitter のいいねは,かつてはタイムラインには何も流れないものだった. それは私にとってはとても都合のよいことであった. 画像付きツイートをいいねするという行為には,当然いいねする側の趣味が大きく反映され,時としておおっぴらにしたくないときもある. リツイートとはまた違った,こっそりとした表明に私は喜びを得ずにはいられなかった.

いつだったか忘れたが,いいねがタイムラインに通知されるようになった. 私自身は他人のいいね通知は見ないのだが,自分のが流れていくとなると話は別である. たとえば,自分のいいねしたツイートが流れた結果,場にふさわしくない画像が相手のタイムラインに表示される可能性が大いにある. こっそり表明したい,と思っていたものが筒抜けになるというのは,ずいぶんと恐怖感のあるもので,しかしもう慣れてしまったのだが,やはりかつてのような隠れとしての機能はないのだ,と思うと寂しい.

趣味嗜好の地層

「いいね」には,人の嗜好が現れる.

私は一昨年の10月ぐらいから,Twitter でふぁぼった画像付きツイートを Slack に流し,サーバーに保存する BOT を動かしている. 各種メタ情報も同時に保存するようにしており,ある程度は検索することができる. これを遡っていると,まるで地層を見ているような気分になることがある. 人の嗜好は変わりやすかったり変わりにくかったりする. ある地点から急にこのジャンルの画像を保存するようになったとか,ずっとこのジャンルの画像は保存しているとか,そういうことである. ここにもう一つコードがちょっと書けることの喜びという側面が出てくる. 昔は手作業でやっていたことを BOT に全部任せられるようになり,私はいいねをするだけで全てが済むようになった. とにかく楽をしたいという気持ちを満たすことができる. ところで,BOT を書いた後には,BOT をメンテナンスするという行為があるのだが,それはまた別の話である.

私は記憶の持たないほうなので,何か外部媒体に記憶を任せないと,すぐに空白期間が生じてしまう. 地層が外部媒体として機能するようになっている今では,私は懐しみを感じるのに少々の労力しか必要としない. そうして,悶々とすることも少なくなっていくだろう. 私は溢れる情報に自分を繋ぎ止めなければ,存在が認知できなくなるような,そういう気持ちを持っている.

gyazo.com

可視化されることで初めて分かってくることもある.

意見

Twitter は早く自分のいいねの通知を流さないように設定できるようにしてほしい. 私は隠れファンのつもりで「いいね」をしており,「いいね」をアカウントとひもづけて大々的に表明していくつもりはない. TPO的なあれそれもある.

よく,「いいね欄はムッツリなんだろう」ということを言われることがあるのだが,いいね欄ぐらい好きにさせてほしいし,好きで通知しているわけでもない. 通知しない別の方法で保存する,となると,これはなかなかの課題になる.

私のことをフォローしてくれていて,何もそういうことを言わないということは,つまりいいね通知が見えていないか,別に気にするほどでもないと思っているかのどちらかだと思うようにしている.

*1:符号を付ければ小さい場合にも一般化できます.

ソートマージ結合法を実装してみた

関係データベースの本を読んでいて,結合質問を処理するアルゴリズムのソートマージ結合法について知ったのですが,動作例だけでアルゴリズムが書いてなかったので,実装をしました.

結合質問とは

テーブルRとSがあって,それぞれ行数がMとNであるとします.みなさんもこういう SQL クエリを書いたことがあると思います.

SELECT R.hoge, S.fuga FROM R
INNER JOIN S ON R.id = S.hoge_id

「テーブル R と S のデータのうち, R.id = S.hoge_id を満足する行の組を結合したもののみを返せ」という意味のクエリです. たとえば,テーブル R が以下のようになっているとします.

id hoge
1 “a1”
2 “a2”
3 “a3”
4 “a4”

また,テーブル S が以下のようになっているとします.

hoge_id fuga
1 “c1”
2 “c2”
2 “c3”
3 “c4”

これらのテーブルに対して上のクエリを実行した結果は次の通りになります.

hoge fuga
“a1” “c1”
“a2” “c2”
“a2” “c3”
“a4” “c4”

ところで,これ以降はテーブルの全てのカラムを取得するときのみを考えることにします.

総当たり法

さてこのクエリに答えるにはどうすればよいかを考えるのですが,すぐ思いつくのは総当たり法でしょう. したがって,たとえばこのような実装が考えられます.

def brute_force(R, S):
    result = [] # 回答を格納するリスト
    for r in R: # R の全ての行 r について
        for s in S: # S の全ての行 s について
            if r[-1] == s[0]: # (r の結合属性の値) == (s の結合属性の値)
                result.append(r + s) # r と s を結合したものを回答に加える
    return result # 回答を返す

しかしながらこの方法は計算量が O(MN) となるので,テーブルの行数が大きくなると実用的な時間でクエリに答えることができなくなります*1

ソートマージ結合法

ソートマージ結合法 (Sort-merge join) は,総当たり法よりも高速に結合質問に答えるためのアルゴリズムです.実装したコードを下に示します*2

def sortmerge(R, S):
    M, N = len(R), len(S) # テーブルRとSの行数
    p1, p2, p3 = 0, 0, 0 # 3つのポインタ.p1 は R,p2 と p3 は S の先頭を指す.
    result = [] # 回答を格納するリスト
    while p1 < M and p3 < N: # p1 が R の終端を指す,もしくは p3 が S の終端を指すまで
        if p2 >= N: # p2 が S の終端を指しているなら
            p1 += 1 # p1 を進める
            p2 = p3 # p2 を p3 に戻す
        else:
            if R[p1][-1] < S[p2][0]: # (R[p1] の結合属性の値) < (S[p2] の結合属性の値)
                p1 += 1 # p1 を進める
                p2 = p3 # p2 を p3 に戻す
            elif R[p1][-1] == S[p2][0]: # (R[p1] の結合属性の値) == (S[p2] の結合属性の値)
                result.append(R[p1] + S[p2]) # R[p1] と S[p2] を結合したものを回答に加える
                p2 += 1 # p2 を進める
            else: # (R[p1] の結合属性の値) > (S[p2] の結合属性の値)
                p3 += 1 # p3 を進める
                p2 = p3 # p2 を p3 に合わせる
    return result # 回答を返す

計算量は,RとSが共にソート済みであるとすると O(M + N) となります*3

まとめ

ソートマージ結合法を知りました.

アルゴリズムの紹介をするならせめて疑似コードを書いてほしい.

*1:実際にはインデックスが貼られていることが多いので,もう少し高速にはなると思われます.

*2:R と S が昇順にソートされているという仮定をしています.

*3:ソートが必要な場合でも O(MlogM + NlogN) となります.

SQLite で ORDER BY RANDOM() を使わずに10連ガチャを実現する

tl;dr

  • WITH RECURSIVE で主キーの乱数列を作って絞り込むと爆速

ナイーブな実装

SQLite でガチャを実装しようとすると通常次のようになるかと思われます.

SELECT * FROM idols ORDER BY RANDOM() LIMIT 10;

よく知られているように,このクエリは非常に重いです.45万件ほどのデータに対してこのクエリを投げると,結果が返ってくるまでに待たされることが多いです.

WITH 句で乱数列を生成する

WITH句でとりあえず仮想的な一時テーブルのようなものを作っていると考えてください.rowid はテーブルの主キーとします.

WITH random_id(id)
AS (
  SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols))
  UNION ALL SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols)) FROM random_id
)
SELECT DISTINCT id FROM random_id LIMIT 10;

これによって,0〜MAX(idols.rowid) の範囲をとる乱数列が生成できます.

rowid の乱数列で絞り込む

あとはこれを組み込んでみましょう.

WITH random_id(id)
AS (
  SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols))
  UNION ALL SELECT ABS(RANDOM() % (SELECT MAX(rowid) FROM idols)) FROM random_id
)
SELECT * FROM idols JOIN (SELECT DISTINCT id AS rid FROM random_id LIMIT 1000) ON idols.id == rid LIMIT 10;

こうして爆速の10連ガチャを実装することができました.よかったですね*1

注意

  • 主キーが連番になってないときの動作は保証しません
  • 追記したのですが, WHERE id IN (SELECT DISTINCT id FROM random_id LIMIT 100000) による判定では偏りが出てしまいます.これは random_id の取得数を減らすか,もしくは上の修正されたクエリのように JOIN を使うことによって解決できるようです

おまけ: rowid について

SQLite のテーブルには必ず rowid という INTEGER PRIMARY KEY AUTOINCREMENT があるので*2,主キーを設定するの忘れてた……というときにも使うことができます. この主キーは隠しカラムであり,これを元にして主キーを再設定することができます.

*1:部内のガチャシステムが40倍高速になりました

*2:実は INTEGER の主キーはこれを参照している

今日の夢日記

全くどういうことなのか分からないけど,「オブジェクト指向の部屋」「大麻常用ツイッタラー」というのがめちゃくちゃ印象に残っている.

英語でのコーディング面接の感想

機会があって英語でのコーディング面接を受けることがあったので,終わってから感じたことを書き留めておく.

感じたこと

話せる語彙が少ない

読める/聞ける語彙はそこそこあって,ゆっくり話してもらえれば聞き取れるし,意味も分かるけど,自分が話を組み立てるという段階になって分かることとして,話せる語彙が思ったより少ない,ということがある. また,使う単語はそんなに難しいものではないけどイディオムとして知らないので話せない,みたいな表現もけっこうあって,話せることがどんどん減るのがつらかった.

情報工学的な英語表現ができなかった

「時間計算量は入力長を N として N の2乗に比例します」という表現が言えなくて complexity is order square N と言っていた. また,書いたコードの説明をするにあたって,解答コードを Python で書いたのだが,Python のコードをそのまま読み下すような説明をしてしまい,かなり時間を消費してしまった. 擬似コードに落とし込んだような表現ができればもっとスムーズに進められただろうなと思う.

その他

  • はきはき喋る
  • もうちょっと事前準備をして話のネタを用意しておく.前日にちょっと予想しただけで終わった話題がそのまま出た
  • コードが合ってたかどうか不安になってきた*1*2
  • コーナーケースの指摘をさらっと流してしまったのはよくなかった

まとめ

見返してみると,「英語は難しい」では済まされないレベルの英語しか話せなかったし,その結果,日本語なら難なくできるであろうことが大きく制限されてかなり不利になってしまったように思う. 普段使ってないからだとか,ちゃんと勉強してないからだとか言われると,確かにそうとしか言えない. 言語のために普段できることができなくなるのは非常に悔しいのでなんとかしたいですね. 院に進学するならどうせ TOEIC とか必要になるだろうし,ぼちぼちやっていく必要がある.

*1:あとでちゃんと書いたところそれっぽい挙動をしているので,書き間違えてなければセーフ

*2:これは試験後のよくあるあれなので,あまり気にしてはいけないと思う