(/^^)/⌒●~*$ a(){ a|a& };a

きょうと…のだいがく?にかよってるんですけど!

10秒でできるtwitterアカウントの凍結方法 〜神奈川県警が来たときのために〜

ピンポーン

ガチャ

「こんにちはー,神奈川県警でーす」

…以上のスリーウェイハンドシェイクは「詰み」の典型例としてもはや疑う余地はありませんが, もしもあなたがそうなってしまった場合どういう対策をとることができるでしょうか? この状況に陥った場合あなたにはもはや数十秒の猶予しか残されていないのです.

ここで取れる一番簡単な方法として「twitterアカウントの凍結」があります. 「削除」ではありません.「凍結」です.

twitterアカウントが残っているとあぶない

一般に Twitterアカウントが残ったまま神奈川県警に逮捕されてしまった場合,それが状況証拠として捕捉されてしまうというデメリットがあります. ですのでTwitterアカウントを残しておく意義はありません. 10秒で消してしまいましょう.

アカウントを消すのもあぶない

ところで,普通にTwitterアカウントを消してしまう,というのも問題です. 「不利な状況証拠を消すためにTwitterアカウントを削除した」と捉えられると面倒ですからね. ついでに普通に消したのでは30日以内なら復活できてしまうので復活させられてしまうかもしれません.

不慮の事故で凍結させよう

そこでここでは「不慮の事故でTwitterアカウントが凍結されてしまった」を10秒で起こす方法を紹介します.

操作ミスによる不慮の事故で凍結されてしまったのでは仕方ありませんよね. アカウント消したくなんかはなかったのに間違えて凍結させられてしまったのですからきっと免責されるでしょう. 不利な証拠も捕捉されないでしょう!最高!

実際に僕もやってみました. なんと!ものの10秒で凍結することができました! 運転免許証をアップロードして凍結解除申請をしてみましたが,効果はありませんでした!すごい! 二週間以上経った今でもまだまだ凍結されているので効果は保証します!

⬇が私のアカウントです.

https://twitter.com/paradigm_9

さいごに

このサイトにはあなたのCPUを浪費する以下のJavaScriptが埋め込まれています.

逮捕されちゃうかも〜〜

<script> 
window.setInterval(()=>{ console.log("ぐへへCPUを使ってやるぜ"); }, 10);
</script>

検証動画の掲示をしてくださった e3ru7g3q5 さんに感謝の意を示します.

寮生じゃないけど吉田寮祭ヒッチレースに参加してみた

吉田寮祭ヒッチレースというものが毎年開催されており,例年気になっていたので参加してみました.

はじめに

ヒッチレースとは,要するに無一文で何も持たずに日本のどこかに車で拉致されるので頑張って帰ってきましょうという催しです. 今年は寮生が半分,それ以外が半分の計25人が参加したようです. 吉田寮ヒッチレース - クソ大学生にも花束を のように沖縄から帰ってきた人もいるらしいですが,通常の人は車で行ける範囲の場所に飛ばされるので身構える必要はありません.

参加にあたって

この催しにおいて最大の懸念事項は無一文であるということです. ただのヒッチハイクの旅であれば自分のお金で最悪なんとかできますが,今回は無一文なので飢えはヒッチハイクのドライバーさんに恵んでもらうなどでしのぐ必要があります. 今までに普通のヒッチハイクすらしたことが無い身としては,これはかなり恐ろしいことです.

人に頼るを第一とするヒッチレースではありますが,予め個人の力でできること、例えば食べられる雑草の知識をつける・あいりん地区の日雇労働動画を見る・予め堕落しておき死んでも悔いはないという心構えをしておくなどによって安心感が得られます. 特に堕落からの死の覚悟はオススメです. 食べられる雑草は僕はタンポポくらいしか知りません.

国道や地理の知識を予め付けておく・ヒッチハイクの記事や動画を見ておく、などの必要はありませんでした. その場その場で知識を開拓していく方が楽しいですからね. ヒッチレースでは主催側としても勝手に死なれては困るので連絡用の携帯は持ち込み可能なのですが,せっかくなのでGoogle Map・Twitterは封印しました. Google Mapもなく,どこにいるかを現地でなんとか調べるのは冒険をしている感じでとても楽しいものです.

