Rails におけるパフォーマンス検証パターン: action 抜けた後が遅いケース

TL; DR

  • アクション抜けたあとは action の callback, rendering, rack middleware の世界
  • おもそうなものを特定して抜こう
  • bullet は重いぞ

事象

新機能開発中に、大量データ突っ込むか〜と思って突っ込んで開いたらまあ全然返ってこない。
はあ、まあそういうこともありますわよねと思って見ていたら、実はアクションから抜けるところまではそこそこの速度で終わることがわかった。1

調査

とゆーことは action 後に呼ばれる処理があやしい。 after_action はざっと確認した感じあんまりなさそうだった。2

ていうかそもそも rails log でも rendering xx sec と出ているのでレンダリングも終わっていることがわかった。

というわけでレスポンスを書き終わったはずなのにまだナニカをする層、つまり middleware があやしいということがわかる。

以下を参考に middleware ごとの経過時間を見ておく

http://blog.mirakui.com/entry/2012/04/03/slow-middleware

元コードは alias_method_chain を使っているので prepend に書き直してみた

gist.github.com

増加時間が長いやつを探す。今回は bullet が悪そうだった。業務アプリなのでログは載せないでおく。

とりあえず disable すればいいかなと思って設定変更したらはやくなったことを確認。
bullet は本番ではオフになるので特に問題にならないはずだなーというところまで考えて調査終了。


  1. このへんは愚直にメモ化されるところをまとめて評価したりしてログにぽこぽこ吐いて確認した

  2. これは目視で確認した。

オフラインリアルタイムどう書くE27の参考問題の実装例(Rust)

オフラインリアルタイムどう書くE27の参考問題「灯りと鏡」の実装例です。オフサイトだし Rust やるかあとおもって書きました。

問題 : http://nabetani.sakura.ne.jp/hena/orde27ligmir/
実装リンク集 : https://qiita.com/Nabetani/items/0b2f459ec128c89948f4

10/6 のイベント : https://yhpg.doorkeeper.jp/events/79705

github.com

NOTE: コードは末尾にも載せています。

問題自体はそんなに難しくなくて、素直にやれば素直に解けると思います……といいつつハマった点を2つ。

1つは、反射したらなんか、時計回りにまわるもんだと思っててあれー?ってなってました。これはただのアホでたぶん俺だけだと思う。

もう1つは、無限ループですね。どう示すか迷って、とりあえず座標 + 方角で HashSet つくって、入ってるか確認して、とやりました。一回通した後に「いや、これ各マスについてbitでフラグ立てればええやん」と思い直して今の実装に。おかげで sort する手間が省けていいです。

