zatsu na benkyou matome saito

勉強したことをまとめるだけのサイト、数学、プログラミング、機械学習とか

データ構造とアルゴリズム:gnome sort(ノームソート)

重要度:低い

Bubbleソートと類似のソート手法で、左から順にみていき入れ替えた時にBubbleソートはそのまま右にずれるが、ノームソートでは入れ替えた後は左にずれる。

順番が正しい場合はスキップ スクリーンショット 2020-11-26 22.26.58.png (140.0 kB)

順番が正しくない場合はスイッチする。この後バブルソートでは右側に移動するがノームソートではスイッチした後に左側にずれるように動く。 スクリーンショット 2020-11-26 22.27.32.png (139.6 kB)

そうすると2,1を比べた時に一番左側に2があるのでここもスイッチする。それ以上左にいけなくなったら再度右移動に戻って同じことを繰り返していく。 スクリーンショット 2020-11-26 22.29.50.png (133.4 kB) スクリーンショット 2020-11-26 22.30.14.png (132.4 kB)

右側に行って、7,8を比べた時に順番が逆なので、入れ替える。その後、一度左に行って、5,7を比べた時に順番が正しいので右に進む。左側に小さい数を貯めていく方式なので、一度左に行って正しければそれ以上左に戻る必要はない。 スクリーンショット 2020-11-26 22.31.09.png (132.9 kB)

右に大きい数字があったら正しい位置に配置されるまで左に向かい数値をスイッチしていき、右に一つもどって確認して一番右までスイッチがなく終了したらソートが完了する。 スクリーンショット 2020-11-26 22.32.42.png (136.4 kB) スクリーンショット 2020-11-26 22.32.54.png (128.6 kB)

from typing import List
import random

def gnome_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    index = 0
    while index < len_numbers:
        if index == 0:
            index += 1
        if numbers[index] >= numbers[index-1]:
            index += 1
        else:
            numbers[index], numbers[index-1] = numbers[index-1], numbers[index]
            index -= - 1
    return  numbers

numbers = [random.randint(0,1000) for i in range(10)]
print(gnome_sort(numbers))

[87, 537, 811, 379, 306, 230, 853, 263, 861, 923]

データ構造とアルゴリズム:selection(選択ソート)

重要度:高い

左から一つづつ、一時的にtmp変数に格納して左から順にそれぞれの配列要素と大きさを比べ、tmpに入っている数値より小さい数値があればその数と入れ替える。その作業を一番右端まで行い、一番小さい数値が入っているインデックス番号の要素を配列の一番左の要素と入れ替える。

その後、2番目の数値を同じようにtmp変数に格納して、左から一番小さい値を除いて右に順次確認していく。 比較して小さい数値があれば、その数値と入れ替え、最後まで行った後に一番小さい数値の入っている要素と左から2番目の要素を入れ替えどんどん小さい値を左側の要素と入れ替えて、左側から順に小さい要素を揃えていく。

スクリーンショット 2020-11-26 0.24.25.png (163.1 kB) スクリーンショット 2020-11-26 0.24.31.png (155.4 kB) スクリーンショット 2020-11-26 0.24.47.png (177.6 kB)

3と5を比較した時に3の方が小さいので5の要素と入れ替える。 スクリーンショット 2020-11-26 0.29.35.png (164.6 kB) スクリーンショット 2020-11-26 0.29.42.png (156.7 kB)

from typing import List

def selectioin_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        min_idx = i
        for j in range(i + 1, len_numbers):
            if numbers[min_idx] > numbers[j]:
                min_idx = j
        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]

    return numbers


nums = [random.randint(0, 1000) for i in range(10)]
print(selectioin_sort(nums))

[351, 532, 539, 550, 601, 686, 773, 871, 908, 995]

rubyで描くとこんな感じでできた

def selection_sort(numbers)
  len_numbers = numbers.length
  
  (0..len_numbers-1).each do |i|
    min_idx = i
    ((i+1)..len_numbers-1).each do |j|
      if numbers[min_idx] > numbers[j]
        min_idx = j
      end  
    end
    numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
  end
  numbers
end


numbers = Array.new(10){ rand 1000 }
print selection_sort(numbers)

[71, 91, 136, 271, 352, 371, 566, 720, 861, 870]

データ構造とアルゴリズム:comb(コムソート)

重要度低い

combというのはクシという意味なので、クシを溶かしていくように、くしの幅を小さくしていくようにソートを行う手法。 Gap 7/1.3 = 5というのは櫛の幅だと考え、1番目と5番目の数値を入れ替えて入れ替える必要がなければ戻し、Gapを狭くして同じ作業を行なっていく。Gapの7というのは配列の個数。 

スクリーンショット 2020-11-25 23.38.50.png (189.5 kB)

前回の幅である5を分子として使用して、次の櫛の幅で同じ入れ替え確認作業を行う。 スクリーンショット 2020-11-25 23.41.14.png (172.9 kB)