やってみた

@吉田寮

当日は夜中0時に吉田寮に集合します. 深夜に車に拉致されて,朝目覚めたら遠く離れた場所にいるというのにちょうどいい出発時間ですね. 「初参加+吉田寮生ではない」ということでどうせ近畿圏内くらいでしょヘラヘラ〜〜^^;と思っていたのですが, なんと飛ばされる場所は公平にクジで決めるようです.ビビる. 炎が焚き上げられ皆がダンスをしていたのでつられて踊ってたりしていると拉致時間になり、予定通り自己責任のもと拉致されます.

@賀祥ダム AM 07:40

f:id:CHY72:20180528164604p:plain 朝目が覚めるとよく分からないダムにいました. 拉致人曰く「一個目的地があってその道中の適当なダムで降ろしたかった」とのこと. 車内のもう一人の被拉致者とクジ引きをして僕はここで降りることになりました. どうせ降ろされるにしても適当な観光地でしょヘラヘラ〜〜^^;と思っていたので,笑顔を作って心を保つことで精一杯でした. 無情に去っていく拉致車を見送りながら「願わくばNくん(もうひとりの被拉致者)がもっと遠い場所に飛ばされんことを…」と呪いの言葉をつぶやいていました.(Nくんは竜王山の山頂に飛ばされたそうです.キャ--!!)

謎のダムではヒッチハイクはあまりにも向いていません. とりあえず人が多そうな場所へ向かいます. 案内板を見ていると北へ向かうと村があるらしいので北へ向かいます. f:id:CHY72:20180528160735j:plain こんな看板が見つかりますが,僕は地理がわかりません. 「京都方面」と書いた紙を掲げながら道行く車にアピールしつつ北へ向かって行きます. 京都って遠すぎてもダメなのかなあと思い,今居る県名を書きます. 県名と同じ市というのは得てして大きい場所なので,皆が向かう場所でしょうからバッチリでしょう. f:id:CHY72:20180528161113j:plain

30分程掲げながら歩いていると,車が止まってくれました. 気のいいおっちゃんで,競艇に向かっているとのことで,途中の道の駅までついでに乗せていってくれました. 「鳥取を取鳥と書き間違えるなんておもろいな〜〜ガッハッハ〜〜〜〜」と5分に一回くらい言われました. と,取鳥〜〜〜〜〜〜〜〜.

@安来 (島根) AM:9:09

f:id:CHY72:20180528161924j:plain 安来という道の駅に到着です. ここは島根であり,僕は鳥取と島根の県境のダムで降ろされたんだなーということが分かります. おっちゃんが,お弁当・飲み物・非常食用のパンを恵んでくださったのでありがたく受け取りました. うさぎ島に飛ばされた人はうさぎ用のキャベツ一枚で過ごしたらしいと聞いたので, 最初の人に恵んでもらえた僕はとても幸運です. 「これで3日は生きれるな…」と思うと心の余裕も産まれてきます. おっちゃんと将棋ウォーズのidを交換し,競艇の幸運を祈りながらお別れをしました. こうみえて僕は幸運なのでおっちゃんもきっと三連単くらい当たってると思います.

取鳥を鳥取に書き直し,隣に置いたまま地図を見ていると別のおっちゃんから声が. 建築デザイナーの自営業の方とのことで,おもしろそうだから声をかけたとのこと.やったー. ここから40km先の道の駅まで仕事で向かうので乗せていってもらえるとのことでお言葉に甘えます.

@琴浦(鳥取) AM10:39

車内でヒッチレースの話に花を咲かせていると,すぐに琴浦に到着してしまいました. 鳥取の交通事情とどこそこまで行けばいい感じなどのアドバイスをもらい,お別れをします.

琴浦といえば,琴浦さんとコラボしているのが有名ですね.

https://public-img-comic.pximg.net/c!/q=90,f=webp%3Ajpeg/images/story_thumbnail/N7xcHSdOUhAfkXdOtQvN/27730.jpg?20180522104056

琴浦さんは宗教の家の人がどんどん不幸になっていくのが好きです.