完全に Rust に不慣れなせいでいくつか困っています。

  • char どうやって変換するのがいいんだろ( from_digit でやってる
  • usize こんなに使ってていいんか? index 指定するために使ってるけど
  • consume 扱いになるとめんどいから参照で取得してるところがあるんだけどそれでいいのかわからない
    • 参照でもったあとリテラルの参照と比較するような書き方をするハメになっていてほんまか?という気持ちが

あと書いてて思ったんですが borrow 難しいですね……。なんかの struct にメソッドはやして破壊的にーとかやるとだいたい死ぬ。俺が悪い気はしている。Rust においてどういうふうに書くのがきれいなのかよくわからないなあと思いながらやっています。

最初に通すまで 2.5h くらいかかってますが Rust のリファレンスめっちゃ見てたのでRuby でやったら勝てた気がする。オンサイト時はおとなしく Ruby を使います。

use std::fmt;
use std::char;
use std::iter::FromIterator;

struct Field {
    f: [[Cell; 5]; 5],
    y_idx: (usize, usize),
}

#[derive(Eq, PartialEq, Debug, Clone)]
enum Direction { N, E, S, W, }

impl Direction {
    fn dir_flag(d: &Direction) -> i32 {
        match d {
            Direction::N => 1,
            Direction::E => 2,
            Direction::S => 4,
            Direction::W => 8,
        }
    }
}

struct RayResult {
    from: (usize, usize),
    dir: Direction,
    stopped: bool,
    passed: [[i32; 5]; 5],
}

fn coor_to_char(coor: (usize, usize)) -> char {
    let idx = coor.0 + coor.1 * 5;
    match char::from_digit(10 + idx as u32, 36) {
        Some(s) => return s,
        None => panic!("Cannot convert coor: ({}, {})", coor.0, coor.1),
    }
}

impl Field {
    fn set(&mut self, cell: Cell, x: usize, y: usize) {
        if cell == Cell::Y {
            self.y_idx = (x, y);
        }
        self.f[y][x] = cell;
    }

    fn start(&self) -> Vec<char> {
        let mut res = RayResult {
            from: self.y_idx,
            dir: Direction::N,
            stopped: false,
            passed: [
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
            ],
        };
        res.passed[self.y_idx.1][self.y_idx.0] = res.passed[self.y_idx.1][self.y_idx.0] | Direction::dir_flag(&Direction::N);

        let mut f = res.stopped;
        while !f {
            // println!("now: ({}, {})", res.from.0, res.from.1);
            res = self.process(res);
            f = res.stopped;
        }

        let mut vec = Vec::new();
        for (y, r) in res.passed.iter().enumerate() {
            for (x, f) in r.iter().enumerate() {
                if f != &0 {
                    let c = coor_to_char((x, y));
                    vec.push(c)
                }

            }
        }
        return vec
    }

    fn process(&self, mut res: RayResult) -> RayResult {
        let coor = match res.dir {
            Direction::N => (res.from.0 as i32, res.from.1 as i32 - 1),
            Direction::E => (res.from.0 as i32 + 1, res.from.1 as i32),
            Direction::S => (res.from.0 as i32, res.from.1 as i32 + 1),
            Direction::W => (res.from.0 as i32 - 1, res.from.1 as i32),
        };
        let oc = self.pick(coor.0, coor.1);
        if oc.is_none() {
            return RayResult {
                from: res.from,
                dir: res.dir,
                stopped: true,
                passed: res.passed,
            }
        }
        let c = oc.unwrap();
        let new_dir = Cell::reflect(c, res.dir);
        let new_x = coor.0 as usize;
        let new_y = coor.1 as usize;
        let flag = Direction::dir_flag(&new_dir);
        if res.passed[new_y][new_x] & flag != 0 {
            return RayResult {
                from: (new_x, new_y),
                dir: new_dir,
                stopped: true,
                passed: res.passed,
            }
        }
        if c != &Cell::X {
            res.passed[new_y][new_x] = res.passed[new_y][new_x] | flag;
        }
        return RayResult {
            from: (new_x, new_y),
            dir: new_dir,
            stopped: c == &Cell::X,
            passed: res.passed,
        }
    }

    fn pick(&self, x: i32, y: i32) -> Option<&Cell> {
        if x >= 0 && x < 5 && y >= 0 && y < 5 {
            return Some(&self.f[y as usize][x as usize])
        }
        return None
    }
}

#[derive(PartialEq, Debug)]
enum Cell {
    X, // x: 光を吸収するマス。
    D, // .: なにもないマス。光を通す。
    R, // 1: 「╱」という向きの鏡。
    L, // 0: 「╲」という向きの鏡。
    Y, // Y: あなた。
}
impl fmt::Display for Cell {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Cell::X => write!(f, "X"),
            Cell::D => write!(f, "D"),
            Cell::R => write!(f, "R"),
            Cell::L => write!(f, "L"),
            Cell::Y => write!(f, "Y"),
        }
    }
}
impl Cell {
    fn reflect(c: &Cell, dir: Direction) -> Direction {
        if c == &Cell::R {
            // println!("reflect by {}", c);
            // R == /
            return match dir {
                Direction::N => Direction::E,
                Direction::E => Direction::N,
                Direction::S => Direction::W,
                Direction::W => Direction::S,
            }
        } else if c == &Cell::L {
            // println!("reflect by {}", c);
            // L == \
            return match dir {
                Direction::N => Direction::W,
                Direction::E => Direction::S,
                Direction::S => Direction::E,
                Direction::W => Direction::N,
            }
        } else {
            dir
        }
    }
}


