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

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

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

【アルゴリズムの勉強】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最小値と比較対象をスワップ

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

学習エントリ。

Pythonで挿入ソートを実装する。

挿入ソートってなんぞ

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート - Wikipedia

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

def insertSort(list,order):
    for i in xrange(1,len(list)):
        j = i
        if order == ASC:
            while j > 0 and list[j] < list[j - 1]:
                list[j], list[j - 1] = list[j - 1], list[j]
                j -= 1
        elif order == DESC:
            while j > 0 and list[j] > list[j - 1]:
                list[j], list[j - 1] = list[j - 1], list[j]
                j -= 1
    return list
        

print("ASC is...")
print(insertSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(insertSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]
ポイントっぽいところ
  • xrange(1,len(list)):1からスタートする
  • iを直接使わず、jという変数で管理する(用途が異なるため)
  • 最後にjを減らしていくことで、連続して判定
  • whileに条件を複数追加