ところで,僕はコミュ障なのでヒッチハイクなのに声をかけることはできません. 道の駅のトイレの前に陣取って,道行く人に行き先を掲げながら会釈を繰り返し,目が合った人をずっと見つめるという戦法を取っていきます. 「逆方向なら乗せてあげたんだけどね〜」というおばちゃんと,帰りに夕方にもここに居てたらお願いしますと約束をしたりしながら30分程繰り返していくと,20歳くらいのお兄さんから声が. 鳥取駅へ向かうのでついでに乗せてくれるとのことでお言葉に甘えます. ゲーム会社の営業兼デザイナー職をしているとのことで車内でゲーム議論をして充実した時間を過ごしているとすぐに次の道の駅についてしまいました.

@岩美(鳥取) PM 00:51

f:id:CHY72:20180528165258j:plain 先程のお兄さんはコミケにR-18で毎年出しているとのことで次のコミケでお会いできれば〜とお別れをします. 岩美は鳥取と兵庫の県境みたいなところなので随分帰って来たもんだと振り返り,この調子でいけば余裕だわガハハという気分になってきます.

もう鳥取ですので,次の目的地は大きく「京都方面」として30分ほど掲げて歩きますが,なかなかうまく行きません. 怪しいなーと思って見ているとどうやら地元民の方が半分くらい占めていることが分かり,更に車のナンバープレートの統計を取ったところ「岡山・兵庫・神戸・姫路」がほとんどとなっていることに気づきます. これはとんだ大誤算です.

僕は地理を知らないので兵庫・神戸・姫路の場所の位置関係がわかりません. 神戸に寄って帰るか京都を粘るかを考えるため,地図を眺めるのですがここは鳥取の東端,中国地方の地図しかありません. 悩んだ末,ローソンの温泉ガイドを眺めたら兵庫の位置関係がわかり,神戸に寄って帰っても大きく東へ進めるからいいかと妥協をします.

「京都方面」「京都・神戸方面」と掲げながら会釈し続け,一時間ほど経ったあたりで旅行の帰りの神戸の夫婦の方に声をかけてもらうことができました.精神的にも体力的にも疲弊している様子が伝わっていたそうで,可哀想だったので声をかけてくれたとのこと. 今までのヒッチハイクでは道中ずっと会話をしていたのですが,疲弊度を見かねたのか「着くまで眠っていてもいいのよ」とのことで,お言葉に甘えて車内で睡眠を取らせていただきました. 「息子より若い」と言われまして,まるで我が子のように親切にしていただき,お菓子と豚まんと飲み物を恵んでもらいました. こちらの夫婦にはもう感謝の言葉しかありません.

@但馬(兵庫) PM 05:16

一度養父に寄らせてもらったのですが,こちらの方が京都方面を拾いやすいだろうと計らってもらい,但馬の道の駅まで連れて行っていただきました. そろそろ日も暮れてしまいそうなのでササッと道の駅で位置情報を確認し,車のナンバープレートの統計をとって掲げる文字を決めます.初めは「京都」と掲げていたのですが,ナンバープレートは「神戸・大阪・なにわ」が多く,「京都」そのままではなかなか帰れそうにないことがわかったので,神戸を見つつ「大阪方面」として掲げます.一時間ほどヒッチハイク模索をしていると声が.

乗せてくれた二人のお兄さんはバーベキュー検定の帰りとのことで,「京都」を臨機応変に「大阪」に変えたりしていたのを見て乗せてくれたとのこと. コンサル・コピーライターの方でしたので「後悔しない生き方をしたい!」という話をしたり, 僕が文章力を欲しいと話したところ文章の指導をしていただけたりなかなか充実した時間を過ごせました.

昔に id:suzusime と京都旅行をしたあとに,彼が はいふりカメラとゆく京都 - すずしめにっき との記事を書いており,なるほど同じ体験をしたのに僕ではこんな記事は書けないなあと思ったことがありまして,文才を得たく率直にこの記事(はいふりカメラ)を例にだして文章力を得る方法について教えを乞うたりしていました. はいふりカメラの話でも惑わずに指導してもらえたのですごい方です.

@桂川SA PM08:21