fn new_field() -> Field {
    Field {
        f: [
            [Cell::Y, Cell::X, Cell::X, Cell::X, Cell::X],
            [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X],
            [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X],
            [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X],
            [Cell::X, Cell::X, Cell::X, Cell::X, Cell::X],
        ],
        y_idx: (0, 0)
    }
}
fn solve(input: &str) -> String {
    let row_strs = input.split("/");
    let mut field = new_field();

    for (y, row_str) in row_strs.enumerate() {
        for (x, c) in row_str.chars().enumerate() {
            let cell = match c {
                'x' => Cell::X,
                '.' => Cell::D,
                '1' => Cell::R,
                '0' => Cell::L,
                'Y' => Cell::Y,
                _ => panic!("Invalid input: {}", input),
            };
            field.set(cell, x, y);
        };
    }

    let tmp = field.start();
    return String::from_iter(tmp)
}
fn test(input: &str, expected: &str) {
    let actual = solve(input);
    if actual != expected {
        println!("ng\n  actual: {} \nexpected: {}", actual, expected);
    } else {
        println!("ok!");
    }
}
fn main() {
    test( "x...x/.1.0./..0../.Y.../0..x.", "ghilnqs" );
    test( "..Y../...../...../...../.....", "c" );
    test( "..x../..Y../...../...../.....", "h" );
    test( "..Y.x/..1x0/11.../....0/1..1.", "c" );
    test( "....1/....Y/...../...../.....", "ej" );
    test( ".10../x.1../x.1x./.Y.1./...0.", "bcghlq" );
    test( "0.x10/00..x/x0x.0/....0/...Y1", "deinsx" );
    test( "1.01./01Y.1/..1.1/..10./0.0..", "abcfgh" );
    test( "x..../x1x../0...0/....Y/.1..0", "klmnot" );
    test( "...../..10./.1Y1./.01../.....", "hilmnqr" );
    test( "...../..10./x.11./...../..Y..", "hilmnrw" );
    test( "...../x.10x/...../x.Y1x/.....", "himnqrs" );
    test( "..010/...Y1/..0../0.x../.....", "defghij" );
    test( "1.0../...../.0x../Y.1x./..1..", "abcfhkp" );
    test( "...../101../0.0../..Y../.....", "fgklmqrv" );
    test( "1.0../00.../.x..0/0.Y1./...10", "abcfghmr" );
    test( "x101./1..../.Y.x./..01./.00.1", "bcghlmrs" );
    test( "x11../x.x../.0.01/..x../...Y.", "bcglmnsx" );
    test( "..1.0/x0.x./0.0../x...Y/.10.1", "cdehjmnot" );
    test( "..x.0/.0.../1..0x/1..1./Y.00.", "klmnpqrsu" );
    test( "0.1.0/.0.xY/0...0/01..1/x00.x", "cdehjmrwx" );
    test( "...0./.0.0./..101/...10/..01Y", "mnpqrstwxy" );
    test( "10..0/.Y.0./0..1./....x/000..", "abfghiklmn" );
    test( "10..1/...../.1010/110.1/x..Yx", "lmnopqrstx" );
    test( "110../....1/x1..x/0.0.0/....Y", "bcghlmrsty" );
    test( "x.101/1..../..001/010Yx/..1.1", "cdehijmnos" );
    test( "x.111/x10../...0./00.1x/x.Y.1", "ghklmnqrsw" );
    test( "11.../....0/11..1/1.1../.Y..1", "fghijlmnoqv" );
    test( "...x1/.1.0./11.1./.01../Y..x.", "cghiklmnpqru" );
    test( ".0.../110x./11..0/01.x./..Y.x", "ghklmnopqrtw" );
    test( ".01.0/.110x/0...0/.01Y./x.1x.", "cdeghilmnqrs" );
    test( ".1100/..1.0/1.11Y/0..1./.0..0", "hijklmnopqrs" );
    test( "1..00/..11./.100./1..Y1/.....", "abcdfhikmnps" );
    test( "1.0../.11x0/.00.x/Y.10./.10x0", "abcfghklmpqr" );
    test( "11110/11.../.x.../.0111/0.Y0.", "deijnorstwxy" );
    test( "...1./.1.0x/10..0/0Y.11/.0.x0", "ghiklmnopqrst" );
    test( "...10/x111./0x.11/.0.../0.0Y.", "dehijmnorswxy" );
    test( ".1x../.x1.0/0x.x./x11.1/x0Y.1", "hijmoqrstvwxy" );
    test( "x.x../x110./1.1.0/0.Y.1/0.00x", "hiklmnopqrstx" );
    test( "...0./11.00/10..x/..0.1/Y0.10", "ghiklmnpqsuvwx" );
    test( ".110./....0/x..../.0001/11.Y.", "cdfghijmnorstx" );
    test( "1.00./....1/.1.../0...0/0..1Y", "abcfhkmpqrstwy" );
    test( ".1.01/..x../..100/..Y../...01", "bcdgilmnoqrstvxy" );
    test( "1...0/Y..../...../...../0...1", "abcdefjkoptuvwxy" );
    test( "x1..0/1..0./.Yx../0...1/.0.1.", "bcdefghijklnopqrstvwx" );
    test( "1...0/.1.0./..1../..01./Y0..1", "abcdefghijklmnopqrstuvwxy" );
}

