【アルゴリズムの勉強】Pythonで線形探索を書いてみた
学習エントリ。
Pythonで線形探索を実装する。
線形探索ってなんぞ
線形探索(せんけいたんさく、英: linear search, sequential search)は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
{\displaystyle n} n個のデータから {\displaystyle m} m個のデータを検索する場合、 時間計算量は {\displaystyle O(nm)} O(nm)、空間計算量は {\displaystyle O(1)} O(1)必要となる。
# 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でマージソートを書いてみた
学習エントリ。
マージソートってなんぞ
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。
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]
【アルゴリズムの勉強】Pythonでクイックソートを書いてみた
学習エントリ。
クイックソートってなんぞ
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO {\displaystyle (n\log n)} (n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO {\displaystyle (n^{2})} (n^{2})である。また数々の変種がある。 安定ソートではない。
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)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。
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アルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
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でバブルソートを書いてみた
学習エントリ。
バブルソートってなんぞ
ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。(単に交換法と言う場合もある)
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先生は優秀だった。聞き方すら幼稚な私に適切な回答をくれた。インフルエンザの検査にはもうひとつ咽頭拭い液という方法があったのだ。
咽頭ぬぐい液(のどの奥に綿棒を挿入し、数回こするようにして粘膜表皮を採取します)
精度は約60~80%前後と高いとは言えないが、インフルエンザの検査はこの2つが主流のようだ。ただ綿棒が喉のかなり奥まで行くので、不快な感じがして吐き気がするそうだ。天が恵みをくれたかのようだった。これぞまさに私の為の検査方法だ。鼻の痛みは計り知れないが、喉ならいける。喉に綿棒を突っ込まれる?余裕だ。なぜなら私は昨日ゲロ吐いているからね!
早速電話をかけた。住まいが新宿近郊なのですべての病院をリストアップした。
その数述べ13件、結果すべての病院が咽頭拭い液を取り扱っていなかった。いやいや、そんなはずはない。ここは東京だ。日本で一番お金が動く場所。あらゆる人間の欲望を満たしてきた場所じゃないか。時間はすでに調べ始めて3時間を経過していた。さすがに東京すべての病院に電話することは出来なかったが、咽頭拭い液を東京で取り扱っている病院は見つからなかった。
夢持たせやがって。僕は東京に失望した。そして私のような絶望から一度希望を与えられ、最後に叩き落される経験を一人でも多くの方にしていただきたいという一心でこのエントリを書くに至った。
結論
インフルエンザの検査は痛いやつしかない
なぜ病院は咽頭拭い液を取り扱っていないのか
これはあくまで私の推測だが
1.確率の低いものを使う意味がない
2.病院の専門外
3.あったとしても受付の方に共有されていない
このあたりが原因だろう。しかし、「こういった治療方法があります」とHP教えてくれた病院が取り扱っていなかったのはとても悲しかった。
そして絞首台に上がる死刑囚はこんな感じかな、と思いながら近くの病院へ行き、陰性の紙切れをもらいましたとさ。おしまい。