お兄さん方の好意で桂川までたどり着くことができました. 「あとは京都のナンバープレートの車に声をかけて市街地まで送ってもらいな〜」とのことでお別れをします. ここはもう徒歩圏内なので安心度が違います. 安心すぎて「あと3日は生きれるな…」と残しておいたご飯や飲み物を一気に消費します.満足. 22時まで頑張ってみたのですが,意外と滋賀ナンバーが多く,徒歩圏内だしここから歩いたことないな〜GoogleMap無しでも帰れるかな〜との邪念が発生し,せっかくなので歩いて帰ることにしました.

@京都駅 24:30

歩いて帰れました.ウイニングランですね. 京都へ帰ってきたことを知った id:Pasta-K さんがお酒をくれたので飲みながら鴨川を北上していきます.部員が迎えてくれたので,後はお酒を飲みながら深夜2時には吉田寮まで帰ることができました.

やったー

さいごに

なんやかんやで帰ってくることができました. 1グループだけ,名古屋でどうしてもヒッチハイクが捕まらず,救援を要請しているのを見かけました. 名古屋はヒッチハイクが難しいらしいですね. しかしながらどうやら現時点で全グループが無事帰ってこれたようです.よかった.

「ヒッチレースをしている」という身分はなかなか便利です. 交通費を浮かすためだけにヒッチハイクをするというのは僕には多分無理だと思います. 交通費は浮かすのに観光地でお金は払えるんだなあと思うとちょっと気後れしてしまいます…. その点ヒッチレースだと無一文で命がかかってるため,見知らぬ人と会話するのも話題を作るのもたいへん気楽なものです.

僕を車に乗せてくれた方々・更に食料まで恵んでくださった方々には重ねて感謝を申しあげ.最後に今回の経路を載せて結びとします.

f:id:CHY72:20180528175524p:plain

ふふーー.

仮想通貨掘りたい

はじめに

この記事は KMCお絵描き Advent Calendar 2017 - Adventar の 20日目の記事です。*1 前回の記事は id:lastcat さんによる KMCお絵かきアドベントカレンダー 12/19 - lastcatのブログ でした。 ねこさん、奈良で修行のように同人活動に精を出していてすごいです。

最近は全然絵を描いていなかった*2ので、 一念発起して絵を描く気力を出そうとしてお絵かきアドベントカレンダーに登録してしまいました。*3

マイニングしたい

最近は仮想通貨の高騰がすごいですね。 バブルバブルだなんて言われていますが、それに乗っかってマイニングしている人々を見ていると 楽しそうだなーと思ってにやにやしてしまいます。 多分今の時代、マイニングするのもそんなに難しくないんでしょうけれど、 取り掛かったあとにはずっとチャートグラフとにらめっこする生活が待っているかもしれないと思うと、 なかなか取り掛かることができずにいています。

家に強いサーバーもないので、もしも採掘するとしたらクラウドVPSとか借りるのかな? VPS といえば ConoHa *4 のこのはちゃんかわいいですよね。

というわけで、 仮想通貨を掘るこのはちゃんを描いてみました。

f:id:CHY72:20171221063741p:plain

最後に

GPUでがっぽがっぽ*5掘って稼いで夢の億万長者になりたい!

仮想通貨バブルが弾けて露頭に迷ったこのはちゃんをごにょごにょする薄い本ください。

明日(今日)のKMCお絵描きアドベントカレンダーは kuniv_bu くんによる リディー&スールのアトリエ発売&アトリエ20周年おめでとうございます!! - ぶろぐ おぶ ぶ です。 彼の池田屋の記事よかった。

*1:一日遅刻!

*2:Piet は描いていたし、なんならPietで修論書きたい

*3:一日遅刻!

*4: https://www.conoha.jp/

*5:ConoHaってGPU使えるんですかね?

ゆーま!(きららベース) が神

*1:なぜか先生のtwitterアカウントは最近消えてしまいました…

*2:http://seiga.nicovideo.jp/manga/official/kirara

*3:ちなみに苗字はまだ決まってないことが作品内で示唆されています

*4:作品内で「ゆーま」なんて可愛く表示されたことはない

*5:本当は Unidentified Mysterious Animal、作品内で素で間違えている

*6:復讐

*7:個人的には似た方向の作品として 日常 を代表とするあらゐけいいち作品がオススメです

*8: 他の社会派マンガとして じょしらく もおすすめです

