しゅういちのぶろぐ

活動記です．アウトプットにも使う予定です．ジャンルは多岐にわたる予(ry．

セキュリティキャンプ2018 応募用紙

はいどうも，しゅういちです．何か世界線を間違えてしまったのか，バグが生じてセキュキャン データベースゼミ(定員2名)に通りました．

そのため，毎年恒例らしい(？)応募用紙晒しをしていきたいと思います．あまり参考にならないと思いますが，自分みたいに技術的に強くないけど面白そうだし申し込むか悩んでいる...という人の背中を押せると嬉しいです．

きっかけ

以前よりセキュリティや低レイヤには興味があり様々な本(ハリネズミ，OS本，ハッカーの学校など)を買っていて，1年前にTwitterで募集を見かけたのが参加のきっかけでした．
興味が沸いた理由として，セキュリティや低レイヤって名前だけですでにかっこいいと思いませんか？僕は思います．ハッカーかっこいい(ホワイトじゃないとだめ) だがしかし競プロ(の沼)にハマっていったりしていてあまり勉強できていません...
こんな感じに面白そうだと思った分野を色々とふらふらしていますが，面白いって思えることに対して懸命になれるってのはいいことじゃないかなって思います．

今年も開催されることを知り，コースで面白そうなものがないかな...って調べていた時に目が惹かれたのがこのデータベースゼミでした． アルゴリズムやデータ構造が大切というワード+トランザクション処理がすごいと興味が沸いたのが理由でした．

応募用紙を書く上での方針

そんなこんなで興味を持ったはいいものの，「自分なんて弱いしどうせ...」と思いながら問題を見ていくと，

たくさん時間をかけて完璧な答えを作る必要はありません．

調べる過程で分かったことだけでなく，分からなかったことや疑問に思ったことも書いてください．

また，参考にした書籍や Web ページについては全てリンク等を書いてください．

とのことでした．
このときの僕「これもしやワンチャンあるのでは...？」
いろんな情報を参考にしてもいいのなら，実力のない自分でも応募用紙を書きつつインプットをしていけば，受かる可能性があるのでは...？と思いました．

こうしたことから，応募用紙を書く際，

  • 知識など大まかなものは一定度信頼できるネット記事から引用(内容を噛み砕きながら)．

  • 自分の中で噛み砕いた内容を文章に反映させて，それに関する自分なりの考えを示す．

  • 自分に技術や知識が足りないことは自明なので，代わりに熱意や興味の強さが伝わるよう文章を工夫する．

  • 講師の先生のメッセージからどのようなことを期待しているのか想定し，それに沿うような文章を作る．

ということに気をつけました． というわけで，ここまでがどうでもよくて，ここからが本編．

問題1

問題文

ACID (atomicity, consistency, isolation, durability) について説明してください．

解答

ACIDとは，信頼性があるトランザクションシステムの持つべき性質として定義されたもので，Atomicity(原子性)，Consistency(一貫性)，Isolation(独立性)，Durability(永続性)の略称である． まず，トランザクションとはデータに対する１つの一連の操作のことである． 原子性は，トランザクションに含まれるタスクが全て実行されるかあるいは全く実行されないという性質である．ある1つだけ実行されると矛盾が生じる危険性があるからだ． 一貫性は，そのデータベース内で一貫したルールをトランザクション開始と終了時に満たしているという性質である．現実に存在しない値があると矛盾が生じてしまうからである．例えば口座残高がマイナスになることはありえない． 独立性は，トランザクション中の操作の過程が外部から隠蔽されていることである．他の操作と分離することでセキュリティを高めていると思われる．ところが並列処理をすると独立性から外れてしまうが，そうしないと処理速度が遅くなるので実用性と独立性をいい塩梅で実装することが大事である． 永続性は，トランザクション終了時点でその操作が永続的となりその後結果が失われないことである． https://ja.wikipedia.org/wiki/ACID_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E7%A7%91%E5%AD%A6) https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E5%88%86%E9%9B%A2%E3%83%AC%E3%83%99%E3%83%AB

補足

Wikipediaからの引用は信頼度が高いとは言えないので，あくまでアイデアの参考程度にして引用は避けた方が良いと思います．少々自分らしく書き直していますけどだいたいそのままです． トランザクションを実生活で全く気にしていなかったので，概念を知ったときはすごく感動しました．

問題2

問題文

Python の threading と multiprocessing パッケージの違いについて説明してください．
その違いが分かるような簡単なプログラムを書いて動かしてみて,結果を教えてください．

解答

Threadingは今あるプロセス内で複数のスレッドを立ち上げるが，Multiprocessingは今あるプロセスとはまた別のプロセスを新たに立ち上げて処理を行わせる．それぞれスレッドとプロセス単位で並列処理をしているという違いがある．以下にそれぞれの簡単なコードとその実行結果を示す．

(Threadingの場合)

import os
import threading
MAX_COUNT = 100000
ITERATION = 50000
def whoami(what):
    # 単純な加算
    count = 0
    for n in range(MAX_COUNT):
        if count % ITERATION == 0:
            # 実行中のプロセスIDと,現在のcount数とスレッドナンバーを表示
            print("{} Process {} thread= {} count {}".format(
                what, os.getpid(), threading.current_thread(), count))
        count += 1
    # どのスレッドが終了したかを表示
    print("end {} Thread {}".format(what, threading.current_thread()))
# 現在のプロセスのidを表示
print("Main Process ID is {}".format(os.getpid()))
# メインのプロセスで実行
whoami("main program")
for n in range(5):
    p = threading.Thread(target=whoami, args=("Thread {}".format(n),))
    p.start()
    P.join()
print("end of program")

(Multiprocessingの場合)

import os
import multiprocessing
MAX_COUNT = 100000
ITERATION = 50000
def whoami(what):
    # 単純な加算
    count = 0
    for n in range(MAX_COUNT):
        if count % ITERATION == 0:
            # 実行中のプロセスIDと,現在のcount数を表示
            print("{} Process {} count {}".format(what, os.getpid(), count))
        count += 1
    # どのIDのプロセスが終了したかを表示
    print("end {} Process {}".format(what, os.getpid()))
# 現在のプロセスのidを表示
print("Main Process ID is {}".format(os.getpid()))
# メインのプロセスで実行
whoami("main program")
print("-----------------------------------------------------")
# プロセスを5作りスタートさせる.
for n in range(5):
    p = multiprocessing.Process(target=whoami, args=("Process {}".format(n),))
    p.start()
print("end of program")

(Threadingの実行結果)

Main Process ID is 47452
main program Process 47452 thread= <_MainThread(MainThread, started 140736268198784)> count 0
main program Process 47452 thread= <_MainThread(MainThread, started 140736268198784)> count 50000
end main program Thread <_MainThread(MainThread, started 140736268198784)>
Thread 0 Process 47452 thread= <Thread(Thread-1, started 123145442807808)> count 0
Thread 0 Process 47452 thread= <Thread(Thread-1, started 123145442807808)> count 50000
end Thread 0 Thread <Thread(Thread-1, started 123145442807808)>
Thread 1 Process 47452 thread= <Thread(Thread-2, started 123145442807808)> count 0
Thread 1 Process 47452 thread= <Thread(Thread-2, started 123145442807808)> count 50000
end Thread 1 Thread <Thread(Thread-2, started 123145442807808)>
Thread 2 Process 47452 thread= <Thread(Thread-3, started 123145442807808)> count 0
Thread 2 Process 47452 thread= <Thread(Thread-3, started 123145442807808)> count 50000
end Thread 2 Thread <Thread(Thread-3, started 123145442807808)>
Thread 3 Process 47452 thread= <Thread(Thread-4, started 123145442807808)> count 0
Thread 3 Process 47452 thread= <Thread(Thread-4, started 123145442807808)> count 50000
end Thread 3 Thread <Thread(Thread-4, started 123145442807808)>
Thread 4 Process 47452 thread= <Thread(Thread-5, started 123145442807808)> count 0
Thread 4 Process 47452 thread= <Thread(Thread-5, started 123145442807808)> count 50000
end Thread 4 Thread <Thread(Thread-5, started 123145442807808)>
end of program

(Thread(p.join()なしの場合)の実行結果)

Main Process ID is 47410
main program Process 47410 thread= <_MainThread(MainThread, started 140736268198784)> count 0
main program Process 47410 thread= <_MainThread(MainThread, started 140736268198784)> count 50000
end main program Thread <_MainThread(MainThread, started 140736268198784)>
Thread 0 Process 47410 thread= <Thread(Thread-1, started 123145563901952)> count 0
Thread 0 Process 47410 thread= <Thread(Thread-1, started 123145563901952)> count 50000
Thread 1 Process 47410 thread= <Thread(Thread-2, started 123145569157120)> count 0
end Thread 0 Thread <Thread(Thread-1, started 123145563901952)>
Thread 3 Process 47410 thread= <Thread(Thread-4, started 123145579667456)> count 0
Thread 1 Process 47410 thread= <Thread(Thread-2, started 123145569157120)> count 50000
Thread 4 Process 47410 thread= <Thread(Thread-5, started 123145584922624)> count 0
Thread 2 Process 47410 thread= <Thread(Thread-3, started 123145574412288)> count 0
Thread 4 Process 47410 thread= <Thread(Thread-5, started 123145584922624)> count 50000
end of program
end Thread 1 Thread <Thread(Thread-2, started 123145569157120)>
Thread 2 Process 47410 thread= <Thread(Thread-3, started 123145574412288)> count 50000
Thread 3 Process 47410 thread= <Thread(Thread-4, started 123145579667456)> count 50000
end Thread 4 Thread <Thread(Thread-5, started 123145584922624)>
end Thread 2 Thread <Thread(Thread-3, started 123145574412288)>
end Thread 3 Thread <Thread(Thread-4, started 123145579667456)>

(Multiprocessingの実行結果)

Main Process ID is 47403
main program Process 47403 count 0
main program Process 47403 count 50000
end main program Process 47403
-----------------------------------------------------
Process 0 Process 47404 count 0
Process 1 Process 47405 count 0
Process 2 Process 47406 count 0
end of program
Process 0 Process 47404 count 50000
Process 1 Process 47405 count 50000
Process 2 Process 47406 count 50000
Process 3 Process 47407 count 0
Process 4 Process 47408 count 0
end Process 0 Process 47404
end Process 1 Process 47405
Process 3 Process 47407 count 50000
Process 4 Process 47408 count 50000
end Process 2 Process 47406
end Process 3 Process 47407
end Process 4 Process 47408

実行時間はそれぞれ0.167s, 0.159s, 0.183sであった． Threadingの場合，processは1つのみ立ち上がっており，その中で5つのthreadが立ち上がっているのが確認できた． p.join()がない場合，end of programが途中に出力された．ある場合はそれぞれ順番にスレッドが立ち上がり，その処理が終了すると次のスレッドに移行していく様子が確認できた． Multiprocessingの場合，processは5つ立ち上がっているのが確認できた．プロセスは同時に最大３つ立ち上がり，3つが並行で処理されていく様子が確認できた． Multi processingだとそれぞれのプロセスで処理が同時に行われていく様子から，処理を分散できているのが確認できたが，Threadingだと終了の出力のみ並列してそれ以外は順に行われていて，いまいち高速化されたのか今回のコードではわかりにくかった． また，MAX_COUNT = 100000000，ITERATION = 50000000かつrangeを20，つまりプロセスやスレッドを20にしてローカルで実行した結果，Threadingでは4m24.323s，Multi processingでは2m44.896sとMulti processingの方が効率が倍以上異なった．これより，大きな処理の場合はMulti processingの方を選択すべきだと考えられる．しかし，Multi ProcessingだとPCのファンがかなり音を立てていたので，エネルギーを急激に消費しているのではないかと考えられる．

https://qiita.com/ogihara/items/1b7f002b7d14a2710bce http://d.hatena.ne.jp/torasenriwohashiru/20110528/1306594075

補足

ここはかなり難しかった記憶があります． コードそのものは完全に引用で，考察もこれらのサイトに頼りきりになっていました．

この問題を通して，これまでより一段スレッドとプロセスの違いがわかった気がします． 上記の詳細やコードの意味がわからない場合は，リンク先に飛びましょう．

問題3

問題文

次の中から 2 つ選んで説明してください． 3a. データ構造としての Hash table と Tree の違いについて．

3b. pthread_mutex_lock() と CAS 命令等を使って作る spinlock の違いについて．

3c. Write-ahead Logging (WAL) について．

3d. Strict Two-Phase Locking (S2PL) について．

3e. Deadlock と Starvation について．

解答

3aと3cを選びました．

3a

Hash tableとは，キーを持つデータ集合に対して，動的な挿入，検索，削除を効率的に行うことができるデータ構造の一つである．ハッシュテーブルはm個の要素を格納できる配列Tと，データのキーから配列の添字を決定する関数(ハッシュ関数)から構成されている．以下のように実装できる． def insert(data): T[h(data.key)] = data def search(data): return T[h(data.key)] ハッシュ関数はハッシュ値が0..m-1(mは配列Tのサイズ)をとるように実装する．この条件を満たすためには，剰余算を使い出力値が必ず0..m-1の整数になるようにする．例えば， h(k) = k % m を使うことができるが，このままだと異なるkeyが同じハッシュ値になる衝突が起きる可能性があるので，回避するためにダブルハッシュを用いたオープンアドレス法がある．次のようにハッシュ関数を定義する． H(k) = h(k, I) = (h_1(k) + i * h_2(k)) % m このハッシュ関数h(k, i)はキーkに加えて，整数iを引数としている．このiは衝突が発生して次のハッシュ値を計算した回数を表している．つまり，ハッシュ関数H(k)は，衝突が起きる限りh(k, 0), h(k, 1), h(k, 2), …を計算し，衝突が起こらなかった最初のh(k, i)をハッシュ値として返す．計算量は衝突しない限りO(1)となっている．また配列を大きくとるため，空間計算量は大きくなる．しかし，要素の挿入・削除にはO(n)の計算量がかかる．

Treeとは，節点(node)と節点同士を結ぶ辺(edge)で表されるデータ構造である．Treeの一種であるBinary Treeは1つの根を持ち全ての節点についてその子の数が2つ以下の木である．計算量がO(log n)で行え，メモリを多めにとっておく必要がない．実装としては，各節点が親と子に対するポインタを持った構造体であることが多い．他にもヒープと呼ばれる配列を使った木構造で実装されることもある． まとめると，Hash tableは剰余算を使ってO(1)でアクセスできるような配列で，TreeはO(log n)でアクセスできる構造体あるいは配列である．参照するだけならHash tableが効率がよく，挿入，削除をする場合はTreeの方が効率がいい．

[プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 渡部 有隆 著，Ozy，秋葉 拓哉 協力(マイナビ出版) p.127~130, 186~187] http://d.hatena.ne.jp/yohei-a/20120130/1327887478

3c

Write-ahead Logging (WAL)とは，ログ先行書き込みと呼ばれるもので，トランザクションをコミットする前にその全てのデータ更新を逐一ログに書き出し，データベースの更新はそれをまずログに書き出してから行うというものである．これは，トランザクションを障害から守るためにログを記録するが，先にデータベースを更新してその後ログを記録する前に障害が起きてしまったら，ログに書き込もうとしていた情報が消えてしまい，再起動時にデータベースに対してその更新をREDO, UNDOする手掛かりがなくなってしまう．そのため，コミットする前にログに書き込むことが必要となる．

[リレーショナルデータベース入門 第3版 増永 良文 著(サイエンス社) p.276~277]

補足

とりあえずググってみて，すぐに説明ができそうなものと，競プロでよくあるデータ構造について解答しました．自分にとってわかりにくいものやあまり興味がわかないものは極力避けました． Treeの説明雑いなぁとか思いながら解答していましたが，提出期限ギリギリだったので許してくださいって感じです．

WALは言われてみればそうだなぁという感じです．gitのようなバージョン管理ソフトと本質は同じだと思います．ただ任意でrebaseできない(できないですよね？)などの違いはあると思います． リレーショナルデータベース入門 第3版は大学の図書館にありました．これから頑張って読んで勉強します...(追記: 結局そこまで読まなかった気がします...)

問題4

問題文

あなたの興味,経験,能力について自由に書いてください．

解答

弱くて恥ずかしいので割愛．

補足

とりあえず，DBについて興味があり，その中でも「たまたま」講師の方と同じトランザクションについて興味があったのでそれについて述べたり，競プロが好きなので(レート800程度の雑魚)そのことを述べたり，最近Web系を勉強している(PHPでインターンに参加している)ので，それ関連について述べたりしました．

一応自分が触れるのは(=ある程度コードが読めて，ググりながらなら書ける)C，C++，C#，PHPとかです．DBはMySQLぐらいです．この程度の技術力です．

今回応募することで得た知見

  • とりあえずでも，自信がなくてもチャレンジすることは大事，別に何かが減るわけではないので．

  • 応募用紙を書くだけでも知識は身につく．

  • 期限があるので，タスク管理には気をつけよう．

結論

本当どうして通った？！？！！

大学生のためのCiNet研究ワークショップに行ってきました(今更)

3/13

概要

約1ヶ月前なんですが，大学生のためのCiNet研究ワークショップに行ってきました．

今更ですが，メモしてたのと，アウトプットとモチベ向上と来年以降気になってる人がいた時のために書き連ねようと思います．
CiNetとは脳情報通信融合研究センターの略で，日本で最先端の研究拠点の1つです．すごい．


7TのMRIと3TのMRIが2つとか合わせて4つあってしかもまた今度導入するとか言ってたし，MEGも2つあるとか本当総務省狂ってやがる(褒め言葉)．どんどん科学技術にお金使っていこうな！

スケジュールや詳細はこちらです．

研究講演について

おもろい研究をしよう！

柳田敏雄センター長のお話．個人的に1,2を争うくらいおもろい話だった．ワクワクしながら話聞いてた．

ヒトの体や脳ってゆらぎを用いてすごいことしてるんだよっていう話．まず，ヒトの脳の消費エネルギーが1Wって聞いてすごいってなった(平静時と思考時の差)．昔のアルファ碁の消費エネルギーは20万Wだったらしく，理由としてはノイズ除去のために無駄なエネルギーを使ってしまうかららしい．
他にもミオシンがブラウン運動によって構造変化させていたりと，ゆらぎってすごいんだよって話してた．ゆらぎすごい．
次に少し話変わって，脳はAIと違って少量のデータセットで学習できるという話．5つくらいのデータセットでできるらしい．これは「ひらめき」が関係しているのではないかと注目したらしい．しゅごい．ひらめき，直感の例として，隠し絵を使った実験をしていた．それによると，隠し絵の探索時間は対数正規分布に従うらしい．これはつまり，ひらめきの反応が分子反応と等価であり，かつアレニウスの式と等価であるのではないかと言っていた． そして，ひらめきには閾値があって，それが小さい人にはひらめきにくいのかもしれないと推測していた．

計算モデルによる社会行動の脳メカニズムの理解

これは春野雅彦先生が講演していた．個人差の神経メカニズムを解明，制御することを目的としているらしい．fMRIとBDIのスコアを用いて脳状態から鬱状態の推測，および1年後の鬱状態も予測できたらしい．結論としては，格差に対した海馬・扁桃体の活動パターンから1年後のBDIスコアは予測可能らしい．今までは利己的だと考えられる古い脳の皮質下領域を前頭前野によって抑えるとされてきたから，そういったアプローチが変わっていくのかもしれない．他にも社会的実験として，Twitterを使った実験もしていた(これに関するツイートが少しバズった)．

他にも様々な講演があったがしかし詳細は省く．
なお途中でこうなっていた．

Q&Aコーナー

こんなものが挙げられていた．

  • Q．CiNetってどうやって入るの？ A．CiNetには入学できないが，大阪大学と連携している
  • (質問内容忘れた)NICTのラボは小さいが，交流が盛ん
  • (上に同じ)ドクターになるなら，ある分野で一番になってほしい（新分野開拓や既存の分野で勝ち抜く）
  • (上に以下略)研究が好きでとにかく研究したいと強く思うならなんとかなる
  • (確か卒業要件的な話)生命機能は英文の論文1本が好ましい（内容重視）
  • (わからん)ラボによって異なる
  • (確かCiNetでの論文投稿頻度の話？)研究員レベルだと1年で1本
  • (わからんけどそれはそう)神経科学を全部は無理
  • (すごい)CiNetだと講演会が多くて情報を集めやすい
  • (すごい！)共同研究などで学べる環境
  • (わからん)バーチャルリアリティを皮膚の下でやる→神経信号
  • Q．今一番必要なものは？ A．センシング技術がブレークスルーが必要

ポスターセッション

「経済的不公平に起因する脳活動パターンを用い、うつ病傾向の変化を予測する」と「脳活動を解読する」と「SNSの使い方と脳活動の関連性」のセッションを聞いていました．つい話し込んでしまうこともありましたが，その時進路相談やアドバイスをもらえ，すごくよかったです．それぞれの内容は省略．Neuroscience関連の論文を調べるときは，NCBIのPubMedやGoogle Scholerがおすすめらしい．

交流会

寿司と酒とオードブルとピザがあってマジ最高だったし，参加していた学生の方達と仲良くなれたし，研究員の方々と仲良くなれてすごくよかった．

まとめ

普段モチベが低くても，とてもテンション上がるので，脳研究に興味がある人はワークショップおすすめです！！

RUPC2018に行ってきました

プログラミング 競技プログラミング

はじめに

皆さんこんにちは．しゅういちという者です．RUPC参加者はブログをあげるのが通例であり，
またブログを普通に書いてみたかったので今回書いてみました．
今後も色々と書いてみたいものがあり次第書いてみようと思います．

RUPCってなぁに？

一応RUPCについて説明を．RUPCとは立命館大学プログラミングコンテストのことで，
日本全国の暇な競技プログラマーが鎬を削ったり削らなかったりして， 楽しんでプログラミングを行う大会です．
競技プログラミングについてはAtCoderなどをご参照ください．

今回僕は3日とも参加したので，それぞれについて述べていこうと思います．

1日目

コンテスト

1日目は立命館大学セットでした．時間は03:00で問題はA~Gまでの7問ありました．
まぁ？僕はレート的に？あの場での最弱だったので？チームメンバーとの相談の結果A問題を解くことになりました．
A問題は灰色レートの僕でも解けるような問題だったので，00:19AC(Accepted)．
残りの時間は椅子を温めていました．
チームとしては5完で22位でした．皆さん強い．僕も精進しないと...

懇親会

基本ぼっちでうまいうまい言いながらオードブルみたいな感じの肉を食べたりしてました． (ぼっちつらい)
途中で同じ境遇(？)の方などと一緒に話すことができて普通に楽しかったです．
sushiがなくて残念でした．

2日目

コンテスト

2日目は会津大学セットでした．時間は05:00で問題はA~Mまでの13問(？！)ありましたやばいすごい． 僕は最底辺なのでとりあえずA問題を解きました(00:12AC)．
その後チームの方にC問題の本質を教えて頂き，Cを通しました(01:02AC)． 他は今回は頑張ろうとしてDとGについて考えましたが，結局わからず．
WA生やしまくって結局解けず戦犯感がすごかったです．
チームとしては4完で41位でした．

懇親会

その後焼肉に行ってきました．肉と酒は正義．
同じテーブルだった強い人たちが今春から大学生とのことでアヘー(死)となってました．
2日目の懇親会も楽しかったです．

3日目

コンテスト

3日目は北海道大学セットでした．時間は03:00で問題はA~Gの7問ありました．
僕は最t(ry，A問題を解きました(00:10AC)． その後要介護されつつD問題を解きました(まだあまりわかっていない)(01:44AC)．
そこからは椅子を温めてました． チームとしては5完で31位でした．

まとめ

オンサイトコンテストは初めてで，どうなることやらと思ってましたが， 終わってみると非常に良いものでした．
時間も長丁場で2,3日目は本当につらかったですが，†忍耐力†がついたかなと思います．
またコンテスト中もAを解く速度が速くなっており，成長を実感できてよかったです．
次もオンサイトコンテストに出れる機会があれば積極的に参加したいと思いました．
とりあえずAC埋めをして強くなりたいです．
競プロはいいぞ