【アルゴリズムの勉強】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に条件を複数追加

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

学習エントリ。

Pythonでバブルソートを実装する。

バブルソートってなんぞ

ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia

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

def bubleSort(list,order):
    while True:
        continue_flg = 0
        if order == ASC:
            for i in xrange(len(list) - 1):
                if list[i] > list[i + 1]:
                    list[i], list[i + 1] = list[i + 1], list[i]
                    continue_flg = 1 
        elif order == DESC:
            for i in xrange(len(list) - 1):
                if list[i] < list[i + 1]:
                    list[i], list[i + 1] = list[i + 1], list[i]
                    continue_flg = 1 
        if continue_flg == 0:
            return list


#result
print("ASC is...")
print(bubleSort(example_list,ASC)) #[1, 2, 3, 4, 5, 18]
print("DESC is...")
print(bubleSort(example_list,DESC)) #[18, 5, 4, 3, 2, 1]

• スワップが容易だった
• while Trueで永続的にループ。flgの値で処理を抜けるか判定。
• for文内の条件式に入っていない→flgが更新されていない→必要な処理は終わったと判断し、抜ける。
• もっと効率的な方法を模索

実は痛くないインフルエンザ検査の方法がある

佐伯です。あけましておめでとうございます。

新年というのに、おみくじ大吉だったにも関わらず体調を崩している。

1/2の夜、急に具合が悪くなりガストで食べたチキン南蛮その他もろもろをすべて胃からトイレに流し込んだあと2日間ほど39.0~38.0度の熱を行ったり来たりしていた。こんなに急に熱上がることあるか？もしやインフルでは、と不安がよぎった。インフルだったら大変だ。もっと休めてしまう会社に迷惑がかかってしまうではないか。

（比較的）痛くないインフルエンザ検査の方法がある

若いからか、39度とは言えまだ動ける状態ではあるので一刻もはやく検査に行くべきなのだが、私にはどうしても躊躇する理由があった。

検査がめちゃくちゃ痛いのだ。

鼻腔拭い液と言って、鼻に綿棒を突っ込み、その粘液から症状を判断するというものだが、痛さが尋常でないのである。無理だ。何故現在の症状よりも辛い思いをして検査を受けなければならないんだ。よく考えればおかしな話である。10000円で100円玉を買うようなものじゃないか。多分違うけど。

初めての出社日、私は仕方なく有給を取った。何度も私は考えた。他の方法は無いかと。25歳にもなってGoogleに「インフルエンザ　検査　痛くない　方法」なんて検索するとは思わなかった。自分を恥じなかったかといえば嘘になる。だがしょうがない。怖いものは怖い。

Google先生は優秀だった。聞き方すら幼稚な私に適切な回答をくれた。インフルエンザの検査にはもうひとつ咽頭拭い液という方法があったのだ。

咽頭ぬぐい液（のどの奥に綿棒を挿入し、数回こするようにして粘膜表皮を採取します）

www.naika-shinjyuku-ekimae-clinic.info

精度は約60～80％前後と高いとは言えないが、インフルエンザの検査はこの２つが主流のようだ。ただ綿棒が喉のかなり奥まで行くので、不快な感じがして吐き気がするそうだ。天が恵みをくれたかのようだった。これぞまさに私の為の検査方法だ。鼻の痛みは計り知れないが、喉ならいける。喉に綿棒を突っ込まれる？余裕だ。なぜなら私は昨日ゲロ吐いているからね！

早速電話をかけた。住まいが新宿近郊なのですべての病院をリストアップした。

その数述べ13件、結果すべての病院が咽頭拭い液を取り扱っていなかった。いやいや、そんなはずはない。ここは東京だ。日本で一番お金が動く場所。あらゆる人間の欲望を満たしてきた場所じゃないか。時間はすでに調べ始めて3時間を経過していた。さすがに東京すべての病院に電話することは出来なかったが、咽頭拭い液を東京で取り扱っている病院は見つからなかった。

夢持たせやがって。僕は東京に失望した。そして私のような絶望から一度希望を与えられ、最後に叩き落される経験を一人でも多くの方にしていただきたいという一心でこのエントリを書くに至った。

結論

インフルエンザの検査は痛いやつしかない

なぜ病院は咽頭拭い液を取り扱っていないのか

これはあくまで私の推測だが

1.確率の低いものを使う意味がない

2.病院の専門外

3.あったとしても受付の方に共有されていない

このあたりが原因だろう。しかし、「こういった治療方法があります」とHP教えてくれた病院が取り扱っていなかったのはとても悲しかった。

