2018-06-16

アルゴリズムの計算量について

1年ちょい前に基本的なソートと探索は研修で実装したんだけど(written in Perl)
その頃はなんだか分からないまま実装してた感あったので計算量もちゃんと意識やってみる
それにあたって計算量の基本の確認

計算量の評価

計算量の評価は時間計算量と領域計算量の2つから成る

時間計算量
- プログラムの実行に必要な時間の評価
  - CPUをどれだけ使うか
領域計算量
- プログラムの実行に必要な記憶領域の評価
  - メモリをどれだけ使うか

時間計算量が問題になることが多いので、計算量といわれるとき大抵は時間計算量

O表記法

オーダ表記法
O(n)やO(n²)のように表記する
nを入力値とし、nを用いた()内の式に計算量が比例することを表す
- 例1) O(n)の場合
  - 入力値nが5倍になれば計算量も5倍になる
- 例2) O(n²)の場合
  - 入力値nが5倍になれば計算量は(5²=)25倍になる

参考

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
特集！知らないと損をする計算量の話は、アルゴリズムとデータ構造を学ぶモチベーションを高めてくれた

2018-06-15

VPCのメインルートテーブルに関してすごい勘違いをしていた

背景

AWSソリューションアーキテクトの勉強も兼ねてVPCの勉強をしていて、どーしても分からないなぁとなっていた。
VPC自体にルートテーブルを設定して何に使うんだ?と。
サブネットに設定されてあるルートテーブルでええやん?と。

結論

VPCに設定したルートテーブルはメインルートテーブルと呼ばれ、ルートテーブルに明示的に関連付けられていない全てのサブネットの全てのルーティングを制御する。
- つまり、VPCに設定されているわけではない!!

備考

上記の通り、明示的に設定していない場合、サブネットのルートテーブルはメインルートテーブルになるのです。
この状態でVPCのメインルートテーブルを変更してしまうと、明示的にルートテーブルが設定されていないサブネットのルートテーブルも変わってしまう!
パブリックサブネットがプライベートサブネットに、またはその逆が起こってしまう可能性があるのだ。

参考

2018-06-10

DNSとDNSレコードについて

AWSについて勉強していて、Route 53に差し掛かったところでそもそもDNSよく分かってないや、ってなったので簡単なまとめ。
Route 53独自のレコードについても触れる。

そもそもDNSサーバ

2種類あるから混同させちゃダメ
1. DNSキャッシュサーバ
  - PCなどから名前解決を依頼されるサーバ
2. DNSコンテンツサーバ(権威DNSサーバ)
  - ドメイン名に関する情報を管理しており(IPアドレスとの対応、または、ドメインを管理している別DNSコンテンツサーバのIPアドレスなど)問い合わせに対して回答するサーバ
DNSの詳細な仕組みに関しては詳細に説明されているサイト(例えばここ)を参照のこと

DNSレコードとは

DNSコンテンツサーバはDNSサーバからの問い合わせに対して、ゾーンファイルを参照する
- ゾーンファイルには、DNSコンテンツサーバが管理する範囲内でのIPアドレスとドメインの対応、
  他のDNSコンテンツサーバにドメインの管理を委譲しているのであれば、委譲先の情報が書かれている
DNSレコードはゾーンファイルの各行のこと

主なDNSレコード

タイプ	略	概要
A	Address	`IPv4` IPアドレス。
AAAA	?	`IPv6` IPアドレス
CNAME	Canonical NAME	ドメイン名の別名。
NS	Name Server	ドメインの管理の委譲先の権威DNSサーバのドメイン名
MX	Mail Exchange	ドメインへのメール配送先サーバのドメイン。
TXT	TeXT	コメント行。Sender Policy Frameworkにも使える
PTR	PoinTeR	IPアドレスに対応するドメイン名。
SOA	Start Of Authority	プライマリネームサーバ、ドメイン管理者の電子メール、ドメインのシリアル番号(更新されたかどうかの判別に使う)、ゾーンのリフレッシュなど

