アルゴリズムの計算量について
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倍になる
- 例1) O(n)の場合
参考
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 特集!知らないと損をする計算量の話 は、アルゴリズムとデータ構造を学ぶモチベーションを高めてくれた
VPCのメインルートテーブルに関してすごい勘違いをしていた
背景
AWSソリューションアーキテクトの勉強も兼ねてVPCの勉強をしていて、どーしても分からないなぁとなっていた。
VPC自体にルートテーブルを設定して何に使うんだ?と。
サブネットに設定されてあるルートテーブルでええやん?と。
結論
- VPCに設定したルートテーブルは
メインルートテーブル
と呼ばれ、ルートテーブルに明示的に関連付けられていない全てのサブネットの全てのルーティングを制御する。- つまり、VPCに設定されているわけではない!!
備考
上記の通り、明示的に設定していない場合、サブネットのルートテーブルはメインルートテーブルになるのです。
この状態でVPCのメインルートテーブルを変更してしまうと、明示的にルートテーブルが設定されていないサブネットのルートテーブルも変わってしまう!
パブリックサブネットがプライベートサブネットに、またはその逆が起こってしまう可能性があるのだ。
参考
DNSとDNSレコードについて
AWSについて勉強していて、Route 53に差し掛かったところでそもそもDNSよく分かってないや、ってなったので簡単なまとめ。
Route 53独自のレコードについても触れる。
そもそも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
がある
参考
バイト列を受け取ったブラウザが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)に囲まれたトークン1に変換する。
それぞれのトークンはそれぞれの特性を持っている。
トークンからノードへ - Lexing
トークンがオブジェクト(ノード)へと変換される。
Tokenizeで、headやbodyなどの各タグは始まりのタグと終わりのタグで別個になっていたが、
この段階でひとまとまりのオブジェクトへと変換される。
- Lex - レキシカルアナライザ(字句解析プログラム)を生成するプログラム
オブジェクトからDOMツリーへ
HTMLでは各タグ同士の包含関係などの関係性が書かれているので、オブジェクトは木構造へと結びつけられる。 htmlタグがparent、head、bodyがchildといった形。 リンク先の図が分かりやすい。
参考
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はプリフィクスに値のバイト数を示すデータが格納される
- 基本的には記憶域を節約できる
varchar
がよいが、必ず同じ桁数の文字列が格納されるカラムであればchar
がよい。
参考
URIのスキーマを省略すると?
どういうこと?
こうではなく
<img src="https://example.jp/index.html" />
こう書くということ
<img src="//example.jp/index.html" />
どうなるの?
短くかけて便利だけど、、、
- 参考リンクやGoogle HTML/CSS Style Guideにもあるように非推奨らしい。
参考
UUID生成について
- UUIDとは
- Universal Unique Identifier
- 汎システム的に他とは重ならない識別子
- uuidgen
- uuidを生成するコマンドラインユーティリティ
- libuuid(3)ライブラリが使われている
- 生成されたUUIDは、いつどこで作られたUUIDとも重ならないと考えて良い
- 書式
- uuidgen [ -r | -t ]
-r
乱数ベース-t
時刻ベース
- uuidgen [ -r | -t ]
- 使い方の例
- cookieにuser id としてセットして、効果計測に使う
- 例 UUIDでユニークユーザーを特定してアプリ広告の効果を測定
- ITP以降、3rd party cookieはセットしてもすぐ消えるかもしれないので注意!
- cookieにuser id としてセットして、効果計測に使う