プロトコルとは

プロトコルについて簡単にまとめると・・・
・ネットワーク上でコンピュータが相互に通信するために必要な「約束事」を定めたもの！
・通信するコンピュータのメーカーや機種が異なっていてもプロトコルが同じなら通信できる！

プロトコルってなんですか？

プロトコルっていうのはだな、簡単に言うとコンピュータ同士でやり取りするのに必要な言語のことだ。

日本語しか喋れないやつと英語しか喋れないやつが会話しても正しくコミュニケーションできないだろ？それと同じでプロトコルが違うとコンピュータ間で上手く通信ができなくてちゃんとデータが送れなくなるんだ。

なるほど、プロトコルって大事なんですね。あ、言語みたいなものってことはプロトコルも何種類かあるんですか？

そうだな、沢山あるぜ。代表的なところだとIP、TCP、HTTPなんかだな。こういうプロトコルを体系的にまとめたものをネットワークアーキテクチャっていうんだけど、「TCP/IP」もその一つだな。

共通のプロトコル(言語)を使うおかげでメーカーやCPUやOSが違うコンピュータ同士でもお互いに通信ができるんだぜ。

なるほど・・・プロトコル・・・必要・・・

2つの文字列の編集距離を求める関数

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回は編集距離について書いていきます。

2つの文字列がどの程度異なっているのかを調べる基準として編集距離というものがあります。具体的には1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数のことです。

編集距離については以下の記事で詳しく述べられています。

qiita.com

# 編集距離関数
def edit_distance(s1, s2):
    s1 = '#%s' % s1
    s2 = '#%s' % s2
    n1 = len(s1)
    n2 = len(s2)
    d = [[None for _ in range(n2)] for _ in range(n1)]
    for i in range(n1):
        d[i][0] = i
    for j in range(n2):
        d[0][j] = j
    for i in range(1, n1):
        for j in range(1, n2):
            mismatch = 0 if s1[i] == s2[j] else 1
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + mismatch)
    return d[-1][-1]

s1 = "castle" # 城
s2 = "cattle" # 牛

# 関数呼び出し s1とs2の編集距離を求める
edit_dis = edit_distance(s1, s2)
print(edit_dis)

プリエンプションとは

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回はプリエンプションとは何かについてざっくり書きました。

たまに本とかで見るプリエンプションってなんですか？

ああ、プリエンプションってのは、コンピュータが実行中のタスクを一時的に中断することだな

そんで中断したタスクは一旦置いて、その代わり別のタスクを実行するんだ、まあざっと下に概要をまとめてみたぜ

複数のタスクを並行して実行するためには、タスクスケジューラーが決定した時刻に、実行中のタスクAから他のタスクBへと強制的に切り替えることが必要となる。これを「プリエンプションを行なう」と言う。
「プリエンプト」とは「先取りする、差し替える」の意味。

具体的にプリエンプションはなんの役に立つんですか？

んん、役に立つというよりか、なきゃかなり不便なレベルだな。プリエンプションが出来ないと動かしたいアプリケーションがあってもその時実行してるアプリケーションが終了するのを待ってからじゃない動かせないだろ

確かに・・・プリエンプションがあるおかげで他のアプリケーションに影響を受けずに処理が行なえるんですね

まあそうゆうことだ、ただ中には一時的に中断したら困る命令もあるから、そいつらはプリエンプションがされないように設定されてたりもするんだぜ

【C言語】配列ソートの関数の処理速度を比べてみる

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回は配列ソートの関数の処理速度について調べてみました。

数字がランダムに入ってある配列を先頭から小さい順に並べ替える（昇順ソート）をしました。

昇順ソートのアルゴリズムは色々あるのですが、アルゴリズムによって並べ替えにかかる時間が異なります。

今回は挿入ソート、選択ソート、バブルソートの代表的な３つのアルゴリズムを用いて同じ配列をソートさせ、ソートにかかった時間を計測し比較しました。

以下のプログラムを実行するとこんな感じになります。

選択ソートが若干遅いですね。

詳しいアルゴリズムの解説は割愛します。

このプログラムではclock()関数を使って処理時間を測定しましたが、正確にはclock関数が表すのはCPU時間なので、CPUの稼働率が100%でないと実際の処理時間と若干の誤差が生じます。

しかし大体どんな感じかを調べる暗いなら特に問題はないかと思います。

#include <stdio.h>
#include <time.h>
#define swap(type, x, y) do {type t; t=x; x=y; y=t; } while (0)

