10/10 何を食べようかということしか頭にないのちょっと悲しい
きょうはPythonと,Pythonを使ったダイクストラ法をすこし.
オブジェクトの中にデータやメソッドなどいろいろな機能があり,それを組み合わせて使うことでさまざまな処理ができるという仕組み.
どうやって使えばいいのかというと,
クラス(オブジェクトのひな型)設計
##クラス(オブジェクトのひな型)設計
class Human:
'''人間クラス'''
def search(self, place):
print(place + "をきょろきょろ.")
'''ある場所を見渡してみる(だから何ということはない)'''
def take(self, food):
self.food = food
print(self.food + "を手に取りました.")
'''食べ物を手に取る(手に取ることによって,持っている食べ物を代入)'''
def open_mouth(self):
print("口を開けました")
'''口を開ける(だから何ということはない)'''
def eat(self):
print(self.food + "を食べました.")
def noaction(self):
pass
これで定義できる(設計書が書けた状態).必ずselfという第一引数が必要で,それぞれがメソッドになる.
次に,これをもとにオブジェクトを生成する.
オブジェクト生成
##オブジェクト生成
#オブジェクト名 = クラス名
hito = Human()
hito.noaction()
hito.search("研究室")
hito.take("おせんべい")
hito.eat()
↓
C:\Users\bin\Anaconda3\python.exe C:/Users/bin/PycharmProjects/practice/practice4.py
研究室をきょろきょろ.
おせんべいを手に取りました.
おせんべいを食べました.
Process finished with exit code 0
オブジェクトを生成すると,メソッドが呼び出せるようになる.引数selfは与えなくてよく,与えた引数は二番目以降の引数に割り当てられる.
クラスを基にして生成したオブジェクト(ここではhito)を,インスタンスという.
※引数selfってなに?
###機材の管理プログラム
class equipmentmanagement:
'''使用bike'''
def setbike(self, bike):
'''使用bikeのメーカーを設定するメソッド'''
self.bike = bike
def getbike(self):
'''使用bikeが何か取得するメソッド'''
return self.bike
taro = equipmentmanagement()
taro.setbike("anchor")
print(taro.getbike())
print(taro.bike)
↓
C:\Users\bin\Anaconda3\python.exe C:/Users/bin/PycharmProjects/practice/practice5.py
anchor
anchor
Process finished with exit code 0
self(ここでいうtaro)はオブジェクトのインスタンス,つまり「クラスという設計書から生成されたオブジェクト」を指している.
インスタンスの初期化メソッド・コンストラクタ
クラスの定義のとき,__init__()メソッドを定義しておくと,インスタンスを生成した時にこのメソッドが自動的に実行されるので,初期化できる.
※クラス変数とインスタンス変数
クラス関数(個別のメソッドの定義の外に書く)はすべてのインスタンスで共通して使える変数,インスタンス変数はインスタンス事に異なる値を設定できる変数.
クラス定義の外側でも変更できる.クラス名.変数名ならクラス変数の変更,インスタンス名.変数名ならインスタンス変数の変更になる.同じ名前でも(クラス変数ではなく)新しいインスタンス変数が作られたことになるので注意.
継承とスーパー(基底)クラス,サブ(派生)クラス
継承:既に定義してあるクラス(基底クラス)を基にして新たな要素を加えたクラス(派生クラス)を定義すること.
class 派生クラス名(基底クラス名):
派生クラスの定義
このとき,派生クラスでは基底クラスの機能はすべて使える.
class Car:
def __init__(self, owner):
self.handle = 0
self.car_type = "normal"
self.owner = owner
…
が定義されているとき,派生クラスの定義のところで,
class Van(Car):
def __init__(self, owner)
super().__init__(owner)
self.car_type = "van"
…
のようにsuper().メソッド名を書けば,基底クラスのメソッドを呼び出せる(二行目にselfが入っていないのは引数のselfは省略していいから.まず基底クラスのメソッド,ここでは初期値を全部読みだしたあとで,self.car_typeだけを初期値として入れ替えているということ).
要するに,大きなクラスを定義したあと,個別的なことを定義したいときに使う機能.
註:派生クラスのメソッドで基底クラスのメソッドにオーバーライドして,「でも基底クラスのメソッドが呼び出したいんだ!」というときは,super().メソッド名でOK.
多重継承といって複数のクラスを基底クラスとして持つこともできる.
class 派生クラス名(基底クラス名):
派生クラスの定義
の基底クラス名のところに複数のクラス名を, で区切って入れればいいだけ.内容がかぶっているときは,左から順番に優先される.
なお,派生クラスの方が基底クラスよりも優先される.
クラスの特殊メソッド
たとえば,ふつうこれだけだとエラーになって,単純に座標だけ足し算してもらうというわけにはいかないけれど,
p1 = Pos(3, 50)
p2 = Pos(10, 50)
p3 = p1 + p2
↓
C:\Users\bin\Anaconda3\python.exe C:/Users/bin/PycharmProjects/practice/practice7.py
Traceback (most recent call last):
File "C:/Users/bin/PycharmProjects/practice/practice7.py", line 1, in <module>
p1 = Pos(3, 50)
NameError: name 'Pos' is not defined
Process finished with exit code 1
クラスを定義しておけば計算できてしまうみたいなこと.
class Pos:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
'''+という演算子に,selfとotherの要素を足すというふるまいをオーバーロード'''
x2 = self.x + other.x
y2 = self.y + other.y
return Pos(x2, y2)
def __str__(self):
'''self.x, self.yを( , )という形に直して返すという定義.
つまり,文字列を読み込んだときのふるまいの定義'''
return "({0}, {1})".format(self.x, self.y)
p1 = Pos(3, 50)
p2 = Pos(10, 50)
p3 = p1 + p2
print(p3)
↓
C:\Users\bin\Anaconda3\python.exe C:/Users/bin/PycharmProjects/practice/practice7.py
(13, 100)
Process finished with exit code 0
メソッド__add__(self, other)は演算子+を使ったときの挙動をオーバーロードするときに.
を参考にさせていただいて勉強中.以下はほぼ同様の内容に,初学者的なコメントを足したもの.
ダイクストラ法とは
ノードと重み(非負)づけがしてあるリンクからなるグラフを考え,同じ始点から始まったときの,最短の経路選択を行うというアルゴリズム.
簡単な例で言うと,地点と通れる道が複数あって,道の長さによって重みづけがされている,みたいな状況.
理論に忠実にやったときのオーダーはO(|V|^2)だが,優先度付きキューという概念を導入することでO(|E|log|V|)にできる.
優先度付きキューを使うと以下のことができる.
・キューに対し,要素を優先度付きで追加
・最も高い優先度の要素をキューから除いて返す
・(最も高い優先度の要素を除くことなく参照)
・(指定要素を除くことなく優先度を変更)
で,これをPythonに実装するためには,ヒープキューアルゴリズム(heapqというモジュール)というのがいいらしい(さっきから「らしい」とつけたいのをずっとがまんしていた).
ヒープというのはたぶん二分ヒープのことをさしていて,親ノードの値≤子ノードの値となる二分木.子ノードどうしの大小には特に制約はない.最大値・最小値を求めるのに便利.ここで使う
.heappush(heap, item)
は,itemをヒープに入れて,かつヒープの不変性は保たれるというもの(
8.4. heapq — ヒープキューアルゴリズム — Python 2.7.13 ドキュメントを見ると
ヒープ不変式と訳されているけど,たぶんヒープの(優先度の)関係が変わらないってことだと思う).
import heapq
q = [] # プライオリティキュー https://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC
# 1をpush
heapq.heappush(q, 1)
print(q)
# 2をpush 1より2のほうが優先度が低いので,先頭以外にくっつく
heapq.heappush(q, 2)
print(q)
# 0をpush 0が一番優先度が高いので,先頭にくっつく
heapq.heappush(q, 0)
print(q)
↓
C:\Users\bin\Anaconda3\python.exe C:/Users/bin/PycharmProjects/practice/practice4.py
[1]
[1, 2]
[0, 2, 1]
Process finished with exit code 0
注意するのは,優先度が一番高い(つまり値が一番小さい)ものが最初にくるが,ほかの順序は適当ということ.
※タプルの比較
==、!=:すべての要素が同じかどうか比較する
<=、<、>、>=:すべての要素の大小を比較する
is:オブジェクトが同じかどうか比較する
pythoncode.blog.fc2.comより.プライオリティキューの優先度の計算では,Pythonの「タプル比較では,最初の要素から順番に比較して大小を判定」という仕組みを使っているらしい.