パソコン日記

気づいたことをまとめる

Pythonでファイルの1列目を辞書(ディクショナリ)キーとして、2列目以降を値として指定する

Pythonで辞書(ディクショナリ)をうまく使いたい

pythonで辞書(ディクショナリ)はキーで値を得ることができ 、非常に便利な機能の一つです。プログラムのインプットファイル的なものを作るときに、1列目を辞書のキーとして、二列目以降をその値として読み込みたいと思ったのでプログラムを書いてみました。すぐ忘れてしまうのでメモ的な記事です。

ファイルの読み込み

次のようにファイルを読み込んでみました。

with open(inputfile, 'r') as f:
    lines = [x.strip() for x in f.readlines() if x.strip() != ""]

空白行は読み込みたくないので、最後の

if x.strip() != ""

で読み込まないようにしました。

空白で区切られたファイルの1列目をキー、2列目以降を値としてディクショナリを作成する

次のように、辞書内包表記で書いてみました。

dic = {x.split(' ', 1)[0]:x.strip().split(' ',1)[1] if len(x.split()) >= 2 else '' for x in lines}

ちょっと複雑?になってるのかもしれません。 最初の

x.split(' ',1)

は文字列xを一つ目の空白' 'で区切り、あとは区切らないという意味です。カンマで区切りたければ","で、2番目まで区切りたかったら1を2にすればいいみたいです。区切られた文字列の1番目(添字は0)をキーとし、2番目(添字は1)を値とします。 また、1列目だけ指定したいときもあると思うので

 if len(x.split()) >= 2 else ''

とし、空白などで区切られてなかったらキーのみ指定し、値に''をいれておきました。 これで意図したディクショナリを作ることができると思います。

Pythonのfloat型からint型へのキャスト(型変換)で気づいたこと

pythonでのfloat型からint型へのキャスト

pythonでfloat型からint型へキャストするときは次のようにすると思います。 今回はすべて対話型シェルで実行しました。

>>> a = 1.2
>>> int(a)
1

四捨五入されるのか切り捨てられるのか

ここで、小数点以下は四捨五入されるのか切り捨てられるのか気になりました。 次のようなキャストを行ってみました。

>>> a = 1.6
>>> int(a)
1

どうやら切り捨てられるみたいです。注意が必要ですね。

四捨五入してキャストする

使い所があるのか分かりませんが、四捨五入してキャストするには次のようにすればいいのかなと思います。

>>> a = 1.6
>>> int(round(a))

linuxでディレクトリのサイズを表示する(duコマンド)

ディレクトリ内のディレクトリやファイルの容量を表示する