オフラインリアルタイムどう書く E26 の実装例(Ruby)

問題 : https://cedretaber.github.io/doukaku/e26/ 実装リンク集 : https://qiita.com/Nabetani/items/0bcabb80bdcbc9b2ff52

負けました。

とりあえず当日中に書いたのはこんなの。

github.com

縦n列目については n + 1 列目にあるやつをうごかせば揃うなーというのは手で動かしてて気づいたので、それで最下段以外は揃えておく。
このあと最下段が揃った後に、最下段にパターンがあるかなーと思ってそれをなんか後から直せないかなというのが回答方針です。が、パターン見つかるわけないよねーということで敗北。

想定解法まであと2ステップほどひらめきが必要だったので、まあ惜しくもないですね。はい。

この後想定解法を実装し終えたらまた追記します。

追記: 2018-09-03 00:00頃

Comparing 4cfee85e1d9745a95caf954bbe485cef0f114e1c...a38c3c3afdd3c2997603d3661871a4f9808e3ef5 · hkdnet/misc · GitHub

解けました。
なんかしらんが x と y を入れ違えてたりでIFの重要性を感じますね……。Coordinate とか作っときゃよかった(´・ω・`)
見どころはたぶん最初の行の全探索のやり方です。パターン生成するのがめんどかったので to_s(4) で4進数表記したものから生成してます。ほかは面白いとこないかと。

@commands = []
n.to_s(4).chars.reverse_each.with_index do |c, idx|
  cnt = c.to_i
  @commands += Array.new(cnt) { [idx + 1, 1] }
end

# 6 なら 12 なので右端から1つめを2回、2つめを1回 まわすとする

WIP: ast でメソッドコールを探すやつを作り始めました + designing data-intensive application を読んでいます

本日は2本立てでお送りします(特にネタがないので小ネタというか終わってないネタを2つ合わせて記事にしとくか……という記事です。

ast でメソッドコールを探すやつを作り始めました

ほしくない?と思って作っています

github.com

使い方は何かと言うとある特定のメソッドの呼び出しを一覧にしたいぞ、というのがもとの欲求です。grep でもいいんですが、せっかく AST parser あるんだから使えばいいじゃん、ということでやってます。まだ NODE でとれるだけです。

grep よりもいい点としてレシーバや引数の情報ももとに検索できることでしょうか。そういう要望があるのかすげーあやしいのですが。あ、でも第二引数がはいってるかどうかをみることでオプション引数がない状態で呼ばれてないか、という確認はできますね。

インターフェースとして今は ruby コード書いてるけどそうじゃなくてなんかいい感じのクエリかけたらいいなーと思いつつ、特にアテがない状況。

テスト環境としては mtsmfm さんの docker image を採用。毎日 trunk でビルドしてくれるのでまだ安定版の存在しない RubyVM::AST のテストにはいいイメージですね。

https://hub.docker.com/r/mtsmfm/ruby-trunk/

designing data-intensive application を読んでいます

読み始めていますがまだ chapter 2 とかです。平易な英語でとても読みやすいのですが単純に英語であるだけで読むのがつらいらしくて全然進みません。すみません。

chapter 1 では、reliable, scalable, maintainable なアプリケーションについて話しています。アプリケーションの良さの指標として前述の3つを挙げて、それぞれについて解説していました。chapter2 では、まあ雑にいうと relational model vs document model という話をしていて、結構面白いです。mysqlJSON 型すら全く使ったことがないのでなんか使うとよさそうなところで使ってみたいですね。

relational model におけるテーブル設計と制約などは少しはノウハウがあるのでなんとなーくわかるのですが、document model においてデータの健全性をどう保てばいいのかよくわかりません。その健全性についても read 時のチェックと write 時のチェックだ、と対比されていましたが正直業務データとか突っ込むには不安が……。個人でやっててもあんまり痛い目みなさそうだし、ダメージが少なそうなところに突っ込むしかないのかなあ……とどう導入しようかいろいろ検討中です。

僕が途中で挫折しないように、感想とかを言える仲間を募集していますので twitter とかでお気軽にどうぞ。

【PR】転職ドラフトで転職してから1年が過ぎたので体験を振り返る

【こちらの記事は転職ドラフト体験談投稿キャンペーンに参加しています】

job-draft.jp

もう転職して1年1ヶ月になりますね。1年も前なので転職ドラフト自体も変わってはいるのでしょうが、体験談を投稿するとアマギフをくれるというので頑張って書こうと思います。


当時の僕は2社目に転職して1年が過ぎた頃でした。技術的に閉鎖的だった1社目から転職しており、当時の会社は技術面では特に問題はない一方で賃金が低いということに対してうっすら不満がありました。そんな中で某 podcast で「転職ドラフトの提示額をもとに翌年の給与の交渉をした」という話を聞いて自分でも試してみたのがきっかけでした。

指名自体は13件頂いていたようです。ありがたや。2017年頭くらいの僕がどんなだったかというと過去記事を参照するのがよさそうです。

hkdnet.hatenablog.com

箇条書きスキルセットはこんなん

  • Ruby + Rails 業務で1年くらい
  • jsをバニラ、jQueryで3年、Reactとか雑にはかけるけど redux とかの設計は無理
  • その他 docker, crystal, php, go とかの経験をちょこちょこ

あんまり経験なさそうだけど、ECS使うとかDeepLearning本一通り実装したとか、そういうある程度の技術トレンドは追ってた感じがありますね。転職する際に有利に働いたんじゃないかな。

指名をもらったあとは、通常の面接が始まる感じですね。面接の内容は、1回目の転職活動と比べて技術レベルとかの話にスッと入っていけた印象はあります。といっても1回目の転職活動はほげナビとかそういうの経由だった1ので比較してよいのかは議論の余地がありそうです。たとえば最近の m○ffers とかと比べてどうなのっていうと、うーんどうなんでしょうね。2
ちなみに m○ffers は登録時にレジュメの添削(人力)があって、そういうところは後発なのもあって頑張ってるなーと思いました。

この後は、転職ドラフト経由での転職おめでとう品をもらうというイベントがあるくらいで他の転職サイトと変わらないのではないでしょうか。転職後すぐの頃は「ある程度マッチングした状態で始まるから楽」とゆーてたのですが、実際に面接官をする立場になってみるとぶっちゃけどの採用経路で入ってきた人でもあんまり変わらない気がしてきました。
なので「転職ドラフト経由でいった会社の面接がやりやすい」と感じていたのは単純な勘違いか、転職ドラフトに指名参加する会社ならだいたい僕がやりやすいという話なのかもしれません。たぶん後者かなあ。

というわけでつらつら書き連ねましたがこんなところでしょうか。転職記念で Apple ギフトカードをいただきまして、それで買った iPad pro はいまでも技術書3を読むのによく使っています。よいサービスだと思っておりますので今後もうまく発展していくといいなとこっそり応援しています。

(1452文字)


  1. 結局リファラルで入ったけど

  2. そもそも m○ffers が、激似すぎるという話があったりなかったりするわけですが

  3. とマンガ

「AESで暗号化した時の文字列の長さってどれくらい変わるの?」という質問に答えようと調べた話

経緯

「AESで暗号化した時の文字列の長さってどれくらい変わるんだろう、って調べているけど全然出てこねえ。実際試してみると1.5倍くらいっぽいが。」

という質問が友人から投げられてきたので調べました。

前提

  • AES256
  • 平文は 99 文字

調査ログ

padding のせいだよ説

AESはブロック暗号方式であるので、ブロックごとの長さに足りない分をpaddingされるだけではないか?と予想。 AESのブロック長は 128bit = 16byte なので Math.ceil(99/16) * 16 = 112 で 112 文字になるのでは?

→ 1.5倍だから150文字くらいになっているのだろう……おかしい

99文字とはいったが1文字1byteとは限らないのでは?

→ ascii 範囲内であることが判明。utf-16とかじゃなければ1文字1byteになりそう(´・ω・`) 99文字 → 152文字らしいので差が53byteある。そもそもブロック長以上の差分が出るわけがないのでおかしい。1