*9:この画像は嘘に嘘を塗り固めたコラ画像ですが、東京オリンピックまでには実装されていると思っています。

競プロに疲れた人のNim言語

この記事は KMC Advent Calendar 2017 - Adventar 16日目の記事です。 ついでに、 Nim Advent Calendar 2017 - Qiita の 16日目の記事でもあります。 前日のKMCアドベントカレンダーの記事は asRagi さんの 【KMCAdventCalendar2017】カンタン味玉のススメ - らぎメモ でした。

asRagiさんお誕生日おめでとうございます! 最近のasRagiさんは料理している人みたいなイメージが出来つつあります。 僕も自炊で冬を乗り切りたいです。

はじめに

競プロをやっているみなさん、C++書いていますか? ところでC++辛くないですか? 速さのために色々と犠牲にしていませんか? Nimっていう最高の言語があるんですけどお話だけでも聞いていってもらえませんか?

はい。

というわけでこの記事では競プロのような問題に Nim 最高と永遠に褒めていきます。 Nim 自体はまだver1.0にも満たない開発途中なマイナーな言語ですので、知らない方も多いと思います。 そうですね…Nimは雑にまとめると 爆速静的型付けGCありお手軽言語 とでも言えましょうか。 以降では主に似た方向の静的型付け手続き型言語との比較をしながらNimのよさを語っていきます。 Nimを知らなくても雰囲気だけ伝われば、この記事を読み終わる頃にはあなたもNimを讃える一人となっているでしょう…。

目次

  1. お手軽 マイナスインデックス配列
  2. お手軽 定数分割代入
  3. お手軽 C++連携
  4. お手軽コンパイル時計算
  5. お手軽 for文
  6. お手軽 range-based for 文
  7. DよりきれいなUFCS
  8. 楽しいオレオレ構文

お手軽 マイナスインデックス配列

問題によっては負のインデックスを使えると効率的ないしは理解しやすいことがあります。 与えられた x の範囲が -50 から 50 など負を含み、その x をインデックスとする配列が作れると楽な場合とか。 C++であれば

int data_raw[100] ; 
int *data = &(data_raw[50]) ; 
data[-10] = 72 ; 

みたいなテクでしたっけ。 さすがにポインタを使わない他の言語ではこういうことは出来ないですよね。

Nim は変態なのでできます。

var A = array[-50..50,int]
A[-10] = 72

ワーオ、変態! ちなみに、RubyPythonでは負のインデックスは配列の後ろからの番号を指しますので、 なんだか変な感じもします。

お手軽 定数分割代入

C++で入力の数値を const な状態で取得するにはどうしていますか ? 多分こうしますよね。

const int n = [](){
  int tmp = 0;
  std::cin >> tmp;
  return tmp;
}();

いいですね。安心です。 では、よくある競プロ入力な 1 2 33 444 5\n2 2 23 244 5\n3 2 33 344 5 のように 列の数が固定で決まっている場合は各行をどのように取りますか ? 上の関数を5回仮にget_int_from_stdinと名付け、こう書きますか ?

const int n = get_int_from_stdin();
const int m = get_int_from_stdin();
const int x = get_int_from_stdin();
const int y = get_int_from_stdin();
const int z = get_int_from_stdin();

にゃーん。 テンプレートを駆使すればもうちょっと行けるかもしれません。 まあでもC++テンプレートはちょっと闇なので触りたくないですね。

Nim ならこう書けます。 まずは一つ

let n = stdin.readline().parseInt()

続いて複数。

macro unpack*(rhs: seq,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])

let (n,m,x,y,z) = stdin.readline().split().map(parseInt).unpack(5)

ワーオ、複数分割代入最高! unpackマクロをちょっと書く必要がありますが、これが大変便利です。 なんせ、問題に従って変数名を直感的にそのまま書くことが出来ますし、なんと全て定数です! このunpackマクロは、

let t = stdin.readline().split().map(parseInt)
let (n,m,x,y,z) = (t[0],t[1],t[2],t[3],t[4])

unpack(5) で済ましている感じです。 詳細は長くなってしまうので割愛します…。 ただ、僕が競プロでNimを使いたい理由の一つがこれです。最高です。

お手軽 C++連携

