shiki0331’s blog

Web Developer. TypeScript / React.js を中心に学んでいます。 ブログ内容で間違っている箇所などありましたら、ご指摘していただけると助かります。

Solving the 'Zigzag Conversion' on LeetCode with C++

問題

https://leetcode.com/problems/zigzag-conversion/

答え

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

この問題の解決策を考えてみよう。

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R

最初の行から最後の行まで、それぞれの行の文字列を組み合わせた答えを求めます。

最初の行は "PAHN "である。 2行目は「APLSIIG」。 3行目は「YIR」。

"PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR" となる。

上記のアルゴリズムをコードとして書いてみよう。 答えのコードを再掲する。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

上のコードを分解してみよう。

    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

numRowsが1の場合は1行なので、s`を返すべきである。

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

numRowsまたは入力sのサイズの最小値を取る必要がある。なぜなら、numRowsが 4 でs` のサイズが 3 の場合、すべての行が使用されるわけではないからである。

goingDown は移動方向を表し、行の上下を表す。

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }
        }

rows[currentRow] += c;` は各行に文字列を作成します。

if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;

currentRowが最初の行、またはcurrentRowが最後の行の場合、goingDownを反転する。 goingDown が true の場合、currentRow を次の行に移動する。 goingDownがfalseの場合、currentRow` を前の行に移動する。

例えば 行数は 3 です。

行は上から下に移動するので、 goingDown は true です。 次の currentRow は 1 である。goingDown は true であり、currentRow はまだ最後の行ではないので、行はまだ上から下に移動する。 次の currentRow は 2 で、currentRow が最後の行であるため、goingDown は true から false に変わる。次の currentRow は 1 である必要があります。

        string result；
        for(string row : rows) { 
            result += row；
        }

各行の文字列を結合する。

www.DeepL.com/Translator（無料版）で翻訳しました。

dev.to

C++でLeetCodeの「Longest Palindromic Substring」問題を解く

Problem

https://leetcode.com/problems/longest-palindromic-substring/

Answer

O(N3)

class Solution { 
private: 
    bool check(string &subString, int subStringSize){
        int i = 0;

        while(i < j) {
            if(subString[i] != subString[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

public:
    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        vector<string> substrings;

        for (int i = 0; i < inputStringSize; i++) {
            string tmp = "";

            for (int j = i; j < inputStringSize; j++) {
                tmp += s[j];
                substrings.push_back(tmp);
            }
        }

        int maxLength = 0;
        string longestSubstring = substrings[0];
        int subStringsSize = substrings.size();

        for (int i = 0; i < subStringsSize; i++) {
            int subStringSize = substrings[i].size();

            if(check(substrings[i], subStringSize - 1)){
                if(subStringSize > maxLength){
                    maxLength = subStringSize;
                    longestSubstring = substrings[i];
                }
            }       
        }
        return longestSubstring;
    }
};

この問題の解決策を考えてみよう。

この問題は、すべての部分文字列をチェックすることで解決できる。 ある部分文字列が回文かどうかは、その部分文字列の先頭と末尾から中央に向かって同じ文字があるかどうかで判断する。

例えば、文字列 babd をすべての可能な部分文字列に分割してみよう： b, ba, bab, babd b, ba, bab, babd, d.

次に、部分文字列の先頭と末尾の文字が同じかどうかを、部分文字列の途中までチェックする。

例えば bは最初の文字（b）と最後の文字（b）が同じなので回文の部分文字列である。 baは最初の文字(b)と最後の文字(a)が同じではないので、回文の部分文字列ではない。 bab は最初の文字 (b) と最後の文字 (b) が同じなので、回文部分文字列である。 babdは最初の文字（b）と最後の文字（d）が同じではないので、回文部分文字列ではない。

この処理をすべての部分文字列に対して続ける。

しかし、この解決策は、すべての部分文字列を作成するのにO(n2)、部分文字列が回文かどうかをチェックするのにO(n)の時間複雑度を持つため、性能は最適ではない。

時間複雑度 O(n2)だけの解決策がある。この解を探ってみよう。

O(N2)

class Solution {
private: 
    bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
        if(startIndex == endIndex){
            return dp[startIndex][endIndex] = true;
        }
        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }
        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }
    }
public:
    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        int startIndexOfMaxLength = 0; int maxLength = 0;
        vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
        for(int g = 0; g < inputStringSize; g++){
            for(int startIndex = 0, endIndex = g; endIndex < inputStringSize; startIndex++, endIndex++){
                solve(dp, startIndex, endIndex, s);
                if(dp[startIndex][endIndex] == true){
                    if(endIndex - startIndex +　1 > maxLength){
                        startIndexOfMaxLength = startIndex;
                        maxLength = endIndex - startIndex + 1;
                    }
                }
            }
        }
        return inputStringSize.substr(startIndexOfMaxLength, maxLength);
    }
};