padding 説は濃厚だがそれだけではなさそう。

padding って実際なにしてんの

ここでインターネットに本格的に頼りだす。記事とそこで挙げられている参考実装を読む

www.atmarkit.co.jp

github.com

参考実装だと 128 bit ごとに入れてるのでそれより長い長さの暗号文をどう扱うかが問題。
もう実装読むしかねえという気持ちになり javax.crypto のソースを漁ると Cipher.getInstance("AES/CBC/PKCS5Padding"); という記述を発見。
また、本人から参考にしている Qiita 記事をもらう。

qiita.com

PKCS5Padding

どうも名のある padding 方式らしいので調べたらRFCとかにもある模様。PKCS#5, PKCS#7のバリエーションがあって、基本的に余った文字数が1だったら 0x01で、2だったら 0x02でっていうふうに埋めてく模様。

blog.shin1x1.com

余談ですが、Java の javax.crypto.Cipher にある PKCS5Padding は、名前は PKCS5 ですが、実質は PKCS#7 相当の動きをするようです。

ひどい話だ……。実用上あんまり問題はないんだろうが。やはりこれを読んでても padding でやたら長くなるのはおかしそうだ。

base64 で膨れてる説

Q: もしかして暗号文って最後に==って出てません?

A: 出てるよ

base64 エンコードされていたことが判明。base64エンコードは長さが変わるのでこれっぽい。 平文→暗号化に入るとき(128bit単位にパディングされて暗号化)→暗号化(パディングされたのと長さ同じ)→base64

