ユユユユユ

webエンジニアです

TIL

任意の区間で任意の整数の倍数を数える

Codility の問題をいくつか解いてみていて、どうにも解けずに諦めてしまった問題があった。匙を投げて解法を検索してみて、あまりにスマートに解けるものだから、なおさら悔しい思いをしている。そこで供養の意味も込めて振り返りをまとめておく。 当該の問…

配列を任意の個数の部分集合に均等に分割するアルゴリズム

長さ N の配列があり、それを M 個の部分集合に均等に分割したい。 制約を簡単に定義するとこうなる。 0 <= N 1 <= M <= 100 TL;DR active_support/core_ext/array/grouping の Array#in_groups がそのものズバリである。 誤ったロジック 3年前の自分が実装…

コンパイラ概論で遭遇した用語集まとめ

The Elements of Computing Systems を読み進めている。今週からいよいよ大詰めのコンパイラ編に突入した。 The Elements of Computing Systems: Building a Modern Computer from First Principles (The MIT Press)作者:Nisan, Noam,Schocken, Shimon発売日…

Amazon RDS for PostgreSQL のタイムゾーンはほとんど常に UTC であることに要注意

postgres の current_timestamp 関数を使ったクエリをアプリケーションに実装していたところ、本番データベースにタイムゾーンのずれによる時刻の不整合を招きいれてしまった。 TL;DR RDSで非 UTC の時刻を扱うユースケースでは current_timestamp や curren…

マルチプレクサとデマルチプレクサ

TIL

The Elements of Computing Systems に沿って基本の論理ゲートを実装している。 jnsato.hateblo.jp NOT, AND, OR, XOR のような耳慣れた論理に加えて、 Multiplexor と Demultiplexor という耳慣れない回路が、基本の論理ゲートとして扱われていた。そもそも…

NAND 演算があればあらゆる論理演算ができる

TIL

NAND とは NOT AND のことで、真理値表は次のようになる。 x y x NAND y 0 0 1 0 1 1 1 0 1 1 1 0 見ての通りの、 AND の否定形である。否定にすぎないから、論理学ではそう注目される演算でもないように思う。 しかし電子回路の世界ではこの演算が中心の座…

C++の整数リテラルに桁区切りを加える

Ruby であればこういう書きかたが許されている。ゼロを列挙するよりもはるかに視認性が高く、お気に入りの記法である。 a = 1_000_000_000 a # => 1000000000 C++ を書くとき、ここにほのかなもどかしさを感じることはあった。1000000000と書くのは読みづら…

rmagick をビルドする

TIL

入社初週の恒例行事として既存プロジェクトの環境構築をしていた。 幸いにしてほとんど障害なく進められたのはありがたい。このエントリに書くことさえ、大したことではない。しかし安易に検索エンジンに頼ったりせずに、自分の頭で考えてビルドを通せたこと…

ローカルの postgres を 12.3 に移行する

TIL

今週から新しいプロジェクトに参加することになった。 Rails + postgres の構成で動くアプリケーションの環境構築をした。 ミドルウェアを使うときはコンテナで実行するのが手癖になっていた。しかし今回は「無理して Docker を使わないこと」のポリシーに沿…

std::map と std::unordered_map

map というデータ構造は連想配列にあたるものと単純に理解していた。unordered_map について追って知ることとなり、初めて map のキーが自動的にソートされることを知る。 #include <map> #include <unordered_map> int main() { std::map<int, int> mymap1; std::unordered_map<int, int> mymap2; in</int,></int,></unordered_map></map>…

`String#==` は実行時間が最適化されているか?

昨日の記事で、 secure_compare は String#== とは異なり常に一定時間で処理が行われる、と書いた。 jnsato.hateblo.jp あらためて GitHub Developer から引用する。 Using a plain == operator is not advised. A method like secure_compare performs a "c…

Rack::Utils.secure_compare を読む

Hanami と Sinatra の CSRF 対策のコードで、いずれも Rack::Utils.secure_compare という API を利用していることを発見した。何が secure なのだろうか? という思いがあり、読んでみた。 def secure_compare(a, b) return false unless a.bytesize == b.b…

<form> タグが送信できる HTTP メソッドは GET と POST のみ

TIL

素の HTML form では GET と POST リクエストしか送信できない。PUT, PATCH, DELETE のような HTTP メソッドをリクエストするには、サーバーサイドで適当に解釈してあげる必要がある。 例えば Rails の場合、 form_with ヘルパーで編集画面の form タグを生…

Sinatra, Rails, Hanami それぞれの CSRF 対策の流儀

CSRF 対策がフレームワークでどう行われるかを読み比べていた。せっかくなので簡単にまとめることにする。 TL;DR 対応するクラス/モジュール 不正時の挙動 トークン Sinatra v2.0.8 Rack::Protection::AuthenticityToken [source] 403 base64 Rails v6.0.3 A…

無理して Docker を使わないこと

TIL

Rails のちょっとした機能を検証するとする。そんなとき、まずはなにからやるか? 今日の僕自身はと言うと、 Dockerfile を作るところから始めていた...。 改めていうまでもないことだが、自戒を込めて書く。愚の骨頂であった。ほんのちょっとした検証にわざ…