/* 関数宣言 */
void insert_sort(int randAry[], int ary_size);
void select_sort(int randAry[], int ary_size);
void buble_sort(int randAry[], int ary_size);

    
    // 挿入ソード関数
    void insert_sort(int randAry[], int ary_size){
        int i;
        int j;
        int x;
        // 挿入ソート前
        for(i = 0; i < ary_size; i++)
        {
            printf("%d ",randAry[i]);
        
        }    

        // 挿入ソートアルゴリズム
        for(i = 0; i < ary_size; i++)
        {
            x = randAry[i];

            j = i;
            while ((randAry[j - 1] > x) && (j > 0)){
                randAry[j] = randAry[j - 1];
                j = j - 1;
            }        
            randAry[j] = x;
            
        }

        printf("\n");
        // 挿入ソート後
        for(j = 0; j < ary_size; j++)
        {
            printf("%d ",randAry[j]);
        
        }
        printf("\n");
    }

    // 選択ソート関数    
    void select_sort(int randAry[], int ary_size){
        int i;
        int j;
        int k;
        int max;
        int max_index;
        // 選択ソート前
        for(i = 0; i < ary_size; i++)
        {
            printf("%d ",randAry[i]);
        
        }    

        // 選択ソートアルゴリズム
        for(i = ary_size - 1; i > 0; i--)
        {
            max=randAry[0]; max_index = 0;
            for(j = 1; j <= i; j++){
                if(randAry[j] >= max) { max = randAry[j]; max_index=j;}
            
            }
            swap(int, randAry[max_index], randAry[i]);
            
        }

        printf("\n");
        // 選択ソート後
        for(k = 0; k < ary_size; k++)
        {
            printf("%d ",randAry[k]);
        
        }

        printf("\n");

    }

    // バブルソート関数    
    void buble_sort(int randAry[], int ary_size){
        int i;
        int j;
        int k;
        int temp;
        // バブルソート前
        for(i = 0; i < ary_size; i++)
        {
            printf("%d ",randAry[i]);
        
        }    
        // バブルソートアルゴリズム
        for(i = 0; i < ary_size; i++)
        {
            for(j = ary_size - 1; j > i; j--){
                if(randAry[j] < randAry[j-1]) {
                    temp = randAry[j];
                    randAry[j] = randAry[j-1];
                    randAry[j-1] = temp; 
                }
            }
        }

        printf("\n");
        // バブルソート後
        for(k = 0; k < ary_size; k++)
        {
            printf("%d ",randAry[k]);
        
        }

        printf("\n");

    }