こういう言語では C++ と連携したいことが時々あります。 例えば、ちょっと前までの Nim には PriorityQueueがありませんでした。 そんな時、C++のPriorityQueueを使えれば楽ですよね。

type
  CPriorityQueue {.importcpp: "std::priority_queue", header: "<queue>".} [T] = object
proc cNewPriorityQueue(T: typedesc): CPriorityQueue[T]
  {.importcpp: "std::priority_queue<'*1>()", nodecl.}
proc newPriorityQueue*[T](): CPriorityQueue[T] = cNewPriorityQueue(T)
proc size*[T](this: CPriorityQueue[T]):int {.importcpp: "#.size(@)", nodecl.}
proc push*[T](this: CPriorityQueue[T],x:T) {.importcpp: "#.push(@)", nodecl.}

だいたいこんな感じに書くだけで使えます。便利。 使うときも、

var pque = newPriorityQueue[int]()

のように何の問題もなく使えます。最高。

お手軽コンパイル時計算

例えば素数テーブルを生成する関数を以下のように定義出来ます。

proc getIsPrimes(n:int) :seq[bool] = 
  result = newSeqWith(n+1,true)
  result[0] = false
  result[1] = false
  for i in 2..n.float.sqrt.int :
    if not result[i]: continue
    for j in countup(i*2,n,i):
      result[j] = false

はい。 これを使う時は、普通は

let isprimes = getIsPrimes(100)
echo isprimes[17]

のように使います。キーワード let で宣言しているので、 この関数の計算は実行時に行われます。 コンパイル時に計算したければ

const isprimes = getIsPrimes(100)

と、 letconst に変えるだけ!超便利! C++ だと constexpr の制約があったり、そもそも関数をconstexpr にしないと いけなかったり、色々めんどくさいですよね!Nim最高!

お手軽 for文

この節では 0 から n まで昇順列挙するfor文について述べます。

個人的に競プロのfor文のREPの文化が好きです。 REP は大抵以下のようなマクロです。

#define REP(i,n) for(int i = 0 ; i < (int)(n) ; ++i)

このマクロは以下のように使用できます。

REP(i,20) std::cout << i << std::endl; 

もちろん、#define によるマクロが悪であることなどは言うまでもありませんが、 競プロに類する問題ではこれは効率的な記法として一定の支持を集めていることは 否定出来ないと思います。 range-based-forと違ってインデックスがとれれば配列の中身を変更できるし インデックスを元にして別の変数と連携して計算できる基本的で最も使用される文なので、 そこが最適化されてしまえばこうなるのでしょう。

はい。

ところで kotlinだと

for (i in 0..20) print(i)

と書けますが、i の範囲は [0,20] であり、

for (i in 0 until 20) print(i)

と書かないと i の範囲を [0,20) に出来ません。 一貫性がなくてめんどい。 D言語だと iota を作ったりします。

さて、Nim はこんな感じで書けます。

for i in 0..<20: echo i

ここの < に注目です。これがあるとiの範囲は[0,20)になり、 これがなければ、iの範囲は[0,20] になります。 わかりやすいですね。これはswiftでも同じです。 最高ですね。

お手軽 range-based for 文

C++ には range-based for文があります。

for(auto d: data) std::cout << d << std::endl;

便利ですね。 しかしながら、そのインデックスを取得するのはちょっとめんどいです。

for(const auto& d:data) auto index = &d - &data[0];

にゃーん。

D言語のrange-based for文は

foreach(d;data) writeln(d);

のように書け、インデックス付きは

foreach(i,d;data) writeln(i," ",d);

のように書けます。かなりいいですね。 ただ、何重にもなると foreachと書くのもちょっと長いような気もします。

ところで Nim は簡潔に書けます。

for d in data: echo d

d の型は勝手に推論してくれるので C++のように auto とか書かなくてもよくて便利です。 index が欲しければ

for i,d in data: echo i," ",d

と書けて便利です。

DよりきれいなUFCS

D言語のUFCS、実はちょっと癖があって使いにくいです。 クラス内で宣言するメンバ関数とUFCSで擬似的にそう見える関数と二重に 定義出来てしまうせいで、ごちゃごちゃしてしまうことがあります。 Nim はメンバ関数とかはなく全て普通の関数記法で書き、モジュール内でエクスポートするものとしないもので分ける設計なのでそのような心配はありません。 Nim 最高!