iOS で Safari の Cookie を無効化しているとリクエストが CSRF 扱いされる

TIL

iOS の設定で Safari の Cookie 機能を無効化することができる。 support.apple.com 普段 Safari を使うことは多くないのでそう意識していなかったが、僕自身はこれを有効化していた。で、これを有効化していると、当然 Cookie を利用したセッション管理を利…

配列の先頭と末尾を管理できる deque 型

AtCoderの過去問より、この問題を解いていた。 atcoder.jp やりたいこと 任意の数列を、空の配列の先頭と末尾に交互に追加していきたい。Ruby であれば、これは Array#unshift と Array#push を使って簡単に書ける。例えばこう。 n = 10 ans = [] 1.upto(n) …

ActiveSupport はきめ細かく require できる

hanami を利用した開発への所感 にて、こう書いた。 タイムスタンプを「○日前」と文字列に変換するだけのために、 ActiveSupport を丸ごと取り込むのは、理にかなった判断とは言えまい。 断定してしまっているが、実はよく調べないまま印象で語ってしまって…

宗教と暦の「歴史的文脈」を担うDateTimeクラス

DateTime クラスのドキュメントを読んでいた。 ほんの小さな好奇心で調べ始めたものだったが、世界文学のふたりの巨匠の命日を引き合いに出して暦の問題を鮮やかに示す文章に興奮させられて、つい読み込んでしまった。それはこんな例である。 shakespeare = …

Rack::Session::Cookie と Secure 属性

hanami にセッション管理を導入しようとしている。デフォルトでは Rack::Session::Cookie を使って cookie にセッションキーを格納する ことになっている。ちょうど先日、 Real World HTTP を読んで cookie の仕組みを復習したところだったので、 Rack がそ…

認証系 gem から知った BCrypt のこと

認証系の機能を持った gem を調べていた。見ていると多くの gem がパスワードのハッシュ化を BCrypt で実装している。きっと BCrypt ならば安心という一般的な合意があるのだろうとだけ推測して、あまり深入りはしなかった。 これだけであればただのつぶやき…

トップレベルドメインと帝国主義

TIL

この記事を読んだ。 gigaom.com 要約する。 インド洋チャゴス諸島。モーリシャスの西に位置し、アフリカから奴隷を入植させて発展した島々は、奴隷解放を経て、1960年代までにはココナッツ農園を軸とした経済と、それに携わる島民の暮らしがあった。 冷戦構…

無理して SPA を採用しないこと

TIL

「ゼロからアーキテクチャを考えるのであればどのような構成を検討しますか?」 これはある企業の面談を受けたときに聞かれたこと。僕は、最低限サーバーサイドのAPIとフロントエンドのSPAを分割する、というようなことを話した。 いま振り返ってこう考えて…

最大公約数を利用して最小公倍数を求める

「最大公約数」と問われると「ユークリッドの互除法!」とただちに着想が湧くようにはなってきた。 その一方で「最小公倍数」と問われたら、「おや...」と思いながら調べ直さざるをえない自分がいた。 この記事できちんと整理して、記憶に定着させたい。 定…

Ruby は 64-bit より大きい整数値をどう扱っているか?

先週末の AtCoder ABC169 B の問題で、long long 型の整数をオーバーフローさせてしまった。しかもそれに気づけずにだいぶつまずいてしまった。 atcoder.jp Ruby や Python であれば意識せず扱える部分であっただけに悔しさがある一方で、こうも思った。 Rub…

2^n 通りのbit全探索を m^n 通りの深さ優先探索に一般化する

以前の記事で bit 全探索を利用して冪集合を作った。 jnsato.hateblo.jp これは任意の有限集合の各要素について、部分集合に含めるか含めないかを表すフラグの組み合わせを総当たりする方法であった。各要素が 0 or 1 の二元のいずれかに振り分けられるため…

任意の集合のすべての部分集合を列挙する

任意の集合について、すべての部分集合を列挙したい。これはつまり、ある集合から冪集合を作りたい、と言い換えられる。 たとえば 3 つの要素からなる集合 X = {1, 2, 3} に対してP(X) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }であるような写…

深さ優先探索と std::next_permutation でそれぞれ n! 通りの順列を生成する

長さ n の順列 [1, 2, ..., n] を並べ替えて n! 個の順列を作りたい。 2<=n<=8 程度として、二通りのやり方を試してみた。 深さ優先探索 与えられた順列を末尾の要素から再帰的に swap して前通りの組み合わせを試す。ループごとに添字が 1 ずつ増えていくの…

ループイテレータの型を思考停止で int 型にしてはならない

y = f(x) = x^5 となるような写像 f を作ろうとして次のようなコードを書いてハマった。 unsigned long long N[1000]; for (int i = 0; i < 1000; i++) { N[i] = i*i*i*i*i; } Nは unsigned long long と定義しているが、 i^5 の i を int としてしまってい…

【go1.11以降】Go言語のモジュール依存管理には golang/dep を使わずに go mod を使うこと

学習者として、同じ学習者に向けた注意喚起として書く。 golang/dep は使わないこと golang package dependencies と検索すると、 golang/dep というツールのレポジトリがヒットすると思う。筆者の環境で、執筆日の時点ではトップに表示された。 github.com …