/* main(処理始まりの関数) */
int main(void)
{
    int randAry[] = {24, 71, 35, 82, 50, 63, 77, 71, 1, 15, 24, 85, 99, 3, 57};
    int temp_Ary1[] = {24, 71, 35, 82, 50, 63, 77, 71, 1, 15, 24, 85, 99, 3, 57};
    int temp_Ary2[] = {24, 71, 35, 82, 50, 63, 77, 71, 1, 15, 24, 85, 99, 3, 57};
    int ary_size = sizeof(randAry) / sizeof(randAry[0]);
    time_t start,end;
    clock_t c1,c2;
    
    c1 = clock();    
    // 選択ソート呼び出し
    select_sort(randAry, ary_size);    
    c2 = clock();
    printf("select_sort_time = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
    printf("\n");   

    c1 = clock();
    // 挿入ソート呼び出し
    insert_sort(temp_Ary1, ary_size);
    c2 = clock();
    printf("insert_sort_time = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
    printf("\n");

    c1 = clock();    
     // バブルソート呼び出し
    buble_sort(temp_Ary2, ary_size);
    c2 = clock();
    printf("buble_sort_time = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
    printf("\n");
    return 0;

}

参照局所性とはなにか

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回はメモリアクセスにおける参照局所性とは何かについてざっくり書いていきます。

参照局所性とは

 参照局所性ってなんですか？ 

参照局所性ってのは「あるプログラムがアクセスする命令やデータのアドレスは特定の場所に集中する」っていうことだ。洋服でもよく着るやつはクローゼットの手前の方にまとまってるだろ。

なるほど・・・じゃあ時間的とか空間的局所性っいうのはどういうものなんですか？

参照局所性には時間的局所性っていうのと空間的局所性ってのがあって、時間的局所性は「一度アクセスしたアドレスそのものは近いうちにまたアクセスする可能性が高い」ってことだ。

そして空間的局所性は「一度アクセスしたアドレスに近いアドレスは近いうちにアクセスする可能性が高い」ってことだぜ。

うーん、なんかもっと具体的な例とかないんですか？

 時間的局所性の例としては、ループ処理や関数呼び出し、空間的局所性の例ではプログラムそのものや配列なんかが挙げられるな。

なるほど・・それで参照局所性を使うとなにかいいことがあるんですか？

仮想メモリやキャッシュメモリではこの参照局所性を最大限に生かすことで、高速と大容量を両立させようとしているんだよ。

よく使う道具はリュックの中に入れておくより、すぐに取り出せるようにポケットに入れておいた方が便利だろ？まあそういうことだ。

ありがとうございます。

サブルーチンとはなにか

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回はサブルーチン化とは何かについてざっくり書いていきます。

サブルーチンとは

サブルーチンってなんですか？たまに聞くけどよくわからなくって・・・

サブルーチンっていうのは、まあ平たく言えば関数のことだ。一番最初に動くメイン関数以外のな。

プログラムのソース中で、繰り返し現れる作業を関数にしてまとめることをサブルーチン化っていうんだ。

なるほど、サブルーチン化にはどんなメリットがあるんですか？

コードがすっきりするからプログラムの可読性や保守性を高く保てるっていうメリットがあるな。あとはよく使われるサブルーチンがキャッシュに格納されることでコンピュータの動作が高速になったりもするらしいぜ。

サブルーチンなんて変な名前つけないで関数って呼べばいいのに・・・

処理を行ったあとに戻り値を返すものを関数、返さないものを手続きと区別して呼ぶこともあるから、それらをまとめてサブルーチンって呼ぶらしいぜ。

書きなぐりnumpy、scipy、pandas、matplotlib

Numpy

配列作成はnp.array([1,2,3,4])

データ型.dtype　次元数.ndim　要素数.size

Numpyで乱数を発生させる。

random.seed(0)

#正規分布(平均0,分散1)の乱数を10個発生

norm_random_sample_data = random.randn(10)

random.choice(norm_random_sample_data,10))

# 10個を抽出（重複あり,復元抽出）

random.choice(norm_random_sample_data,10,replace=False)

# 10個を抽出（重複なし、非復元抽出)

zero_data = np.zeros*1

結果　-0.9999999852953547ほぼ-1

Pandas

データのハンドリング、操作が可能となる。表計算やデータベース。

from pandas import Series,DataFrame

モジュールの説明

Series

sample_pandas_data = pd.Series([0,1,2,3,4,5,6,7,8,9])

print(sample_pandas_data)

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

dtype: int64

こんな感じでインデックス(左)と入力した数(右)を表示する。.valuesでアクセスできる。

pd.Series([0,1,2,3,4,5,6,7,8,9],index=['a','b','c','d','e','f','g','h','i','j'])

こういう感じでインデックスを指定したりもできる。

DataFrame

attri_data1 = {'ID':['100','101','102','103','104']

        ,'city':['Tokyo','Osaka','Kyoto','Hokkaidao','Tokyo']

        ,'birth_year':[1990,1989,1992,1997,1982]

        ,'name':['Hiroshi','Akiko','Yuki','Satoru','Steeve']}

attri_data_frame1 = DataFrame(attri_data1)

print(attri_data_frame1)

#以下のようにテーブルみたいなのができる。

ID birth_year city name

0 100 1990 Tokyo Hiroshi

1 101 1989 Osaka Akiko

2 102 1992 Kyoto Yuki

3 103 1997 Hokkaidao Satoru

4 104 1982 Tokyo Steeve

.Tでテーブルを転置できる。

.dropで削除できる。

attri_data_frame1.drop(['birth_year'],axis=1)

axis=0で行の削除

axis=1で列方向の削除

pd.merge(attri_data_frame1,attri_data_frame2)

でデータのマージ(内部結合)キーを明示しない場合は自動で見つけて結合してくれる。

attri_data_frame2.groupby("sex")["math"].mean()

Matplotlibの基礎

データビジュアライゼーション、散布図、ヒストグラム

データを可視化するpythonライブラリー

Matplotlib#メイン

Seaborn#図をきれいにすることが出来る

import matplotlib.pyplot as plt

import matplotlib as mpl

import seaborn as sns

plt.plot(x, y, "o")#散布図

#以下でも散布図が描ける

plt.scatter(x, y)

plt.hist()でヒストグラムを作る。

os.path.split() ディレクトリ名とファイル名に分離

*1:2,3), dtype='i')

print("・0でint型　\n", zero_data)

・0でint型　

 [[0 0 0]

 [0 0 0]]

N = 10**6

[random.random() for _ in range(N)]#100000回乱数を発生させたリストを作る。このリストを使ってnp.array([1,2,3,4])とかでnumpy配列が作れる。

%timeitは何回か同じ計算をしてベスト3の平均計算時間を返す。

Numpyで3×3の行列を作る。

sample_multi_array_data1 = np.arange(9).reshape(3,3)

print(sample_multi_array_data1)

[[0 1 2] #インデックス 0

[3 4 5] #インデックス 1

[6 7 8]]#インデックス 2

sample_multi_array_data1[0,:]はインデックス0の行で列はすべて取り出す。横

sample_multi_array_data1[:,0]はインデックス0の列で行はすべて取り出す。縦

行列の積はnp.dot(A,B)

要素の積はA*B

Scipy

Scipyは科学技術計算するためのモジュールで多様な数学処理が可能。

線形代数の計算とかできる。逆行列、固有値、固有ベクトル、最適化

scipy.linalg線形代数用のモジュール

linalg 行列式.det 逆行列.inv 固有値と固有ベクトルの取得 .eig

最適化計算を使って方程式の解を求めてみる。

f(x)=x2+2x+1 = 0 の解

newton関数を使う

from scipy.optimize import newton

# 計算実行

print(newton(sample_function,0