id:morchi氏からの指摘 > sort()って確かクイックソートが実装されてるんじゃなかったっけかな。 「Pythonクックブック 第２版」によれば、Python 2.3で「最適、自然、安定」マージソート(通称timsort)が実装されたらしいです。 2.5ならソースコードのObject…

そう言えば昨日の実験では、Pythonの組み込み関数sort()を使ってなかったなぁ なのでやってみた。 # Compare some ways of Search import time import random def Search(target, numList): for x in numList: if x == target: return True return False def…

クイックソート。 アルゴリズム自体は簡単だけど、実装は微妙にめんどくさい。inspire先↓ クイックソート : アルゴリズム書いたコードはほぼリンク先と同じだけど、中身で何をしているかさっぱり つまり、再帰が全く身についていないことが分かった。 これは…

続き。 線形探索とバブルソート＋二分探索で勝負してみた。要素の数をを100, 1000, 10000の時、そして、探索場所をリストの前・真ん中・後ろの３箇所で調べてみた。 # Compare two ways of Search import time import random def Search(target, numList): f…

昨日二分探索はソートが完了していることが前提条件と言っていたので、今日はソートかな。 バブルソート。 泡がボコボコッと水面に上昇していくように、大きな数字がどんどん後ろにずれてゆく。 すんごい単純なアルゴリズム。 Pythonだとsort()という関数が…

昨日の続きで二分探索。 こいつも相当簡単な探索。 探索対象(リスト)のある位置x(大概は真ん中)を見て、探したいものがxより大きければその後ろを、小さければその前を、といった具合に探索範囲を狭めながら探索をおこなっていく。 ただし、前提条件としてソ…

下のエントリは線形リストではなく、「線形探索」ですな。 「線形リスト」= 「線形探索」と読み替えてください。 すんまそ。 んでもって、関数Positionを関数Searchとくっつければ、下でほざいている問題も関係ないっすね。 Search作ってから、継ぎ足しでPos…

ちょっと本気でプログラミングを学びたい欲求に駆られている今日この頃。 授業ではまったく興味なく、でも単位だけとってしまった「データ構造とアルゴリズム」 今となって重要性を感じるので独学で勉強する。 まず手始めに線形リスト。 def Search(n, List)…

先ほど書いたコードは時間がなくてかなり適当だったのでもう一度。 リスト内包記法の練習もかねて。 リストと探索したい数を与えるとその数の個数と場所を探索する。 def LinearSearch(target, datas): # targetに一致する要素が見つかったらその場所を保存 …

ご飯食べたし、続きのお勉強 恥ずかしながらこれまでオブジェクト指向は知識はありつつちんぷんかんぷんだった。 使わないし〜 関係ないし〜 とスルーしていた。 でも、久しぶりに「みんなのPython」のオブジェクト指向の項を読んでいて、「何か分かるかも」…

今日は引越し作業やら何やらで結局研究室にいけなかった… で、何か無性にプログラミングの勉強をしたくなったので。 Pythonをチョイス。 実験データの整形など、ファイルをいじるのに多少使っているくらいで、便利やなぁ〜と思いつつ深くは関わっていない。 …