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

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倍になる

参考

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

背景

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

結論

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

備考

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

参考

DNSとDNSレコードについて

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

そもそもDNSサーバ

  • 2種類あるから混同させちゃダメ
    1. DNSキャッシュサーバ
      • PCなどから名前解決を依頼されるサーバ
    2. DNSコンテンツサーバ(権威DNSサーバ)
  • 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がある

参考

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

概要

ブラウザがページをレンダリングするまでにはいくつかのステップを経ている。 googleConstructing 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といった形。 リンク先の図が分かりやすい。

参考


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

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がよい。

参考

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

どういうこと?

こうではなく

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

こう書くということ

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

どうなるの?

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

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

参考

UUID生成について