というわけで 99 bytes を変換したら 152 bytes になるかを検証。

平文: 99 bytes
平文(パディング): 112 bytes
暗号文: 112 bytes
base64: 152 bytes ( = Math.ceil(Math.ceil(112 * 8 /6) / 4) * 4 )

ok

そんでもとの質問は「AESで暗号化した時の文字列の長さってどれくらい変わるの?」だったので、ざっくり1.5倍かなーと思いつつ試算

  4(n+16)/3 >= 3n/2
⇔ 128 >= n

ダメじゃん!2

仮に2倍とっておくと 8>=n におさえられて安心。
input の平文の長さが決まってれば 2 倍じゃなくてかなりきれいに扱えそう。

実験

ここまで理解したところで実験。

encrypted len - Google スプレッドシート

たしかに1.5倍だとところどころ抑えられていないことを確認。 とゆーわけで input の長さによるが、2倍あればおおむねいける。固定長ならもっと攻めることができる、という感じでした。

# https://docs.ruby-lang.org/ja/latest/class/OpenSSL=3a=3aCipher.html
require 'openssl'
require 'base64'

class Encryptor
  def initialize(data)
    @salt = OpenSSL::Random.random_bytes(8)
    @pass = "**secret password**"
    @data = data
  end

  def exec
    # 暗号化器を作成する
    enc = OpenSSL::Cipher.new("AES-256-CBC")
    enc.encrypt
    # 鍵とIV(Initialize Vector)を PKCS#5 に従ってパスワードと salt から生成する
    key_iv = OpenSSL::PKCS5.pbkdf2_hmac_sha1(@pass, @salt, 2000, enc.key_len + enc.iv_len)
    key = key_iv[0, enc.key_len]
    iv = key_iv[enc.key_len, enc.iv_len]
    # 鍵とIVを設定する
    enc.key = key
    enc.iv = iv

    # 暗号化する
    encrypted_data = ""
    encrypted_data << enc.update(@data)
    encrypted_data << enc.final

    encrypted_data
  end