そして絞首台に上がる死刑囚はこんな感じかな、と思いながら近くの病院へ行き、陰性の紙切れをもらいましたとさ。おしまい。

今年を振り返って、来年は転職しようと思った

私だ。これは釣りタイトルだ。別に転職する気はない。しかしそれくらいの心持ちだ。今年を振り返りつつ、考えをまとめてみた。

会社にわがままを言って一年が過ぎた

もう今年も終わりそうだ。

今年は弊社サービスのディレクター的立ち位置から、プログラマーに転向した一年だった。もともとプログラマーとして入社したのだが、改善点を指摘しているうちに「じゃあお前やってみろよ」ということになり、前職と同じようにディレクターとしてサービスに働きかけるようになった。しかしやはりプログラマーになりたいという思いは捨てきれず、切りがよいところで転向の意思表示をした。それが2016年1月のことだ。

そこからはPHPのフレームワークを使ったサーバーサイドの実装を担当した。わからないイライラをメンターにぶつけながらも、自分で作った機能をいくつも世に出すことが出来た。あの喜びは他には変えられないし、自分のわがままに対応してくれた会社、そして、物分かりが悪い僕を見捨てないでいてくれたメンターには感謝してもしきれない。そしていま、僕は組織の転換期もあってか、サーバーサイドを離れ、SwiftとObjective-Cを使ったiOSを担当している。クライアントサイドは僕含めて2人しかチームが居ないため、わりと自由に、時にわからない部分にひりひりしながら開発している。一年でサーバーサイド、クライアントサイドの両方を任せてもらえたのは貴重だったな、と今になって思う。

そして来年、2017年が終わる頃、僕はどうなっていたいのか。端的に言うと

プログラマとして転職または独立できるレベルになっていたい。

別に今の会社に不満が有るわけではないので、転職したい、というわけではないが。やはり根本にあるのが、もっと成長したい、そんでもってお金ほしい、だ。

プログラマが転職を考えるとき、それはもう技術的にこの会社で得られるものが無くなったときらしい。それはすなわち与えられた環境で最大限に成長したということだ。どうせまた一年同じ仕事をするなら、そこを目指したい。

目標を細分化してみる

僕にとってプログラマとして転職または独立できるレベルとは次の2点を指す。

１. 担当するチケットをどういったものでも最速で実装できるレベル（Dev面）

２. 組織のボトルネックがどこかを考えて、働きかけることが出来るレベル（Biz面）

である。

１．担当するチケットをどういったものでも最速で実装できるレベル

メモ

何故速さを重要視するかというと、いままでのインプットが中心で、全体を理解してから取り組もうという姿勢ではいい結果が残せなかったからだ。それもまあ良い勉強方法であるが、一年を通した結果、実装できた機能は個人的には少なかったと感じている。自分で実装した部分は文字通り自分の血肉となる。今年は目の前のタスクをいち早く完了にすることを念頭に置く。もちろんバグを出さずにだ。目の前の事をどんどんこなしていけば、いずれインフラやDB、負荷分散の部分にも手をいれるときが来るだろう。そうすれば自ずとサービスを形作る一連の知識がつくはずだ。未知のものに対して、既存の知識をかけ合わせながら解決まで持っていくスピードが早ければ、どの言語でも対応可能だと思う。

手段

それぞれのチケットを見積もりの半分の期間で完了にできるよう工夫する

２．組織のボトルネックがどこかを考えて、働きかけることが出来るレベル

メモ

去年の悔やむべき部分は、自分の思考の浅さと表現の乏しさだ。組織のボトルネックがどこか考え、働きかける。一見当たり前のように感じるし、自分もその姿勢こそあれど、この一年、自分のボトルネックと捉える部分の曖昧さ、働きかけの弱さを痛感させられた。原因は思考の浅さだと思う。伝えたい事が明確であれば、もっと他者に働きかけることができるからだ。最近はゼロ秒思考という本の、メモ書きを実践している。以前よりも頭が整理されたことを実感しているので、引き続き継続したい。

手段

メモ書きを継続することでまずは頭を整理する。

それ以外にも

・ブログの更新は怠らない。

・LTを一回やってみたい

・自動売買のシステムを日常的にまわしたい

・去年よりもっと本読みたい

などあるが、一年もある。全部できるはずだ。ここは絶対にやる、と言い切ることにする。まあ、気負いすぎずのんびりやっていこうと思う。来年も楽しみだ。来年の今頃、恥ずかしくてこの記事を消すことがないようにしたい。