最終的に幅が1で入れ替え確認作業を行い、SwapフラグがFalseになったまま周回が終わるまで入れ替え作業を行なっていく。 スクリーンショット 2020-11-25 23.42.25.png (229.9 kB)

from typing import List
import random

def comb_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers
    swapped = True

    while gap != 1 or swapped:
        gap = int(gap / 1.3)
        if gap < 1:
            gap = 1

        swapped = False

        for i in range(0, len_numbers - gap):
            if numbers[i] > numbers[i + gap]:
                numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
                swapped = True

    return numbers

# nums = [2, 9, 1, 8, 7 ,3, 5]
nums = [random.randint(0, 1000) for i in range(10)]

print(comb_sort(nums))


[169, 197, 217, 245, 328, 383, 555, 692, 824, 983]

データ構造とアルゴリズム:cocktail(シェーカーソート)

cocktail(シェイクソート)

カクテルをシェークするような動きをするのでこのような名前がつけられている。bubbleソートの改良版でbubbleソートにかなり類似しておりbubbleソートを振る、ようなイメージ。

まず、左から右に配列を見ていって小さければ入れ替え、というのはbubbleソートの時と同様。 ただ、swap = Falseというフラグがあり、その周回の時に入れ替えが起きたらSwapをTrueに変更する。一番右のlimitまできたらswapをFalseに直して、今度は右から左に数字を見る。

この時に左の方が大きければ、右と入れ替える。という作業を行う。一番大きい数値は最初の段階で一番右にくるのでlimitを一つ下げる。 スクリーンショット 2020-11-25 0.54.25.png (223.0 kB)

スクリーンショット 2020-11-25 0.54.58.png (239.5 kB)

右から左に来るときは、一番左の数値が一番小さい数値になるので左側のlimitを一つ上げるようにする。

スクリーンショット 2020-11-25 0.57.47.png (244.1 kB)

一度もswapがTrueにならなかったらその時点でソートを完了して良い。そのため、swapが Trueにならない周回があったらその時点でソートが完了しているとみなしても良いため、全てのパターンを行う必要がなくBubbleソートよりも早く処理が完了する。 スクリーンショット 2020-11-25 0.58.54.png (309.7 kB)

  • まずswapの初期値がTrueなのでwhile swappedの箇所でwhilteのloopに入る。
  • 通常のbubbleソート同様に左の数値が大きければ右の数値と入れ替えるというのを1重のfor文で実現する
  • ①の最後でもしswappが起こればswappedフラグをTrueにする。
    • この時点で、swappedがFalseのままであれば、その時点でソート完了し、breakとなる
    • 初期でendを−1している理由は、最初のfor文で一番後ろに最大値が移動するので一番後ろまで処理する必要がないから
  • そのご②に入る
    • ②に入る前にend - 1をしてあげることで、limitを一つずらす
  • for i in range(end-1, start-1, -1):というfor文は配列を逆順に入れる作業をしている
    • この逆順にする作業で、for文を逆から読み込ませる作業を行なっている。実際に行っているのは通常のbubbleソートの逆順にしたバージョンである。
    • 最後にもしswapped = Trueになれば再度一番上に戻り①からやり直しswapped = Falseのまま続くまで行う。
from typing import List

def cocktail_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    swapped = True
    start = 0
    end = len_numbers - 1
    
    while swapped:
        swapped = False
        # 右方向に進むときの for loop
        # for①=============================start
        for i in range(start, end):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True
        # for①=============================end
        
        # swappが変更されなければfalseのままなのでここで処理が終了
        if not swapped:
            break

        swapped = False
        end = end - 1
        
        # for②=============================start
        for i in range(end-1, start-1, -1):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True
        # for②=============================end
        start = start + 1
    
    return numbers


import random
arry = [random.randint(0, 100) for i in range(10)]
print(cocktail_sort(arry))


[0, 5, 36, 44, 53, 55, 68, 83, 84, 96]

このサイトのgif?がすごくわかりやすいのだが、右に行くときは大きいものを一番右に押しやる作業、左に行くときは小さいものを一番左に押しやる作業を行なっているのがわかる。 眺めていられるシェーカーソートのシミュレーション|JavaScript

ダウンロード.png (32.9 kB)

データ構造とアルゴリズム:本編

アルゴリズムの重要性

GAFAシリコンバレーの企業面接には絶対にアルゴリズムのコーディング試験があり、1秒でも処理が早くなるのであればアルゴリズムを早い方に書き換えたほうが良い。車の自動運転など瞬間の判断に関わるものは特に反応速度が重要視されているので、アルゴリズムについて精通していたほうが良い。

データ構造

スクリーンショット 2020-11-24 21.23.29.png (260.3 kB)

データ構造とアルゴリズムとは?

  • データをどのように格納するのか
  • どのような格納順で実装すると処理が早くなるのかなどの構造のこと

