皆様、こんばんは
私の記事も total 400 view と言うことで
嬉しい限りです、有難うございます m(_ _)m
分かりにくかったらコメント OK です(oﾟｪﾟo)ﾉYO--
私の夏休みを使ったチャレンジも意味があったと、
しみじみしています。今日で夏休みは終わりで
来週から仕事です。明日、明後日は育児、家事というなの修行です(笑)
出来れば時間を見つけて
この活動は続けたいので是非、応援宜しくお願い致します。
さて、O(1)!? ってことで、
そこから説明するのは私が分かっていないことを
バレてしまいますので省きます(笑)
有識者の方の記事を拝見すると、要は for 単品 or for のネスト or while + if を
やめれば O(1) になりそうな気がしました(勝手に URL 貼って良いのかな。まぁ、いっか)。
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0
先日、以下の考え方でスタックを作りましたが、
https://qiita.com/AKpirion/items/f3d5b51ab2ee9080e9c6
取りあえず、記述としては push/pop は O(1) の理解で問題なさそうです。
さて、min の実装ですが、min 関数を走らした時点で、スタックしたデータから最小値を探し出すには for 文の使用は必須です。
なので、O(1) を満たす為には、Push の度に、最小値を格納する箱を更新できれば良いと思いました。
よって、初期値に str_min を追加しました。
class top:
def __init__(self, capacity: int = 5):
self.str = [None] * capacity
self.capa = capacity
self.ptr = 0
self.str_min = float("inf") #最小値を格納する箱
※@shiracamus さん、autopep8 やりました(笑)。初耳の方はググってみましょう
self.str_min を float("inf")、つまり無限大に設定しているのは、
最初に push した値を必ず str_min に格納できるからです。
def min_str(self, value):
#self.str_min = min(self.str_min,value)
if self.str_min > value: #入力値 value が str_min より小さければstr_min を更新
self.str_min = value #self.str_min < value であれば何もしないで return
return self.str_min
個人的には上図の def .. のすぐ下にあるコメントにあるように min() でやっても良いと思うんですけど、
本当に O(1)!? って言われると自信がないので、if 文で逃げました。
なんか確認方法あるんですか、これ!?
取りあえず時間がないので Push に行きます。
def push(self, value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value #str にデータを Push!
top.min_str(self, value) #Push したデータと str_min と比較し、最小値を更新
self.ptr += 1
Push の記述は基本今まで通りなのですが、
top.min_str(self,value) を突っ込む事で Push する度に最小値を更新できるようにしました。
よかった、探す手間が簡略化できそうです( *´艸｀)
あとは最後に min を呼び出すときに
少し工夫が必要でした。
取りあえず、以下のコードを眺めてみてください。
while True:
num = int(input("select 1.push , 2.pop : , 3.min "))
if num == 1:
s = int(input("enter data: "))
try:
test.push(s)
except test.full:
print("full!")
elif num == 2:
try:
x = test.pop()
print(x)
except test.empty:
print("empty!")
elif num == 3:
print(test.min_str(float("inf"))) #無限大と最小値を比較
else:
break
最初に 3 を入力すると min を呼び出せるのですが、
def min_str(self,value) っとなっているので、
何かを value の個所にぶち込まないとエラーになります。
なので、私は無限大を突っ込んで、必ず最小値が必ず出せるようにしました。
今回は絵がイメージの絵が皆無でした、すいません。
あとは、こんな記事も書いてますので宜しければどうぞ
1つの配列に 2 つのスタックを Python で実装してみる
https://qiita.com/AKpirion/items/2e74eecd30063a01d2fc
それでは良い週末を・ω・´)尸
ところが、、2020/9/29 @neboccoさんのご指摘により、
前述の記述で不足分を指摘いただきました。
以下、コメントの抜粋です。
stackでは、pushは末尾に追加、popは末尾を削除、という操作になります。
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF
よって先程示したような操作をすると、topに保持されたデータは以下のようになると思います。
push(3)
=> str = [3], str_min = 3
push(1)
=> str = [3, 1], str_min = 1
pop()
=> str = [3], str_min = 1
（strの中身がNoneになっている部分は描画を省いています。）
これだと1は既にpopされてstackには残っていないのに最小値には1が残ってしまう（正しい最小値は3）のではないでしょうか？
pop の際に最小値が抜けてしまったら、
min も更新しないとダメではないか!?
全くもって、死角でした、気付けなくて恥ずかしいです。
でも、教えてくれて有難うございます(´；ω；`)ｳｩｩ
では対策行ってみましょう。
例えば、
push(1)
push(2)
push(0)
push(2)
push(5)
push(2)
っと順に push したとします。
すると str 本体の中身は以下のようになります。
これとは別に最小値を管理する str_min を用意します。
ここに格納するのは、push の度に求めた最小値です。
下図をご覧ください、イメージを図にしました。
このようにしてあげれば、pop と同じように、str_min の上から順に値を拾えば、
どのタイミングで pop されたとしても簡単に最小値を拾える算段です。
ではでは、修正していきましょう。
class top:
def __init__(self, capacity: int = 5):
self.str = [None] * capacity
self.capa = capacity
self.ptr = 0
self.min = float("inf") #Pushデータが最小か否かを判断する基準
self.str_min = [None]*self.capa #最小値を管理するスタック
self.str_min と self.min の追加をしました。
self.min 用途については、以下の記述を見てもらったほうが早いかもしれません。
class top:
def push(self, value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value
top.min_str(self, value)
self.ptr += 1
def min_str(self, value):
#基準値 min と push value を比較
#min の初期値は inf
if self.min > value:
#pushしたvalueの方が小さければstr_min格納
self.str_min[self.ptr] = value
#基準値 min も最小値の value へ更新し、次の比較に使用する
self.min = value
else:
#基準値 min が最小値を維持しているのであれば min を str_min に push
self.str_min[self.ptr] = self.min
return self.str_min[self.ptr-1]
最後の return self.str_min[self.ptr-1] のですが、
pop と同じ要領です。
このような勉強の機会をくださった @nebocco さんに感謝です。
本当に有難うございましたm(_ _)m
っというわけでコード全貌です。
class top:
class full(Exception):
pass
class empty(Exception):
pass
def __init__(self, capacity: int = 5):
self.str = [None] * capacity
self.capa = capacity
self.ptr = 0
self.min = float("inf")
self.str_min = [None]*self.capa
def push(self, value):
if self.ptr >= self.capa:
raise top.full
self.str[self.ptr] = value
top.min_str(self, value)
self.ptr += 1
def min_str(self, value):
if self.min > value:
self.str_min[self.ptr] = value
self.min = value
else:
self.str_min[self.ptr] = self.min
return self.str_min[self.ptr-1]
def pop(self):
if self.ptr <= 0:
raise top.empty
self.ptr -= 1
return self.str[self.ptr]
test = top()
while True:
num = int(input("select 1.push , 2.pop : , 3.min "))
if num == 1:
s = int(input("enter data: "))
try:
test.push(s)
except test.full:
print("full!")
elif num == 2:
try:
x = test.pop()
print(x)
except test.empty:
print("empty!")
elif num == 3:
print(test.min_str(float("inf")))
else:
break