end

1.upto(255) do |n|
  enc = Encryptor.new('a' * n).exec
  enc_size = enc.size
  base64_size = Base64.encode64(enc).size

  puts "#{n},#{enc_size},#{base64_size}"
end

  1. ここで utf-8 は ascii 範囲内の文字は ascii 互換で 1byte 文字であること、日本語の「あ」とかは3byte文字であることなどを説明

  2. というか 99 -> 152 の時点で 1.5倍超えてる

icfp pc 2018の問題を解く、前準備を勧めている

だいたいタイトルどおりの話です。なおまだ問題全然解いてないです。

ICFP Programming Contest 2018

icfp pc はなんか数日間頑張って最適化とかの問題を解いてスコアを競うやつです。今回のはざっくりいうと3Dプリンタ最適化問題で、指定の座標を塗りつぶしたモデルを作成するためにボットを操るやつです。なおかなり前に終了しています。

モデルのデコーダ

モデル = 指定の座標がどこか示してあるやつ。これのデコーダがないとその後扱える気がしなかったのでとりあえず書いたのだが、冷静になってみるとブラウザでレンダリングして簡単そうなのを選んだほうがよかったかもしれない。
フォーマットは、僕の理解ではこんな感じ。

  • 先頭1バイトはサイズrを指定。 r * r * r のサイズの空間でなんかやる
  • 座標(x, y, z)に対応した整数として x * r2 + y * r + z (r進数的に解釈したやつ)を考える
  • 2バイト目以降は座標に対応したビットが立ってるかどうかで判定
    • 2バイト目は [7, 6, 5, 4, 3, 2, 1, 0]
    • 3バイト目は [15, 14, 13, 12, 11, 10, 9, 8]

いまの版ではこんな感じです。最初goで書いてたんだけどrubyのが楽だった。bit操作になれてなさすぎてbitを真面目に扱うより to_s(2) して文字列操作したほうが楽であることが判明した。これは今後も使っていきたいテクニックである

コレ自体はコンテスト期間中も書いてたのだけど、あとで viewer にかけたら chars.reverse の reverse がないせいでバグってたことが判明して昨日直したのと、あといま書いてて r が奇数のときはバイトが余るので to_s(2) しても8桁にならない可能性があって、それを format で直すの忘れてたんのでなおした。

つもりになってたが今直したほうは最上位 bit が立ってないケースも該当してて、それは reverse してるから特に問題なかったな……。はい

require 'model'
require 'coordinate'

class ModelDecoder
  def initialize(src)
    @src = src
  end

  def decode
    return @model if defined?(@model)
    _decode
  end

  private

  def _decode
    @r = bytes.first
    indexes = []
    bytes.drop(1).each.with_index do |b, i|
      base = i * 8
      str = "%80d" % b.to_s(2)
      str.chars.reverse.each.with_index do |c, j|
        if c == '1'
          indexes << base + j
        end
      end
    end
    cs = indexes.map do |i|
      x, tmp = i.divmod(@r*@r)
      y, tmp = tmp.divmod(@r)
      z = tmp
      Coordinate.new(x, y, z)
    end
    @model = Model.new(r: @r, fulls: cs)
  end

  def bytes
    @bytes ||= File.open(@src) do |io|
      io.each_byte.to_a
    end
  end
end

コマンドのエンコーダ/デコーダ

これは特に書いてて面白いことなかったのでパス。固定長じゃなくて2バイト読む必要があったのがめんどかった。配列渡して shift していく方式にして必要なら余分に shift すればおk

viewer

three.js つかって書いたら結構簡単にできてすごーいってなった。texture に適当にそのへんにあった water.jpg を使っているのだが見にくい。
左が公式のやつで右が僕のやつです。公式のやつ影とかついてて偉いな……。

f:id:hkdnet:20180812144930p:plain

なお、コレをみてなんかモデルのデコード失敗してんだなと理解して直した↓

