【アルゴリズムの勉強】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教えてくれた病院が取り扱っていなかったのはとても悲しかった。
そして絞首台に上がる死刑囚はこんな感じかな、と思いながら近くの病院へ行き、陰性の紙切れをもらいましたとさ。おしまい。
今年を振り返って、来年は転職しようと思った
私だ。これは釣りタイトルだ。別に転職する気はない。しかしそれくらいの心持ちだ。今年を振り返りつつ、考えをまとめてみた。
会社にわがままを言って一年が過ぎた
もう今年も終わりそうだ。
今年は弊社サービスのディレクター的立ち位置から、プログラマーに転向した一年だった。もともとプログラマーとして入社したのだが、改善点を指摘しているうちに「じゃあお前やってみろよ」ということになり、前職と同じようにディレクターとしてサービスに働きかけるようになった。しかしやはりプログラマーになりたいという思いは捨てきれず、切りがよいところで転向の意思表示をした。それが2016年1月のことだ。
そこからはPHPのフレームワークを使ったサーバーサイドの実装を担当した。わからないイライラをメンターにぶつけながらも、自分で作った機能をいくつも世に出すことが出来た。あの喜びは他には変えられないし、自分のわがままに対応してくれた会社、そして、物分かりが悪い僕を見捨てないでいてくれたメンターには感謝してもしきれない。そしていま、僕は組織の転換期もあってか、サーバーサイドを離れ、SwiftとObjective-Cを使ったiOSを担当している。クライアントサイドは僕含めて2人しかチームが居ないため、わりと自由に、時にわからない部分にひりひりしながら開発している。一年でサーバーサイド、クライアントサイドの両方を任せてもらえたのは貴重だったな、と今になって思う。
そして来年、2017年が終わる頃、僕はどうなっていたいのか。端的に言うと
プログラマとして転職または独立できるレベルになっていたい。
別に今の会社に不満が有るわけではないので、転職したい、というわけではないが。やはり根本にあるのが、もっと成長したい、そんでもってお金ほしい、だ。
プログラマが転職を考えるとき、それはもう技術的にこの会社で得られるものが無くなったときらしい。それはすなわち与えられた環境で最大限に成長したということだ。どうせまた一年同じ仕事をするなら、そこを目指したい。
目標を細分化してみる
僕にとってプログラマとして転職または独立できるレベルとは次の2点を指す。
1. 担当するチケットをどういったものでも最速で実装できるレベル(Dev面)
2. 組織のボトルネックがどこかを考えて、働きかけることが出来るレベル(Biz面)
である。
1.担当するチケットをどういったものでも最速で実装できるレベル
メモ
何故速さを重要視するかというと、いままでのインプットが中心で、全体を理解してから取り組もうという姿勢ではいい結果が残せなかったからだ。それもまあ良い勉強方法であるが、一年を通した結果、実装できた機能は個人的には少なかったと感じている。自分で実装した部分は文字通り自分の血肉となる。今年は目の前のタスクをいち早く完了にすることを念頭に置く。もちろんバグを出さずにだ。目の前の事をどんどんこなしていけば、いずれインフラやDB、負荷分散の部分にも手をいれるときが来るだろう。そうすれば自ずとサービスを形作る一連の知識がつくはずだ。未知のものに対して、既存の知識をかけ合わせながら解決まで持っていくスピードが早ければ、どの言語でも対応可能だと思う。
手段
それぞれのチケットを見積もりの半分の期間で完了にできるよう工夫する
2.組織のボトルネックがどこかを考えて、働きかけることが出来るレベル
メモ
去年の悔やむべき部分は、自分の思考の浅さと表現の乏しさだ。組織のボトルネックがどこか考え、働きかける。一見当たり前のように感じるし、自分もその姿勢こそあれど、この一年、自分のボトルネックと捉える部分の曖昧さ、働きかけの弱さを痛感させられた。原因は思考の浅さだと思う。伝えたい事が明確であれば、もっと他者に働きかけることができるからだ。最近はゼロ秒思考という本の、メモ書きを実践している。以前よりも頭が整理されたことを実感しているので、引き続き継続したい。
手段
メモ書きを継続することでまずは頭を整理する。
それ以外にも
・ブログの更新は怠らない。
・LTを一回やってみたい
・自動売買のシステムを日常的にまわしたい
・去年よりもっと本読みたい
などあるが、一年もある。全部できるはずだ。ここは絶対にやる、と言い切ることにする。まあ、気負いすぎずのんびりやっていこうと思う。来年も楽しみだ。来年の今頃、恥ずかしくてこの記事を消すことがないようにしたい。
上司からの指示が気持ちよかった
今日上司からある指示を受けたのだが、それがとても気持ちよかった。決してそういう趣味が有るわけではない。しかし気持ちよかったのだ。何が気持ちよかったか、上司からの要求が整理されているからだ。
大体こんな順序だった(内容は結構変えている)。なんかこう、最小限の要素で物事を伝えている様に、美しさすら覚えた。
「機能の洗い出しをして欲しい。いまiOSにあってPCにない機能が多くなっていて、一度統制する必要がある。その洗い出したものをもとに機能の取捨選択を行う。ログイン前とログイン後、というカテゴリで洗い出してくれれば、それ以外のフォーマットは問わない。メンバーは〇〇とあなたで1/12までに行って欲しい。何か質問有りますか?」
それぞれが曖昧で無く、意味を持っている。私はこういう話し方がしたい。ダラダラ長い話をする人は苦手だ。自分もそうだから、会話や要求は疲れる。省エネがしたい。
それぞれがどういう意味を持っているのか?
先ほどの指示を要素ごとに書き出してみた。なんだかストーカーみたいな作業だが、決してそんな趣味はない。
・機能の洗い出しをして欲しい(要件)
して欲しい指示の要約
・いまiOSにあってPCにない機能が多くなっていて、一度統制する必要がある(理由/背景/目的)
問題になっていること、それをどうすれば解決されるか。
・その洗い出したものをもとに機能の取捨選択を行う(用途)
自分の成果物が、目的達成の為にどういう用途で使われるか
・ログイン前とログイン後、というカテゴリで洗い出してくれれば、それ以外のフォーマットは問わない(ポイント)
その作業をする上で絶対に外してはいけないポイント。ルール。
・メンバーは〇〇とあなたで1/12までに行って欲しい(メンバー・納期)
補足情報
・何か質問有りますか?(質問)
最後にお互いの認識の摺り合わせをする
それぞれがないとどうなるのか?
ある意味を考えたが、今度は無かったらどうなるか考えてみた。
要件がないとどうなる?
・そもそも何をすればいいかわからない。
・相手の解釈にブレが生じる
理由や背景・用途がないとどうなる?
・背景を共有されないため、全体を理解できない。
・原因がわからないと、その方法が適切かどうかという議論ができない
・そもそもやらされている感がでて、やる気がでない
ポイントがないとどうなる?
・各自がそれぞれの認識で仕事を行ってしまい、良い成果とならない
・そもそも正確な評価基準がない。
メンバーがないとどうなる?
・誰に相談すべきかわからない
納期がないとどうなる?
・問題の重要度が共有されていないため、後になって揉める
・スケジュールが立てにくい
質問がないとどうなる?
・意識の摺り合わせができない
・言われなかったから、そういう話が出なかったから、という感じで後になっても揉める
書き出して思ったが、当たり前だけど、いろんな角度から共有することが大事なんだなと思った。その大まかな要素が、要件、理由、用途、ポイント、メンバー、納期、質問みたい。もっと他にあるかもしれないけど、今日思ったのはそんなところ。
誠実な人って常に「自分は誠実じゃない」って思っている人だと思う
タイトルの通り。
よく「事故を起こさない人は、いつか自分は必ず事故を起こす、と常に自分を疑っている」と言われるがその原理と一緒だ。
本当に誠実なひとなんて存在しないんじゃないか
誠実とは
( 名 ・形動 ) [文] ナリ
偽りがなく、まじめなこと。真心が感じられるさま。 ↔ 不誠実 「 -な人柄」 「 -な対応」[派生] -さ ( 名 )
・偽りがない
・真面目
・真心が感じられる
これらほとんどが相手からの視点だ。自分でコントロールできるとすれば、偽りがない位だが、偽りが無くとも相手が真心を感じなければ、それは誠実とは言えない。相手に依存するものである以上100%誠実でいることなど不可能だ。「僕は誠実だ」と抜かす人間はそいつを誠実だと思った数%以外の大多数の人間を認識すら出来ていない。今日誠実だった奴が明日誠実とは限らない。アイツに誠実だった奴がコイツに誠実とは限らない。
でも誠実な人間に近づけることは出来る
僕が思う誠実な人間は
・今の自分が出来ることを
・無理がない状態で
・100%他者に行える
人間だと思う。
そのためにいつも自分を疑っていないと、今本当に相手に出来ることなどみつからないと思う。無理がない状態で、と入れた理由は、自分が無理をする状況は誠実とは言えないような気がするからだ。度が過ぎるとそれは押し付けになってしまう。結局は物事はバランスなので一言では語れないのが常だ。しかし大事なのは「今の自分は本当に誠実か?」と疑うことだ。そうすることで誠実な人にはなれずとも、それに近づくことが出来ると思う。
ドキュメンタルという番組で松本人志が「世界一おもしろい人って面白くないんですよね」と言っていた。なんとなくそれに近くて、「他者の解釈に依存するものは自分でコントロールすることは不可能なのですが、それに近づけて行くことで自然とそうなっていくんじゃないですかね」ということでした。
まあ、一番言いたいのはドキュメンタルはとても面白いということです。
どうすれば深い議論ができるか考えた
仕事で何かを議論しているとき、どうも深い議論にならないことがよくある。「こういうお問合わせが来ているんだけど、なんで起きたんですかね?」などという話から、深まりがなく、沈黙が起きてしまうことが少なくなかった。
最初はそれに対する前提の知識が薄いからだと思っていた。確かにそれはあるかもしれないが、時間が経つに連れて、一番の原因は、問題をシンプルに纏める作業をしていなからだと思うようになった。
問題をシンプルにまとめるってなんだ
考えた。
問題がシンプルになっている状態とは?
・その問題の原因が分かる状態
・その解決策が明確になっている状態
・問題の概要を短く要約出来る状態
いろいろあるだろうが、悶々考えた結果
評価軸が明確である状態 = シンプルな状態
だと思う。何をもってそれが良い、悪いとなるのか。それがどうなるかによって、結果がガラリと変わるもの。原因や解決策はその後の手段であり、概要は評価軸を決める為に必要なものだ。それを会話の中で行うことによって議論が深まるように感じる。
例えば、あるウェブサービスを運営していて、利用ユーザーからお問い合わせが来たとする
A「〜というお問合わせが来ていたようです」
B「原因は〜じゃないですかね?」
A「調べてみましょうか」
B「そうですね。もしそうだったら再発しないように〜しましょう」
これが普通の流れだと思う。しかし、この会話からは深みがないように感じる。それは原因を中心に話しているからだ。もちろん何か問題が起きていたら原因を調査し、解決しなくてはならないが、これではマイナスを0にしているだけで、将来的なプラスはない。
そこで評価軸を中心に話してみる
A「〜というお問合わせが来ていたようです」
B「原因は〜じゃないですかね?けどこれは修正するのに時間がかかりそうだ(人的コスト)」
A「けどこのお問合わせって〜の人にも迷惑がかかっていそうですね(ユーザーの満足度)」
B「それだと売上にも影響がありそうですね(直接的な売上)」
こんな感じで〜という評価軸だったらどうか、を挙げていく作業を行う。選択肢を洗い出していくイメージだ。ただそれだけだと逆に問題が複雑になるだけだ。
その中でじゃあ一番大事な評価軸ってなに?という話に移る。それはチームによりけりではあるが、これを(自分だけでも)意識して行うだけで、一つのお問合わせを修正しただけで、サービスのの理解が一層深まる議論が出来るはずだ。もちろん評価軸はどんどん変わってかまわないと思う。話せば話すほどブラッシュアップされるからだ。
上記の会話は例に過ぎないが(実際この3つに優先順位を付けるのは大変だ)実際に自分が考えたことであるので、ちゃんと自分で試していきたいと思う。
まずは声を大きくするところから始めよう。。。