読者です 読者をやめる 読者になる 読者になる

A社の佐伯さんがのらりくらりと

A社の佐伯さんがのらりくらりと。インターネットと少しだけ生活のこと。

うろ覚えだった知識をまとめてみたよ【ハードウェア編①】

学習エントリ。 全体的な知識の底上げをすべく、復習も兼ねてまとめてみる。

ハードウェアとは

ハードウェアとは、コンピュータを構成する要素の総称。処理・記憶・入力・出力それぞれ4種類の機能を持つ装置のこと。

CPUとは
  • コンピュータの頭脳みたいな
  • メモリから命令やデータを取り出して、それを実行し、またメモリに結果を格納する
CPUの動作
  1. 命令フェッチ:メモリから命令を取得
  2. デコード:取得した命令を解読。CPUのどの回路に動作させるか決める
  3. オペランドフェッチ :メモリから処理対象のデータを取得
  4. 実行
  5. 結果の書き込み:結果をメモリに書き込む

これらの流れを命令サイクルという。オペランドは処理の対象となるデータ。命令もデータもとりあえずはメモリに置いてある。

CPUの構成要素

中でも重要な3点 * レジスタ :メモリから取得した命令やデータ、計算結果を格納する変数みたいなもの。まずはこのレジスタに入れて、演算を行い、結果をレジスタに戻す。命令レジスタ、凡庸レジスタ、アキュムレータ、インデックスレジスタ、ベースレジスタなど * ALU:四則演算や論理演算を行う機構。 * デコーダ:命令レジスタが保持している命令を解読し、CPU内部のどの部分を動作させるか決める機能

クロック周波数

CPUが全体として正しく動作するためには、レジスタデコーダがタイミングをあわせて正しく動作する必要があり、そのタイミングを合わせるための信号がクロック。クロックを一秒間にどれくらい発生させるかをクロック周波数という(単位はHz)。一般的にクロック周波数が高いとCPUの動作は早くなる。3GHzのCPUなら、一秒間に約30億回のクロック。

CPUの構造
  • CISC:複合命令セットコンピュータ。高性能な命令を豊富に用意したCPU。 便利だけど、すべてをハードウェアでコントロールすることが出来ず、一部はソフトウェア(マイクロプログラム)で管理されている。そのため速度は若干遅い。

  • RISC:基本的な命令のみに絞ったCPU。CISCと違い、CPU内部の回路は単純なため、全てをハードウェアで管理(ワイヤードロジック制御)。動作は早い。

パイプライン制御とハザード

命令サイクルをプロセッサ内で複数のステージに細分化し、複数の命令を並列に実行することで命令を高速で処理できる様になった。ベルトコンベアのようなイメージ。これをパイプライン制御という。パイプライン制御を阻害する様々な要因がハザード。主に以下の2つ。 * 制御ハザード:条件分岐命令、ジャンプ命令の実行 * データハザード:直前の命令の実行結果を利用する

マルチコアプロセッサ

CPU本体の回路をコアという。ひとつのCPUに複数のコアがあるのでマルチコアプロセッサ。消費電力を抑えつつ、処理性能を高められるのがいいとこ。

機械言語とその命令の種類

機械語アセンブラ言語)はCPUが直接理解できる唯一の言語。 * 転送命令:メモリ〜レジスタ間のデータの転送 * 演算命令:算術、論理演算 * 比較演算命令:大小関係の比較 * シフト演算命令:レジスタに格納されている数値の桁を移動する * 分岐命令:プログラムの実行順序を変える

機械言語命令の構成

命令部 オペランド部:処理対象のデータを指定。データが何番地にあるのか?その指定の事をアドレッシングモードという。

アドレッシングモード
  • 直接アドレス指定:オペランド部に書いてある数値が格納場所の番地であるとする
  • 間接アドレス指定:オペランド部に書いてある数値が有効アドレスがある番地を指している(有効アドレス=データが格納させれている番地)。2回メモリにアクセスせにゃならん。
  • インデックスアドレス指定:インデックスレジスタオペランド部に書いてある数値を足した値が格納場所の番地であるとする。配列のアクセスなどに使う。
  • ベースアドレス指定:ベースレジスタオペランド部に書いてある数値を足した値が格納場所の番地であるとする。
割込み

割込みが発生するとCPUは処理を停止し、割込みの対応を行う。それが終わると停止したプログラムを再開する。 内部割り込み:プログラムを実行した結果として発生する割込み 外部割り込み:CPUに接続される周辺装置が状況により発生させる割込み

参考

www.amazon.co.jp

【アルゴリズムの勉強】Pythonでユークリッドの互除法を書いてみた

学習エントリ。

Pythonユークリッドの互除法を実装する。

ユークリッドの互除法ってなんぞ

ユークリッドの互除法ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである

ユークリッドの互除法 - Wikipedia

# coding: utf-8

x = 108
y = 648

def gcd(x,y): 
	while y != 0:
		x , y = y , x % y 
	return x

print(gcd(x,y)) ##108

【アルゴリズムの勉強】Pythonで二分探索を書いてみた

学習エントリ。

Pythonで二分探索を実装する。

二分探索ってなんぞ

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである(O記法)。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。

二分探索 - Wikipedia

# coding: utf-8
import math

example_list = [1,3,4,5,6,7,9,10,13,16,18,22,24,25,26] 
target = 22