du -csh ./*

これで現在のディレクトリに存在するファイルやディレクトリの容量を見やすい形で表示することができます。

duコマンド

duコマンドはディレクトリやファイルの容量を表示するコマンドです。しかし、オプションを何もつけずに実行するとサブディレクトリの容量までも表示されたり、人間にとってわかりにくい単位で表示されたりします。そこでオプションを使って見やすい形にします。

duコマンドのオプション

duコマンドには様々なオプションが準備されていますが、よく使うものをご紹介いたします。

du -c

指定したディレクトリのトータルの容量を表示することができます。

du -h

ガバイトやギガバイトなどの人間にとって見やす形式で表示してくれます。

du -s

サブディレクトリの容量を表示しません。

du -csh

これらをあわせると、指定したディレクトリ内にあるファイルやディレクトリのみの容量を表示してくれます。

C言語でバブルソートの実行時間を測る

ソートの実行時間を測る

以前の記事でプログラムの実行時間の測り方をご紹介いたしました。

1-compinfo.hatenablog.com

今回はバブルソートの実行時間を測定してみたいと思います。

バブルソートとは

バブルソート - Wikipedia

バブルソートwikipediaにあるように、ソートのアルゴリズムの一つで、隣り合う要素を比較しながらソートします。また、アルゴリズムが単純でプログラミングの学習によく用いられているそうです。

ソートの準備

バブルソートのプログラムを作る前に、ソートする配列を作らなければなりません。そこで、要素数Nのランダムな整数型の配列を生成するプログラムを作成しました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i;
    int N = 100;
    int n[N];

    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }
}

これで生成されるランダムな配列に対してソートを行ってみたいと思います。

マージソートのプログラム

マージソートのプログラムを次のように作ってみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i,j,t;
    int N = 10;
    int n[N];

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // 配列を表示
    printf("ソート前: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");

    // バブルソート
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }

    // 配列を表示
    printf("ソート後: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");
}

とりあえず確認のため要素数Nを10で実行してみると次の結果が得られました。

ソート前: 3362 5885 7590 2004 2490 2836 6035 697 7675 5956
ソート後: 697 2004 2490 2836 3362 5885 5956 6035 7590 7675

きちんとソートされているのが確認できました。

マージソートの実行時間を測る

プログラムを次のように変更し、マージソートの実行時間を測ってみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i,j,t;
    int N = 10000;
    int n[N];
    clock_t start, end;

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // バブルソート
    start = clock();
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }
    end = clock();

    printf("要素数: %d\n", N);
    printf("バブルソート実行時間: %f sec\n", (double)(end-start)/CLOCKS_PER_SEC);

}

これをコンパイルして実行すると、大体0.33秒あたりとなりました。この値は使っているコンピュータに依存してくると思います。 また、生成される配列は毎回異るので、実行するごとに実行時間が異なってしまいます。 要素数を増やしていくとどのような、相関があるのか気になったため、何回か実行した平均値をとって見たいと思います。 プログラムを次のようにしてみました。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int main(void) {
    int i,j,k,t;
    int N = 10000; //配列の要素数
    int M = 10; //実行回数
    int n[N];
    clock_t start, end;
    double total = 0.0; //各実行時間の和
    struct timeval tv;

    for(k=0; k<M; k++){
        // ランダムな配列を生成
        gettimeofday(&tv,NULL);
        srand(tv.tv_sec * tv.tv_usec);
        for(i=0; i<N; i++){
            n[i] = rand() % 10000;
        }

        // バブルソート
        start = clock();
        for(i=0; i<N-1; i++){
            for(j=i+1; j<N; j++) {
                if(n[j] < n[i]){
                    t = n[j];
                    n[j] = n[i];
                    n[i] = t;
                }
            }
        }
        end = clock();
        total += (double)(end-start)/CLOCKS_PER_SEC;
    }

    printf("要素数: %d\n", N);
    printf("実行回数: %d\n", M);
    printf("バブルソート平均実行時間: %f sec\n", total/M);

}

ランダムな配列を生成するときに、乱数の種の生成はsrand(time(NULL))を使っていました。 しかし、これでは乱数の種は秒単位で変わるので、今回のプログラムには適していません。 そこで、更に細かい時間で乱数の種を生成できるように、上記のようにしてみました。 さらに、バブルソートの実行回数は10回としており、収束が悪いですが、時間の都合上これで行い、 有効数字を2桁でとってみます。 自分のノートパソコンでの結果は次の通りになりました。(データはかなり雑です)

配列の要素数 : 平均の実行時間(秒)
1000 : 0.0027
10000 : 0.35
100000 : 20

素数増えると実行時間結構かかりました。図でも書こうかと思いましたけどやめました。

C言語でプログラムの実行時間を測る

プログラムの実行時間を測りたい

C言語でソートのプログラムを作ってテストしたいなと思いました。 せっかく作るなら実行時間を測って、ソートのアルゴリズムの性能を評価してみたいと思います。 そこで、今回の記事ではC言語での、実行時間の測り方をまとめてみたいと思います。

clock()を使う

C言語ではプログラム実行時からの時間を取得することができるclock()があります。 実行時間を測定したいところの前でclock()を実行し、それが終了するところで再びclock()で時間を取得し それらを引けば実行時間を得ることができます。また、clock()を使うには、 time.hのヘッダファイルをインクルードする必要があります。 次にサンプルを書いてみました。

#include <stdio.h>
#include <time.h>

int main(void) {
    clock_t start, end;
    start = clock();

    int i;
    for(i = 0; i < 1000000; i++){
    }

    end = clock();
    printf("%f sec\n", (double)(end-start)/CLOCKS_PER_SEC);

}

テストなので、何もしないforループを回して時間をかけました。また、秒で表示するためにはCLOCKS_PER_SECで割る必要があります。 さらにdouble型でキャストしました。

これでアルゴリズムの処理時間が測定できそうです。

C言語で関数を使う

C言語の関数とは

C言語で関数とは、ある一通りの処理をまとめたものです。今まで使ってきた"main()“や"printf()"も実は関数です。"main()"以外にも自分で関数を定義し、使っていくことができます。今回はC言語で関数を定義し、実際に使ってみたいと思います。

簡単な関数をつくってみる(void型)

はじめに、与えられた整数型の数字を足して、"printf()“で表示するプログラムを作ってみました。

include <stdio.h>

void sum(int d1, int d2){
    printf("%d\n", d1+d2);
}

int main(void){
    sum(2,4);
    return 0;
}

この中で、自分で定義した関数は"void sum(int d1, int d2)“です。関数を定義するときはこのようにします。関数を定義するときの注意点としては、プログラムは上から順にコンパイラに解析されていくので、実行するところよりも上に書いてないといけないことです。もし、実行するところよりもあとに書きたいときは関数原型宣言(関数プロトタイプ宣言)をしなければなりません。これについては後で説明いたします。

上記のプログラムでは"sum()“をvoid型で宣言しました。void型は返り値がない関数です。この関数ではint型のd1、d2を引数として受け取っています。引数とは、関数を利用する際に、実行する関数に与えることができる値です。引数は関数の中で利用することができます。この関数は"main()"の中で"sum(2,4)"と関数を呼び出し、関数に渡した二つの引数を足して表示しています。

簡単な関数をつくってみる(int型)

今度は、先程の関数をvoid型ではなく、int型の返り値を持つ関数で作ってみます。次のようにしてみました。

#include <stdio.h>

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

この関数"sum()“では"void"となっていたところが"int"となっています。これは返り値はint型ですよ、という意味です。"main()"を見てみると、"x = sum(2,4)"となっており、"sum()"が実行され、返ってくる値を"x"に代入しています。そして、得られたxを"printf()"で表示しています。

関数原型宣言(プロトタイプ宣言)をやってみる。

ここで、次のプログラムをコンパイルしてみます。

#include <stdio.h>

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

gccコンパイルしてみましたが、以下のような警告がでました。

test.c:5:9: warning: implicit declaration of function 'sum' is invalid in C99 [-Wimplicit-function-declaration]
    x = sum(2,4);
        ^
1 warning generated.

自分としては、コンパイルできないのかなと思っていましたが、コンパイルができ実行もできました。警告は"sumが宣言されてないけど、C99では無効だよ"って意味です。コンパイラによってはコンパイルできないみたいです。この警告を消すためにプログラムを次のようにしてみました。

#include <stdio.h>

int sum(int, int);

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

main()の前に"int sum(int d1, int d2);“の行が追加されています。これが関数原型宣言です。こういう型の関数を宣言するよ、というのを先にコンパイラに教えておきます。関数原型宣言ではカッコ内の引数の"d1"、"d2"などの変数名は必要なく、型だけでオッケーです。

再帰関数をつくってみる

次に、再帰関数というものを作ってみたいと思います。今まで、関数を"main()“の中から呼び出していました。宣言した関数の中で、さらにその関数自身を呼び出すとどうなるのでしょうか。そのように、関数の中で自分自身の関数を呼び出す関数を再帰関数と呼びます。

階上の再帰関数をつくってみる

はじめに単純な例である、階上の再帰関数をつくってみます。例えば4の階上は

4! = 4 × 3 × 2 × 1 = 24

となります。そこで次のようなプログラムを作ってみました。

#include <stdio.h>

int factorial(int n){
    if (n == 1){
        return n;
    } else {
        return n * factorial(n - 1);
    }
}

int main(void){
    int x;
    x = factorial(4);
    printf("%d\n",x);
    return 0;
}

このプログラムの中で"factorial()“という関数が再帰関数として書かれています。この関数の中で、"return n * factorail(n-1)"という行があります。この行で自分自身が呼び出されています。階上では数字を1づつ減らしながら1まで掛けていきます。なので、"n"がイチのとき、関数を呼び出さず値を返してあげ、それ以外は、"n-1"をもとの数と掛けていきます。理解しやすくするため、"factorial()"を次のようにしてみました。

int factorial(int n){
    int x;
    if (n == 1){
        x = n;
        printf("factorial: %d\n",x);
        return x;
    } else {
        x =  n * factorial(n - 1);
        printf("factorial: %d\n",x);
        return x;
    }
}

実行結果↓

factorial: 1
factorial: 2
factorial: 6
factorial: 24
answer: 24

はじめに表示されている値は"1"です。"main()“の中で、関数に渡した値は4なのにはじめに"1"が表示されます。これは"printf()"を通過する前に"factorial(n-1)"が呼び出されているので、値が表示される前に、さらに関数が呼び出されるためです。"n == 1"までいくと、値が返ってくるのでその下の"printf()"が実行されていきます。そして、はじめは1、その後1×2=2、2×3=6、6×4=24というのが表示されていきます。

等比数列の和の再帰関数をつくってみる

次に等比数列の和を再帰関数で求めてみたいと思います。

等比数列 - Wikipedia

別に再帰関数を書かなくても、公式を使えばすぐできますが、練習のため作ってみました。また、等比数列の和を求める中で、累乗を求める必要があります。C言語の数学的な計算をするための"math.h"のヘッダの中に、累乗を計算する"pow()“が定義されていますが、今回はこれも自分で作って見ました。"math.h"で定義されている"pow()"はdouble型の返り値を持ちますが、今回つくってみたのはint型ですのでご注意ください。

#include <stdio.h>

int pow(int a, int n) {
    int ans = 1;
    int i;
    for(i=0; i<n; i++){
        ans = ans*a;
    }
    return ans;
}

int geoprog(int a, int r, int n) {
    if (n == 1) {
        return a;
    } else {
        return a*pow(r,n-1) + geoprog(a, r, n-1);
    }
}

int main(void){
    int x;
    x = geoprog(1,2,5);
    printf("answer: %d\n",x);
    return 0;
}

等比数列の和を求める関数は"geoprog()“です。引数は"a"が初項、"r"が項比、"n"が項数です。"初項1,公比2,項数5"で実行すると"31"とでてきたので、おそらくあっていると思います。ちなみに、"pow()"は引数"a"が底で、"n"が指数です。ちなみに、"pow()"はint型で作っているので、"n"が負の数になるような場合はきちんと動きません。"n"を負の数にも対応させたいときはdouble型になるように作ってみてください。