本解法は動的計画法を用いている。 小問題に分割された問題を解き、小問題の答えをメモとして保存します。

解の内部を見てみよう。

    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        int startIndex = 0; int maxLength = 0;
        vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));

inputStringSize 変数は引数 s の長さ。 startIndex変数は対象となる文字列の先頭インデックスである。 maxLength変数は最長の回文文字列です。 dp変数は、小さなプログラムをメモとして保存し、2次元配列として答えを保存したものです。

次に、2重ループで使用されるsolve関数を見てみよう。

    bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
        if(startIndex == endIndex){
            return dp[startIndex][endIndex] = true;
        }
        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }
        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }
    }

startIndexがendIndexと等しい場合、dp[startIndex][endIndex]にtrueを代入する。 例えば startIndex が 0 で endIndex が 0 の場合、 inputString は1語である。これは回文文字列に等しい。

        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }

dp[startIndex][endIndex] に true を代入するのは、endIndex - startIndex が 1 に等しく、かつ s[StartIndex] が s[endIndex] に等しい場合である。

例えば s が aa で、startIndex が 0 で、endIndex が 1 の場合、endIndex(1) - startIndex(0) は 1 に等しく、s[0] は a で、s[1] は a で、互いに等しい。 これは回文文字列である。

dp[startIndex][endIndex] に false を代入するのは、endIndex - startIndex が 1 で、かつ s[StartIndex] が s[endIndex] と等しくない場合です。

例えば s が ab で、startIndex が 0 で、endIndex が 1 で、endIndex(1) - startIndex(0) が 1 で、s[0] が a で、s[1] が b で、互いに等しくない場合。 これは回文文字列ではない。

        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }

s[startIndex]とs[endIndex]が等しく、かつdp[startIndex + 1][endIndex - 1]がtrueの場合、dp[startIndex][endIndex]にtrueを代入する。 例えば sがabaでstartIndexが0でendIndexが2の場合、s[startIndex]とs[endIndex]は等しい。 sがabaでdp[0 + 1][2 - 1]が真なら回文文字列。 dp[1][1]は小さい部分文字列から計算されるので、すでに計算されています。dp[1][1]がbなので、dp[1][1]はtrueです。