Big O Notation (Big O 記法)

learn-programing.hatenablog.jp

安定ソート

スクリーンショット 2020-11-24 22.22.03.png (606.3 kB)

安定ソートとは

ソート判定において、同一であると判断された入力データの順序がソート後も変わらない スクリーンショット 2020-11-24 22.23.46.png (1.1 MB)

元の配列のソート順は変わらない

ex) (2, Bill) , (2, June) という要素はstable sortでは元の順番が変わっていないが、unstable sortではそれぞれの順番が変わっている。

ソート

bogoソート

重要度:低い learn-programing.hatenablog.jp

bubbleソート

重要度:高い learn-programing.hatenablog.jp

cocktail(シェーカーソート)

重要度:低い learn-programing.hatenablog.jp

comb(シェーカーソート)

重要度:低い learn-programing.hatenablog.jp

selection(選択ソート)

重要度:高い

learn-programing.hatenablog.jp

データ構造とアルゴリズム:Big O Notation (Big O 記法)

スクリーンショット 2020-11-24 21.24.17.png (253.0 kB)

アルゴリズムの処理速度を可視化したもの。

O(log(n))

# O(log(n))
def func2(n):
    if n <= 1:
        return
    else:
        print(n)
        func2(n/2)
func2(10)

10
5.0
2.5
1.25

O(n)

# O(n)

def func3(numbers):
    for num in numbers:
        print(num)
        
func3(range(1,10))

1
2
3
4
5
6
7
8
9

O(n * log(n))

# O(n * log(n))
def func4(n):
    for i in range(int(n)):
        print(i, end=' ')
    print()

    if n <= 1:
        return
    func4(n/2)

func4(10)

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 
0 1 
0 

O(n**2)

for文を2回回すと2乗になる

# O(n**2)
# for文を2回回すと2乗になる
def func5(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            print(numbers[i], numbers[j])
        print()

func5([1,2,3,4,5])

1 1
1 2
1 3
1 4
1 5

2 1
2 2
2 3
2 4
2 5

3 1
3 2
3 3
3 4
3 5

4 1
4 2
4 3
4 4
4 5

5 1
5 2
5 3
5 4
5 5

データ構造とアルゴリズム:Bogoソート

bogo(ボゴソート

ボゴソートはシャッフルに並び替えた後にそのソートが正しく並び替えられているかを確認するソート手法。 def in_orderでは、左側の数字が右側の数字(i+1番目)よりも大きければその時点で並び替えは失敗しているので、return Falseという

配列の1つ目から、forで回して、最後の1個以外を一つ後に来る配列の要素と大きさを比べている。 最後の要素までいったということが配列が正しく並び替えられている理由になるので、最後の一個は比較しない。

in_orderがTrueを返すまではランダムに並び替える作業を止めないので、while not文でTrueが返ってくるまでランダムシャッフルと並び替えの確認作業をし続ける。

import random
from typing import list

def in_order(numbers):
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i+1]:
            return False
    return True

def bogo_sort(numbers):
    while not in_order(numbers):
        random.shuffle(numbers)
    return numbers

if __name__ == '__main__':
    print(bogo_sort([1, 5, 3, 2, 6]))
    
[1, 2, 3, 5, 6]

in_orderの確認はリスト内包括を利用することで1文で書くことができる。

def in_order(numbers: List[int]) -> bool:
    return all(numbers[i] <= numbers[i + 1] for i in range(len(numbers) - 1))

def bogo_sort(numbers: list) -> list:
    while not in_order(numbers):
        random.shuffle(numbers)
    return numbers

if __name__ == '__main__':
    print(bogo_sort([1, 5, 3, 2, 6]))
def bogo_sort(numbers: List[int) -> List[int]:

と書くことで、引数にlist型を期待していて、返り値にinteger型のlistを返すということを明示できる。 listの代わりにboolなども使用可能。

詳しくはなんかぐぐる実践!!Python型入門(Type Hints)

ランダムな配列を適当に作るコード

0 ~ 100までのランダムな数字で10個の要素を持つ配列を作成する。

if __name__ == '__main__':
    nums = [random.randint(0, 100) for _ in range(10)]
    print(nums)

[21, 97, 13, 36, 89, 59, 30, 50, 14, 15]

このようにbogoソートはランダムで実行するので、基本的に処理時間は長い。運が良ければ処理時間が短くなるが可能性はひくい。下記、ボゴソートを行った時の処理時間を測定。 配列が100個あるときは終わらなかった。。。

# 配列が10この時
[17, 26, 31, 31, 49, 51, 64, 69, 76, 89]
4.3439563389993054

Pythonの if name == 'main': は何のためにあるものですか?

この構文がないと、単にimportされた時にも.pyファイルが実行されてしまうので、import時の実行を防ぐために記載される処理。