上記のDNSレコード以外に、Route 53には独自のDNSレコードALIASがある
- ALIASレコードでは下記リソースのみ指定でき、それぞれ次のような振る舞いをする
  - CloudFront ディストリビューション
    - Cloud Frontドメイン名へのクエリと同様の振る舞い
  - Elastic Beanstalk 環境
    - 環境への1つ以上のIPアドレスを返す
  - ELB ロードバランサー
    - ELBへの1つ以上のIPアドレスを返す
  - 静的ウェブサイトとして設定された Amazon S3 バケット
    - S3バケットへの1つのIPアドレスを返す
  - エイリアスレコードを作成している同じ Route 53 ホストゾーン内の別のレコード
    - 別レコードへのクエリと同様の振る舞い
- ALIASレコードが参照しているレコードへの変更は自動的に認識される
  - ex) ELBのIPアドレスが変更されてもレコードを変更しなくてもよい
- 一度の名前解決でIPアドレスが得られるので早い
- DNS 名前空間の最上位ノード(Zone Apex)に作成できる

参考

2018-06-05

バイト列を受け取ったブラウザがDOMツリーをつくるまで

概要

ブラウザがページをレンダリングするまでにはいくつかのステップを経ている。 googleのConstructing the Object Modelを読んで、分からなかった単語などを調べながらまとめる。 CSSDOMのところは除いてとりあえずDOMツリーが作られるところまで。

バイト文字列からDOMオブジェクトになるまでの流れ

ブラウザーに渡されたバイト列は、下のような流れでDOMツリーになってレンダリングされる。英語が苦手な人もgoogleのページの図を見てもらえると分かりやすいかと。

バイト列
  ↓
文字列
  ↓
トークン
  ↓
オブジェクト
  ↓
DOMツリー

バイト文字列から文字列へ - Conversion

ブラウザーは、サーバーやディスクから読み込んだバイト列を、決まった文字コードに応じて文字列に変換する。例えば、htmlファイルのheadに<meta charset="utf-8">があれば、バイト列をUTF-8として処理する。

文字列からトークンへ - Tokenizing

ブラウザーは文字列を<html>や<body>などカギカッコ(angle brackets)に囲まれたトークン¹に変換する。それぞれのトークンはそれぞれの特性を持っている。

トークンからノードへ - Lexing

トークンがオブジェクト(ノード)へと変換される。 Tokenizeで、headやbodyなどの各タグは始まりのタグと終わりのタグで別個になっていたが、
この段階でひとまとまりのオブジェクトへと変換される。

Lex - レキシカルアナライザ(字句解析プログラム)を生成するプログラム

オブジェクトからDOMツリーへ

HTMLでは各タグ同士の包含関係などの関係性が書かれているので、オブジェクトは木構造へと結びつけられる。 htmlタグがparent、head、bodyがchildといった形。リンク先の図が分かりやすい。

参考

トークンはここでは、連続したデータにおいて最小の意味を持ったまとまりの意味。↩

2018-06-02

MySQLのデータ型の後にある括弧について(おまけ: charとvarchar)

整数型の場合

テーブルを作る
何文字まで入るのか、確認のためINSERTしていく

mysql> CREATE TABLE tinyint_test ( `num` tinyint(1) NOT NULL );

mysql> INSERT INTO `tinyint_test` VALUES ( 1 );
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `tinyint_test` VALUES ( 2 );
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `tinyint_test` VALUES ( 127 );
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `tinyint_test` VALUES ( 128 );
ERROR 1264 (22003): Out of range value for column 'num' at row 1

tinyintの取りうる範囲(符号ありの場合、-128 ~ 127)であれば、全て入れられる。
- 値や桁数の制限にはならない

文字列型の場合

varcharの場合

mysql> CREATE TABLE `varchar_test` ( `string` varchar(5) NOT NULL );
Query OK, 0 rows affected (0.03 sec)

mysql> INSERT INTO `varchar_test` VALUES ( 'あああああ' );
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `varchar_test` VALUE( 'ああああああ' );
ERROR 1406 (22001): Data too long for column 'string' at row 1

charの場合

mysql> CREATE TABLE `char_test` ( `string` char(5) NOT NULL );
Query OK, 0 rows affected (0.02 sec)