s[startIndex]とs[endIndex]が等しくないか、dp[startIndex + 1][endIndex - 1]が真でない場合、dp[startIndex][endIndex]に偽を代入します。 例えば sがabcd、startIndexが0、endIndexが3、dp[0 + 1][3 - 1]が偽の場合、回文文字列ではありません。 dp[1][2]は小さい部分文字列から計算されるので、すでに計算されています。dp[1][2]はbcなので偽です。

        for(int g = 0; g < inputStringSize; g++){
            for(int i = 0, j = g; j < inputStringSize; i++, j++){
                solve(dp, i, j, s);

ループは、1つの単語からすべての単語までのすべての部分文字列に対してsolve関数を実行する。 例えば inputStringSizeはabaである。 まず、solve(dp, 0, 0, aba)。部分文字列が a なので、dp[0][0] が真になる。 次に、solve(dp, 1, 1, aba). dp[1][1] は部分文字列が b なので真である。 dp[2][2] は部分文字列が a なので真である。

dp[0][1] は部分文字列が ab なので偽である。 dp[1][2] は部分文字列が ba なので偽である。 dp[0][2] は部分文字列が aba なので真である。

                if(dp[startIndex][endIndex] == true){
                    if(endIndex - startIndex +　1 > maxLength){
                        startIndexOfMaxLength = startIndex;
                        maxLength = endIndex - startIndex + 1;
                    }
                }

solve関数で計算されたdp[startIndex][endIndex]が真で、かつmaxLengthである endIndex - startIndex + 1 が現在のmaxLengthより大きければ、startIndexをstartIndexOfMaxLengthに、endIndex - startIndex + 1 をmaxLengthに再割り当てする。

最後に，longestPalindrome関数は，最長の回文部分文字列であるinputStringSize.substr(startIndexOfMaxLength, maxLength)を返します．

英語で書いたものを機械翻訳で日本語に翻訳しています。

dev.to

C++でLeetCodeの「Longest Substring Without Repeating Characters」問題を解く

Problem

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Answer

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_map<char, int> map;
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

この問題の解答を考えてみよう。

入力がasapdaのとき、答えは4（sapd）である。 文字を先頭から見ていく。最初のa が現れたとき、最も長い部分文字列の長さは 1 (a) である。

次にsが初めて現れ、最も長い部分文字列の長さは2（as）に伸びる。 次はaが再び現れる。aはすでに文字列の最初に出現しているので、カウントに含めることはできない。

今回の目的は文字を繰り返さずに最も長い部分文字列の長さを見つけることである。つまり、asaは正解ではない。

次にsの位置から文字を数え始めなければならない。 これは、ある文字が再び出現した場合、その文字が最初に出現した文字の次の文字から数え始めなければならないことを意味する。

次にpが初めて出現し、最も長い部分文字列の長さが3（sap）に伸びる。 次にdも初めて出現し、最も長い部分文字列の長さを4（sapd）に伸ばす。 最後にaが再度現れるが、同じ文字はカウントに含まないので数えない。

つまり、答えは4 (sapd)である。

上記の解答をコードで考えてみよう。 重要な点はある文字が再び出現したとき、その文字が最後に出現したときの位置の次の文字から数え始める必要があるということです。

文字に出会ったときのindexを保存する。 例えばasapdaの場合、aはindexが0、sはindexが1である。

a が再び出現したときは、最初の a の次のインデックスから数え始め、新しい a のindexで a のindexを更新する必要がある。 同じ文字のindexを複数保存する必要はない。 Mapは一意なkeyとvalueのペアを格納できるので、この問題に適している。文字をkeyとして、そのindexをvalueとして格納する。

そして、2つの変数が必要になります。1番目の変数はカウントを開始する場所を示し、2番目の変数はカウントを終了する場所をします。 答えのコードを詳しく見てみよう。

        std::unordered_map<char, int> map;
        int maxLength = 0;
        int left = 0;

mapはMapデータ構造として宣言し、文字をkey、そのindexをvalueとして格納する。 maxLength変数は最も長い部分文字列の長さを数え、left変数はどこからカウントを始めるかを示します。

        for (int right = 0; right < s.length(); right++) {

変数 right は文字をカウントし終える位置を進める。

            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

同じ文字に再度出会ったら、カウントを開始する位置であるleftを更新する。 しかし、leftは現在の位置から戻ってはならない。leftを現在のleftと元のleftの大きい方に再割り当てする。

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

map[s[right]] = right は文字をkeyとして、そのindexをvalueとして格納する。

std::max(maxLength, right - left + 1) は maxLength を現在の maxLength と right (カウント終了位置) から left (カウント開始位置) を引いた値の大きい方で更新する。

インデックスは0から始まるので、正確な文字カウントを保証するために1を加える。

英語で書いたものを機械翻訳で日本語に翻訳しています。 dev.to

C++でLeetCodeの「Add two numbers」問題を解く

Problem

https://leetcode.com/problems/add-two-numbers/description/

Answer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

まず、期待される出力を考えてみよう。

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

l1とl2の数字を順番に合計すれば出力が得られる。

2 + 5 = 7
4 + 6 = 10 -> 0 // 4 + 6 = 10. 次の桁に1を運び、残りの桁を切り捨てる。
3 + 4 = 7 -> 7 + 1 = 8 // 前の桁から繰り越した1を加える。

Output: 7, 0, 8

次に、この操作をコードで表す必要がある。

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0;

関数の結果は ListNode* なので、dummy を ListNode* 型の変数として定義する。 各桁を合計するために各ノードを参照する必要があるので、dummy ポインタを参照するために temp 変数を定義する。 carry`変数を定義して、繰り越された数値を格納する。

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }

全ての l1 と l2 の数値を計算する必要がある。 つまり、 l1 と l2 が NULL で carry が 0 になるまで計算を続けなければならない。

もし l1 が NULL でなければ、l1 の値を sum 変数に加える。 現在の l1 の値は計算済みなので、l1 ポインタを次のポインタに移動する。

同じことを l2 にも行う。

            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

前の桁から carry がある場合は、それを sum 変数に追加し、次の桁に繰り越す必要がある新しい値で carry を更新する必要がある。

sumの最初の桁を新しいNodeに代入し、この新しいNodeを temp->next に代入する。 これは新しい Node を dummy の ListNode に追加するが、新しい Node を直接 dummy->next に代入しない。

なぜなら dummy と temp は同じポインタを持っているからだ。 この理由は、関数の最後で新しい ListNode の先頭を返す必要があるからである。

temp は l1 と l2 を計算するためのポインタであり、dummy は新しい ListNode の先頭を返すためのポインタである。

本記事は英語から日本語に翻訳しています。 dev.to

TypeScriptにおける Record 型の実装を理解する

TypeScriptのRecord型とは？

まず、TypeScriptのRecord機能について説明します。

Record型の説明は以下のURLで確認できます： https://www.typescriptlang.org/docs/handbook/utility-types.html#recordkeys-type

Record型は、2つの型を受け入れることで、ある型を別の型にマッピングします。

以下が例です：

type RGBColors = Record<'red' | 'green' | 'blue', number>；

ここで、Record型は、number型（第2引数）を "red"、"green"、"blue"（第1引数）のユニオンにマッピングします。

その結果、次のようになります：

type RGBColors = {
"red": number；
"green": number；
"blue": number；
}

TypeScript の Record 型の実装を理解する

以下のURLでRecord型の実装を確認することができます： https://github.com/microsoft/TypeScript/blob/5d8ef4bdcb8bdbd4307c74a07b01e3bdf6e04b6a/lib/lib.es5.d.ts#L1590

/**
 * Construct a type with a set of properties K of type T
 */
type Record<K extends keyof any, T> = {
    [P in K]: T;
};

Record型は2つの引数を受け取ります：

最初の引数は K extends keyof any で、これは "string" | "number" | "symbol" に対応する。したがって、第一引数は "string" | "number" | "symbol" 型です。 第2引数のTはすべての型を受け入れることができます。

では、Record型の中を見てみましょう。 key は [P in K] です。in キーワードは、KをループしてPとしてマッピングするために使われます。

例えば、Kが"red"、"green"、"blue"のとき、[P in K]は"red"、"green"、"blue"のkeyを生成する。

先ほどのRGBColors型を再確認してみましょう：

type RGBColors = Record<'red' | 'green' | 'blue', number>；

// これは、上記のRGBColorsと同等です。
type RGBColors = {
"red": number；
"green": number；
"blue": number；
}

TypeScriptのRecord型についての理解が深まれば幸いです。

英文:

dev.to

C++でLeetCodeの「Two Sum」問題を解く

## Problem
https://leetcode.com/problems/two-sum/description/?envType=featured-list&envId=top-interview-questions

## Answer (Brute Force)
```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                } 
            }
        }

        return {};
    }
};
```

この問題を解決するためには、nums配列の各要素の組を合計する必要があります。

例えば
nums = [1, 2, 3, 4]
target＝5

1 + 2 = 3;
2 + 3 = 5;
3 + 4 = 7;

2重のforループを使用する必要があります。
最初のループは、nums配列の最後から2番目の要素まで繰り返し処理します。これは、2つの要素を合計する必要があるため、最後の要素は最初のループに含める必要がないためです。
2回目のループは、同じ組み合わせを2回繰り返さないように、i + 1の位置から開始します。

最後に、この2つの要素の和がtarget引数に等しい場合に、2つの要素のインデックスをvector<int>の形で返します。

 

return {i, j}という文では、{i, j}がiとjの要素を含むvector<int>を作成します。

「コンピュータはなぜ動くのか」まとめ。GW企画

GWなのでたくさん本を読んでいきたいと思います。

読むだけではあまり知識が定着しなさそうなので、自分で大事そうなところをまとめてアウトプットしていきますー！

 

「コンピュータはなぜ動くのか」

まずは1冊目の「コンピュータはなぜ動くのか」をまとめていきます。

 

shop.nikkeibp.co.jp

 

本の概要を簡単に説明すると、前半はコンピュータの基礎知識について学びます。

中盤から後半にかけては、データ構造・データベース・TCP/IPなどの知識を学んでいきます。

 

コンピュータの三大原則

以下が三大原則です。

  1. コンピュータは、入力・演算・出力を行う装置
  2. プログラムは、命令とデータの集合体
  3. コンピュータの都合は、人間の感覚と異なる場合がある

 

「ハードウェア」は入力・演算・出力の3つを行う装置。

例えば、「1」と「2」という情報をキーボードから入力して、プログラミングでそれらを足し算するという演算を行い、その結果である「3」を画面に表示するのがコンピュータです。

 

Webの閲覧やゲームなどの複雑な機能も、結局は入力・演算・出力の3つが組み合わさって出来ているのです。

 

 

「プログラム」は命令とデータの集合体です。

命令とは、入力・演算・出力をコンピュータに指示するものです。

データとは、命令の対象となる入力情報または命令の結果によって得られる出力情報のことです。

 

コンピュータの都合は、人間の感覚と異なる場合があります。

例えば、コンピュータの世界では文章・画像・音楽など全ての情報を2進数の数字で表します。

このようにコンピュータの都合があるので、人間にとっては難しく感じることもあるのです。

 

2進数については下記の記事をご覧ください。

bit byte 2進数とは？ - shiki0331’s blog

 

 

ハンド・アセンブル

コンピュータは、前述した通りに2進数の数字しか理解することができません。

これを「マシン語」といいます。

 

しかし、2進数の数字の羅列であるマシン語を人間が使うには大変ですよね。

 

そこで、少しでも人間が理解しやすいように英語に似たニックネームを付けてプログラムを作成することを「ニーモック」と呼び、ニーモックを使ってコンピュータに命令するプログラミング言語を「アセンブリ言語」と呼びます。

 

コンピュータは「マシン語」だけしか理解ができないので、「アセンブリ言語」を理解できません。なので、コンピュータに最終的なお願いをするときは「マシン語」に変換してから伝えてあげなくてはいけません。

 

このアセンブリ言語で記述したプログラミングをマシン語に変換する作業を「ハンド・アセンブル」といいます。

 

ちなみに現在よく使われている「Ruby」や「PHP」は「高級言語」といいます。

これらの言語も最終的には「マシン語」に変換されてコンピュータに伝えていることを理解しておきましょう。

 

オブジェクト指向プログラミング

オブジェクト指向プログラミングには「クラス」と「オブジェクト」という概念があります。

 

「クラス」は「オブジェクト」の定義であり、「クラス」が実体を持ったものが「オブジェクト（=クラスのインスタンス）」。

 

現実に例えると、お菓子のクッキーを作る際の「クッキーを作るための型」が「クラス」で「くり抜かれたクッキー」が「オブジェクト」です。

 

オブジェクト指向には大きな三本柱があります。

「継承」・「カプセル化」・「多態性」です。

 

「継承」はクラスの機能を新しいクラスを作成する際に継承することで、簡単に前のクラスの機能＋新しい機能を作成することができます。

また機能を変更する際にも、継承元のクラスを変更するだけで継承先のクラスも変更することができます。

 

「カプセル化」は必要のないクラスの情報をブラックボックス化することで、使いやすい部品となり保守性が上がります。

 

「多態性」は同じメッセージで複数の操作が行えるクラスを作れば、クラスを使う人は覚えることが少なくて済みます。

 

どれも大型プロジェクトを作成する際に凄く役立つ機能なので、個人での小さい開発などではオブジェクト指向の良さが実感しにくいかもしれません。

 

データベース

以下のような3つのテーブルがあるとします。

　商品       　　           売り上げ                 　   顧客
・商品ID           　　・売り上げID          　  ・顧客ID
・商品名     1対多    ・商品ID   　　多対1    ・顧客名
・単価               　　・顧客ID          　         ・住所
                          　　・売上数量   　             ・電話

 

商品ID・売り上げID・顧客IDがそれぞれ主キーとなります。

「主キー（primary key）」はレコードを特定するIDです。

 

売り上げデーブルには、顧客IDと商品IDというフィールドがあります。

これらは、他のテーブルの主キーであり、売り上げテーブルにとって「外部キー（foreign kye）」と呼ばれます。

 

同じ値の主キーと外部キーによって複数のテーブルが関連づけられ（relation）データを芋づる式に取り出せます。

 

リレーションシップの形態は「多対多」とはなってはいけません。複数のテーブルを芋ずる式にたどることが困難になるからです。

 

「多対多」になってしまう場合は、上記のリレーショシップのように2つのテーブルの間にもう一つテーブルを作成します。

これを「結合テーブル（リンクテーブル）」と呼びます。

 

DBMSの機能の一つとして、テーブルの個々のフィールドに「インデックス（index」を設定できます。

 

インデックスは、データの検索と並べ替えの速度を向上させる内部的な仕組みです。

 

フィールドにインデックスを設定すると、そのフィールドのためのインデックス・テーブルが自動的に作成されます。

インデックス・テーブルは、フィールドの値と、そのフィールドを持つレコードの位置を記録したものです。

 

例えば、顧客テーブルの顧客名フィールドにインデックスを設定すると、「顧客名」と「ファイル上の位置」という2つのフィールドを持ったインデックス・テーブルが作成されます。

 

インデックス・テーブルは元のテーブルに比べてフィールド数が少ないので、高速に検索や並び替えが行えます。

インデックス・テーブルで検索や並び替えを行ってから、元のテーブルのレコードを取り出します。

 

そうなると、全てのフィールドにインデックスを設定すれば良いのでは？と思いますね。

 

しかし、インデックスを設定するとテーブルにレコードが登録されるたびにインデックス・テーブルの更新処理が必要になります。

 

検索と並び替え速度向上の代償に、登録の速度が低下するのです。

 

そのため頻繁に検索や並び替えが行われる場合にだけインデックスを設定するべきです。

 

 

トランザクションに関して、SQLの命令が用意されています。

  1. DBMSにトランザクションの開始を知らせるBEGIN TRANS-ACTION命令
  2. トランザクションの終了を知らせるCOMMIT命令
  3. トランザクションの途中でトラブルが発生した場合に、トランザクション開始前の状態にデータベースの内容を戻すROLL BACK

 

 

TCP/IPネットワーク

インターネットを通して情報が電気信号として伝わるからコンピュータ同士で情報を交換できます。

 

電気信号を受信したコンピュータは、それが自分宛てものであれば受け取り、そうでなければ無視します。

電気信号の宛先は「MAC（Media Access Control）アドレス」と呼ばれる番号で指定されます。

 

個々のネットワーク・カードが持つROM（Read Only Memoly=読み出し専用メモリー）には、あらかじめ一枚ずつ異なるMACアドレスが焼きこまれている一意な番号です。

 

MACアドレスだけでインターネットを実現すると、インターネットに接続している膨大な数のコンピュータには、何もグループ化されていないMACアドレスがあるだけです。

 

これでは情報の送り先を見つけるのに、もの凄く時間がかかってしまいます。

 

そこで、TCP/IPネットワークでは、ハードウェア的なMACアドレスとは別の、ソフトウェア的な番号をコンピュータごとに設定しています。

この番号が「IPアドレス」です。

 

ただし、最終的に情報を受け取るネットワーク・カードを識別するのがMACアドレスであることには変わりありません。

 

IPアドレスによって、例えば1~3つ目の数値で企業を表、4つ目の数値で企業内のコンピュータを表すようなグループ化が簡単に行えます。

IPアドレスもMACアドレスと同様に一意な数値です。

 

インターネットの世界ではIPアドレスという数値でコンピュータを識別しているはずなのに、普段私たちは「www.example.com」のような文字列でWebサーバーを指定できていますよね。

 

実は、インターネットには「www.example.com」という文字列をIPアドレスに変換してくれる「DNS（Domain Name System）サーバー」というものが存在しています。

 

 

「TCP」はデータの受信者と送信者がお互いに相手の確認を取りながら、確実にデータを受け渡すためのプロトコルです。

他のも大きなデータを「パケット（小包）」と呼ばれる単位に分割して送信し、それを受信側で元のデータに復元するためのプロトコルもあります。

 

 

 

少しだけですがまとめてみました。

途中難しい章もあって飛ばした部分もありましたが、基礎を学ぶ上では良い本だったなと思います。

 

amazonのkindle版では1000円ちょっとで買えるので、是非興味ある方は読んでみてください！