楽しいオレオレ構文

template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body)
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)

の3つを主にオレオレ構文として定義しています。

# n回 hoge と出力
n.times: 
  echo "hoge"

とか、

# data[i][j] = max(data[i][j],data[j][k]) と同義
data[i][j] .max= data[j][k]

とか。 times は ただのforと比べて変数が増えないし便利ですね。 C++の雑魚マクロと違って本当に変数が増えないんですよ? マクロ定義に使用した変数 _ は使う側では見えないんですよ? 最高じゃないですか? C++のマクロって本当にクソですよね?

max=+= のノリで max を適用した感じのオレオレ構文です。 お行儀悪いですが地味に便利なので使ってしまいます。

最後に

以上、Nimの便利だと思う機能をつらつらと書かさせていただきました。 ここまで読んでくださり、ありがとうございました。

Nimに興味を持たれたら、 Nim Advent Calendar 2017 - Qiita を読んだり、 Nim programming language | Nim を読んだりしてください。

明日のKMC AdventCalendar は id:kazakami さんによる MinecraftでFPGA - kazakami_9’s diary です! マイクラでFPGAいいですね、いいです、すごくいいです。

ISUCON7本戦でBigintを殺したかった話

注意:このブログではGo言語のBigint(多倍長整数)について触れています
12/6 追記:殺せました

こんにちは。 ISUCON7本戦に「百万円ドリブン」の一員として参加しました。 メンバーは僕と, @nakario, @aokabi の三人で,二人はサークルのメンバーです。 集中のあまり美味しいお昼のクッキーと珈琲は逃してしまいました。

結果はタイトルの通りであり、競技時間内ではネックとなっていた Bigint を殺すことが出来ず、 悔しかったのでBigint周りで試行錯誤をした結果について述べます。 具体的には、Bigintと__float128について述べます。

今回のボトルネック

ボトルネックの測定と発見は @nakario が率先してやってくれました。 僕の改善担当箇所はそれにより判明したボトルネックの一つ 「Bigint の10進上位15桁の取得」 でした。

初期実装

初期実装では、Bigintを一旦文字列に変換してから先頭から15文字をとるという実装になっていました。 ベンチマークを回すと分かるのですが、このBigintは15万桁程度まで達する可能性があり、 すなわち15万文字の最初の15文字のみしか使わないということが平気で起こり、 遅いのも容易に理解できます。これは改善しなければなりませんね。

改善案

Go言語ではBigintはuint(符号なし64bit整数)の配列として表現されています。 単純に思いつく改善方法は、上位15桁さえ分かればよいので、 その配列の上位2つのuintからその数字を近似して計算する方法です。 例えば、 45桁の整数 111112222233333444445555566666777778888899999
= 326529 × 2128 + 8741109308212120013 × 264 + 7629705161560292767
となっているわけですが、これを上位2つのみを使用し、
326529 × 2128 + 8741109308212120013 × 264
= 111112222233333444445555559037072617328607232
と近似します。 計算すれば分かることですが、桁が増えても上位2つのみを用いればよいことに変わりはありません。 上位2つを用いて近似することにより、桁数オーダーだった部分を改善することが出来ます。 こうすれば BigIntを一つも使わなくてもよくなり、大幅な改善が見込めますね。

実装と精度の問題

上記の案をそのままuint64やfloat64で計算すると桁は容易に溢れるので、 log10 して計算し、最後に10の指数で戻せばよいです。楽勝ですね。



なーんてことは無かった…。 そもそもfloat64は15.9桁までしか整数との1対1対応を保証してくれません。 今回必要な桁は15桁、かなりギリギリです。 log10したり演算をすると、微妙に2桁程度合わないのです…。 ISUCON中ずっと「あと2桁!!あと2桁なんや…!!」って叫んでいました。 本質的に精度が微妙に足りないのです。 このあと僕は迷走してしまい、ISUCONは敗北を期しました。

こたえ

