0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Python で作ったスタックに最小値(min) を返す機能を追加するが push/pop/min は基本 O(1) !!

Last updated at Posted at 2020-09-25

皆様、こんばんは
私の記事も 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 を追加しました。

stack_min.py
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 に格納できるからです。

stack_min.py
    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 に行きます。

stack_min.py
    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 を呼び出すときに
少し工夫が必要でした。
取りあえず、以下のコードを眺めてみてください。

stack_min.py
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 本体の中身は以下のようになります。
図1.PNG
これとは別に最小値を管理する str_min を用意します。
ここに格納するのは、push の度に求めた最小値です。
下図をご覧ください、イメージを図にしました。

図2.PNG
このようにしてあげれば、pop と同じように、str_min の上から順に値を拾えば、
どのタイミングで pop されたとしても簡単に最小値を拾える算段です。
ではでは、修正していきましょう。

stack_min_r2.py
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 用途については、以下の記述を見てもらったほうが早いかもしれません。

stack_min_r2.py
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

っというわけでコード全貌です。

stack_min_r2.py
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
0
1
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?