mysql> INSERT INTO `char_test` VALUES ( 'あああああ' );
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `char_test` VALUES ( 'ああああああ' );
ERROR 1406 (22001): Data too long for column 'string' at row 1

文字列型の場合、文字数制限がかけられる
varcharは可変長、charは固定長なのでもしかすると、違う結果になるのかなと思って両方やったけど同じ結果になった。

数値型のデフォルトの括弧の値

数値型の場合、デフォルトの値をしていなかった場合どうなるんだろう

mysql> CREATE TABLE `tinyint` ( `tinyint` tinyint NOT NULL );
Query OK, 0 rows affected (0.02 sec)

mysql> SHOW  CREATE TABLE `tinyint`;
+---------+-----------------------------------------------------------------------------------------------+
| Table   | Create Table                                                                                  |
+---------+-----------------------------------------------------------------------------------------------+
| tinyint | CREATE TABLE `tinyint` (
  `tinyint` tinyint(4) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 |
+---------+-----------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

4桁or4文字までとな
あ、マイナスがあるからか！

mysql> CREATE TABLE `tinyint_unsigned` ( `tinyint` tinyint  unsigned NOT NULL );
Query OK, 0 rows affected (0.02 sec)

mysql> SHOW  CREATE TABLE `tinyint_unsigned`;
+------------------+-----------------------------------------------------------------------------------------------------------------+
| Table            | Create Table                                                                                                    |
+------------------+-----------------------------------------------------------------------------------------------------------------+
| tinyint_unsigned | CREATE TABLE `tinyint_unsigned` (
  `tinyint` tinyint(3) unsigned NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 |
+------------------+-----------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

数値型で値を指定しなかった場合のデフォルト値は文字数のようだ

文字列型のデフォルトの括弧の値

mysql> CREATE TABLE `string` ( `c` char NOT NULL, `v` varchar NOT NULL );
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'NOT NULL )' at line 1

mysql> CREATE TABLE `string` ( `c` char(1) NOT NULL, `v` varchar(1) NOT NULL );
Query OK, 0 rows affected (0.03 sec)

そもそも指定しないとエラーになる

charとvarcharについて

charは固定長で 255文字まで格納できる
- 最初に指定した値の長さになるように文字列の右側が空白で埋められる
- 通常の設定では取り出す時に空白は削除される
varcharは可変長で 65,535文字(行全体のバイト数の最大値) まで格納できる
- varcharはプリフィクスに値のバイト数を示すデータが格納される
  - ~255までであればプリフィクスは1バイト、256~ であれば2バイト。
基本的には記憶域を節約できるvarcharがよいが、必ず同じ桁数の文字列が格納されるカラムであればcharがよい。

参考

11.4.1 CHAR および VARCHAR 型

2018-05-29

URIのスキーマを省略すると?

どういうこと?

こうではなく

<img src="https://example.jp/index.html" />

こう書くということ

<img src="//example.jp/index.html" />

どうなるの?

現在見ているサイトのプロトコルでリクエストが送られる。
- httpで見ているサイトならhttpで、httpsで見ているサイトならhttpsで

短くかけて便利だけど、、、

参考リンクやGoogle HTML/CSS Style Guideにもあるように非推奨らしい。
- プロトコルの省略、httpプロトコルの使用は非推奨とのこと
- こんな記事があったりするように、https化を進めているからかね。
- 何年かしたらプロトコル省略がデフォルトでhttpsとして解釈されたりするんかな?

参考

2018-05-20

UUID生成について

UUIDとは
- Universal Unique Identifier
- 汎システム的に他とは重ならない識別子
uuidgen
- uuidを生成するコマンドラインユーティリティ
- libuuid(3)ライブラリが使われている
- 生成されたUUIDは、いつどこで作られたUUIDとも重ならないと考えて良い
書式
- uuidgen [ -r | -t ]
  - -r 乱数ベース
  - -t 時刻ベース
使い方の例
- cookieにuser id としてセットして、効果計測に使う
  - 例 UUIDでユニークユーザーを特定してアプリ広告の効果を測定
  - ITP以降、3rd party cookieはセットしてもすぐ消えるかもしれないので注意！
    - ITPによるリターゲティング広告、計測ツールへの影響