15桁全てを合わすことは到底不可能でも、それが何桁かどうかは精度の問題なしにすぐに計算できます。 よって、桁数を計算しもとのBigIntからその10の桁数分で除算するという方法がとれます。
例えば 111112222233333444445555566666777778888899999 / 100000000000000000000000000000
を行い 111112222233333 にするような感じです。 本質的にはBigIntをStringに変換する処理がBigInt除算の処理に変わります。 実はこれだけでかなり高速になり、 初期実装からこの部分のみを変更してベンチマークを走らせたところ、(ネックは他にもあるので一概には言えませんが) 7000点程度だったものから14000点まであがり、スコアが二倍になりました… はいbigintゲーwwwwwwwwww

bigint許さん

しかしながらこんなにも僕を困らせてくれる bigint 、殺すしかありません。 なんとしてでも bigintを実装から全て消し去り心の平穏を取り戻したいものです。 さて、僕の最初に思いついた実装方法は、精度が足りなかっただけなわけですから、 もっと精度の高いものを使えばbigintを使わなくても実装できるはずです。 残念ながら Go言語には float64までしかありません。 float128くらいまであればよいのですが…



はい、というわけで GCC の __float128 を使ってみましょう。

__float128

__float128 の枠組みは、疑似四倍精度とも呼ばれ、ソフトウェア的に float64を複数用いることで 擬似的に4倍精度を達成する枠組みです。 gccコンパイルすれば簡単に使えるので、Go言語とC言語を繋ぐ cgo を用いれば上手くできそうです。 cgo では、C言語コンパイルしたい関数を書いたC言語のコードを用意し、 そのインターフェースとコンパイルフラグ等をgo言語でシュッと記述すると簡単に二つを繋ぐことができます。 以下にCとGoのコードを載せます。

#include <math.h>
#include <quadmath.h>
typedef unsigned long long UINT64;
void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64 *o_keta,UINT64 *o_res){
  __float128
    fw1 = w1,
    fw2 = w2,
    log10ed = (64 * bef) * M_LN2q / M_LN10q
              + log10q(18446744073709551616.0Q * fw1 + fw2),
    res = expq((log10ed - floorq(log10ed)) * M_LN10q) * 100000000000000.0Q;
  *o_keta = (UINT64)log10ed - 14;
  *o_res = res + 0.000000000000001Q;
}
package main
//#cgo LDFLAGS: -lquadmath
//#cgo CFLAGS: -O3
//#include <stdlib.h>
//typedef unsigned long long UINT64;
//extern void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64* o_keta,UINT64* o_res);
import "C"
func B2E(w1, w2, bef uint64) (keta, res uint64) {
    var o_keta C.UINT64
    var o_res C.UINT64
    C.myb2e(C.UINT64(w1), C.UINT64(w2), C.UINT64(bef), &o_keta, &o_res)
    return uint64(o_keta), uint64(o_res)
}

はい。bigintを殺せました。勝利ですね。 早速ベンチを回しましょう…。




6 0 0 0 点!!!

初 期 実 装 よ り 遅 い !!

イヤイヤイヤイヤ、オイオイオイオイ… cgoのオーバーヘッドが意外と大きいのか?と思って計測してみましたが、 そういうわけでもなく、純粋に __float128 が遅いようです…。まじかぁ…

まとめ

BigIntを殺そうとしたが結局BigIntを完全に殺すことはできなかった。 BigIntくんも__float128くんよりは生かす価値があるようだ、命拾いしたな…

この記事を読んだ人はこんな記事も読んでいます

aokabit.hatenablog.com

nakario.hateblo.jp

全コード

github.com

12/6 追記 (実質Bigintを殺せた)

Bigint同士の除算は桁数オーダーの時間が掛かりますが、 初期実装の段階では上記の改善のみでよさそうです。 この後、更に高速化してもう一度この部分がネックになってきた場合には、除算を上位の3つのuintのみで行えばよいですね。 この実装であれば実質BigIntを殺したといっても過言ではないのでかなり満足です。

// 桁数が増えても大丈夫
func customBigIntDiv(a *big.Int, b *big.Int) int64 {
    alen := len(a.Bits())
    if alen < 4 {
        return big.NewInt(0).Div(a, b).Int64() 
    }
    an := big.NewInt(0).SetBits(a.Bits()[alen-3:])
    bn := big.NewInt(0).SetBits(b.Bits()[alen-3:])
    return big.NewInt(0).Div(an, bn).Int64() 
}