f:id:hkdnet:20180812145026p:plain

そんなに真面目にフロント書くわけじゃないし webpack とか使う気にならず、 ln -s ../node_modules/three/build/three.min.js three.min.js とかで symlink はって終わらせました。

画像が回転できないと話にならないので回転させたんだけど最初は scene の rotate ではなくカメラのポジションをぐるぐるまわして、中心に向き直ってーとか考えてた。
原点を中心とした球の面上を移動すればよくて、(0, 0, R) を始点として zx 側の角度と zy 側の角度がわかれば球上の1点を指定できる気がした……のだがこれがどうもうまくいかない。たぶん球上の点になってないけどベクトルはあってるみたいな状態になってるので何倍かしてやればよかったな、と今更思った。

document.addEventListener("DOMContentLoaded", function() {
  var delta = 10;

  const modelSelect = document.getElementById("model");
  const viewerDiv = document.getElementById("viewer");
  const rightArrow = document.getElementById("right-arrow");
  const leftArrow = document.getElementById("left-arrow");
  const topArrow = document.getElementById("top-arrow");
  const downArrow = document.getElementById("down-arrow");
  fetch("/models")
    .then(e => e.json())
    .then(function(list) {
      const fragment = document.createDocumentFragment();
      list.sort().forEach(e => {
        const opt = document.createElement("option");
        opt.value = e;
        opt.textContent = e;
        fragment.appendChild(opt);
      });
      modelSelect.appendChild(fragment);
    });
  modelSelect.addEventListener("change", function() {
    const value = this.value;
    fetch(value)
      .then(e => e.json())
      .then(function(model) {
        const r = model.r;
        scene = new THREE.Scene();
        camera.position.z = 2 * unit * r;
        model.fulls.forEach(function({ x, y, z }) {
          scene.add(cubeCreator(r, x, y, z));
        });
        requestAnimationFrame(animate);
      });
  });
  rightArrow.addEventListener("click", function() {
    scene.rotateY(THREE.Math.degToRad(delta));
    requestAnimationFrame(animate);
  });
  leftArrow.addEventListener("click", function() {
    scene.rotateY(THREE.Math.degToRad(-delta));
    requestAnimationFrame(animate);
  });
  topArrow.addEventListener("click", function() {
    scene.rotateX(THREE.Math.degToRad(delta));
    requestAnimationFrame(animate);
  });
  downArrow.addEventListener("click", function() {
    scene.rotateX(THREE.Math.degToRad(-delta));
    requestAnimationFrame(animate);
  });
  document.addEventListener("keydown", function(e) {
    if (e.keyCode === 37) {
      leftArrow.click();
    }
    if (e.keyCode === 38) {
      topArrow.click();
    }
    if (e.keyCode === 39) {
      rightArrow.click();
    }
    if (e.keyCode === 40) {
      downArrow.click();
    }
  });

  var camera, scene, renderer;
  const unit = 1;
  const width = 820;
  const height = 820;
  const cubeCreator = (function() {
    const texture = new THREE.TextureLoader().load("textures/water.jpg");
    return function(r, x, y, z) {
      const geometry = new THREE.BoxBufferGeometry(unit, unit, unit);
      const material = new THREE.MeshBasicMaterial({ map: texture });
      const mesh = new THREE.Mesh(geometry, material);
      mesh.position.x += (x - r / 2) * unit;
      mesh.position.y += (y - r / 2) * unit;
      mesh.position.z += (z - r / 2) * unit;
      return mesh;
    };
  })();
  init();
  function init() {
    camera = new THREE.PerspectiveCamera(70, width / height, 1, 1000);
    renderer = new THREE.WebGLRenderer({ antialias: true });
    renderer.setPixelRatio(window.devicePixelRatio);
    renderer.setSize(width, height);
    viewerDiv.appendChild(renderer.domElement);
  }
  function animate() {
    if (scene) {
      renderer.render(scene, camera);
    }
  }
});

simulator

やる気にならなくていまブログ書いてるところです

今後

シミュレータがあれば適当に手で生成した命令列を実行したときの結果が見えるから戦略を考えてざーっと確かめられそう。でも下回りが整ったら飽きそうではある。