def binary_search(list,taget): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)/2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return str(target) + "は見つかりませんでした"
	else:
		return "要素の値が" + str(target) + "のインデックス=>" + str(result)

    
print binary_search(example_list,target) #要素の値が22のインデックス=>11

メモ

・left,rightというリストの両端のインデックスを用意する
・targetの判定によって、centerを用いてどちらかを狭めていく
・targetを見つけたら処理をwhile文を抜ける
・最大まで狭めると処理を終了する
・結果を判定するための変数(result)は-1にしておく。result = 0だとtargetが1(indexが0)の場合に失敗になってしまう。


この前のマージソートのように再帰的に求められるかと思ったが、挫折した。こちらの書き方の方がシンプルで分かりやすい。

【アルゴリズムの勉強】Pythonで線形探索を書いてみた

学習エントリ。

Pythonで線形探索を実装する。

線形探索ってなんぞ

線形探索(せんけいたんさく、英: linear search, sequential search)は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
{\displaystyle n} n個のデータから {\displaystyle m} m個のデータを検索する場合、 時間計算量は {\displaystyle O(nm)} O(nm)、空間計算量は {\displaystyle O(1)} O(1)必要となる。

線型探索 - Wikipedia

# coding: utf-8

example_list = [5,2,10,1,18,3,7,4]
target = 18

def linear_search(list,taget): 
	result = 0
	index = 0
	for x in xrange(0,len(list)):
		if list[x] == target:
			result = 1
			index = x
			break
	if result == 1:
		return str(target) + "はリストの" + str(index) + "番目にあったよ"
	else:
		return str(target) + "はリストには無かったよ"
    
print(linear_search(example_list,target)) ##18はリストの4番目にあったよ

楽に書けた
targetが複数あった場合の処理は別途必要

【アルゴリズムの勉強】Pythonでマージソートを書いてみた

学習エントリ。

Pythonマージソートを実装する。

マージソートってなんぞ

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def mergeSort(list,order):   
    mid = len(list)
    if mid > 1:
        left = mergeSort(list[:(mid/2)],order)           
        right = mergeSort(list[(mid/2):],order)
        list = []
        while len(left) != 0 and len(right) != 0: 
            if order == ASC:
                if left[0] < right[0]:                
                    list.append(left.pop(0))
                else:                                  
                    list.append(right.pop(0))
            elif order == DESC:
                if left[0] > right[0]:                
                    list.append(left.pop(0))
                else:                                  
                    list.append(right.pop(0))
        if len(left) != 0:                        
            list.extend(left)                     
        elif len(right) != 0:                   
            list.extend(right)               
    return list         


        

print("ASC is...")
print(mergeSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(mergeSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]
ポイントっぽいところ

再帰的に最小までスライシングした配列を作る
・初期化したlistにleft[0],right[0]の小さい方を加えていく
・※その際popを使うことで元の要素を減らしていくどちらかの要素数が0になるまで行う
・どちらかの要素数が0になった場合、反対の要素数は1残ってしまうので、その配列を最後に足してあげる

【アルゴリズムの勉強】Pythonでクイックソートを書いてみた

学習エントリ。

Pythonクイックソートを実装する。


クイックソートってなんぞ

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO {\displaystyle (n\log n)} (n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO {\displaystyle (n^{2})} (n^{2})である。また数々の変種がある。 安定ソートではない。


クイックソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def quickSort(list,order):
    if len(list) <= 1:
        return list
    pivot = list[0]
    left = []
    right = []
    if order == ASC:
        for i in xrange(1,len(list)):
            if list[i] <= pivot:
                left.append(list[i])
            else:
                right.append(list[i])
        return(quickSort(left,ASC) + [pivot] + quickSort(right,ASC))
    else:
        for i in xrange(1,len(list)):
            if list[i] > pivot:
                left.append(list[i])
            else:
                right.append(list[i])
        return(quickSort(left,DESC) + [pivot] + quickSort(right,DESC))

    
        

print("ASC is...")
print(quickSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(quickSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]

ポイントっぽいところ

・リストの要素の一つをpivotとし、他のlistの要素を、それぞれpivotより大きいか小さいかを判定し、leftとrightに分ける
・left,rightをそれぞれ自身の関数に入れてソートし直す。要素数が1になるまで続ける。
・ソートし終えたleft + pivot + ソートし終えたrightを返す

【アルゴリズムの勉強】Pythonで選択ソートを書いてみた

学習エントリ。

Pythonで選択ソートを実装する。

選択ソートってなんぞ

選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

選択ソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def selectSort(list,order):
    for i in xrange(0,len(list)):
        if order == ASC:
            min = list[i]
            num = i
            for j in xrange(num + 1,len(list)):
                if min > list[j]:
                    min = list[j]
                    num = j
                if num == i:
                    continue
                list[i],list[num] = list[num],list[i]
        elif order == DESC:
            max = list[i]
            num = i
            for j in xrange(num + 1,len(list)):
                if max < list[j]:
                    max = list[j]
                    num = j
                if num == i:
                    continue
                list[i],list[num] = list[num],list[i]
    return list


print("ASC is...")
print(selectSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(selectSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]
ポイントっぽいところ

・1. 順番にlistを取り出し、最初の値を比較対象とする
・2. 最小値or最大値を仮に比較対象とする
・3. 比較対象とそれ以降の要素(list[j])を一つ一つ比べ、最小値or最大値を求める
・4. 求めた最大値or最小値と比較対象をスワップ