RSSフィードを購読
Python Coding Challenge - How will you achieve the minimum implementation of a stack using a list?
(Python コーディングチャレンジ [主要操作の実行計算時間が全て O(1) のスタックを list を利用して実装しよう！] 編)
(Python コーディングチャレンジ [主要操作の実行計算時間が全て O(1) のスタックを list を利用して実装しよう！] 編)
Python で提供されている list では、既にスタック機能 (push / pop) を実現するための関数群が提供されており、これらの関数の実行計算時間 (time complexity) は要素数に関係ありませんから O(1) です。
今回はこれらの提供されている関数操作に加えて、スタック中の最小要素を返す get_min() を追加したスタック機能を実現します。この get_min() 機能を O(1) の実行計算時間で実現することができますか？
問題：
Python の list を利用してスタック機能を実現するプログラムを記述してください。実装するスタック (stack) では以下の４つの機能を 全て constant time (要素数に左右されずに常に一定時間) で処理する必要があります:
push(x): x を新規要素としてスタックに積みます。
pop(): スタックから最上位要素を削除し、その要素を返します。
top(): スタックの最上位要素を返します。削除は行いません。
get_min(): スタックに積まれている要素の中で最小のものを返します。削除は行いません。
クラス定義は以下のような形です (同じである必要はありません):
from typing import Any
class MinStack:
def __init__(self):
...
def push(self, x: Any):
...
def pop(self) -> Any:
...
def top(self) -> Any:
...
def get_min(self) -> Any:
...
class MinStack:
def __init__(self):
...
def push(self, x: Any):
...
def pop(self) -> Any:
...
def top(self) -> Any:
...
def get_min(self) -> Any:
...
作成したプログラムは以下のテストをパスする必要があります:
import unittest
class TestMinStack(unittest.TestCase):
def setUp(self):
self.stack = MinStack()
def test_1(self):
self.assertIsNone(self.stack.pop())
def test_2(self):
self.stack.push(5)
self.assertEqual(self.stack.get_min(), 5)
self.assertEqual(self.stack.pop(), 5)
def test_3(self):
self.stack.push(5)
self.stack.push(3)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 3)
self.assertEqual(self.stack.get_min(), 5)
def test_4(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
self.assertEqual(self.stack.get_min(), 3)
def test_5(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.stack.push(1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
def test_6(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.stack.push(1)
self.stack.push(1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
class TestMinStack(unittest.TestCase):
def setUp(self):
self.stack = MinStack()
def test_1(self):
self.assertIsNone(self.stack.pop())
def test_2(self):
self.stack.push(5)
self.assertEqual(self.stack.get_min(), 5)
self.assertEqual(self.stack.pop(), 5)
def test_3(self):
self.stack.push(5)
self.stack.push(3)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 3)
self.assertEqual(self.stack.get_min(), 5)
def test_4(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
self.assertEqual(self.stack.get_min(), 3)
def test_5(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.stack.push(1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
def test_6(self):
self.stack.push(5)
self.stack.push(3)
self.stack.push(6)
self.stack.push(1)
self.stack.push(1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 1)
self.assertEqual(self.stack.pop(), 1)
self.assertEqual(self.stack.get_min(), 3)
self.assertEqual(self.stack.pop(), 6)
考え方:
get_min() の実装を除けば他の３つの機能 (push, pop, top) を実行計算時間 O(1) で実装することは問題ないでしょう。
そこで get_min() の実装について考えます。シンプルな方法は、list を最初から最後まで走査して最小の要素を見つける、といったものですね。しかしこの場合はスタックの要素数 n に左右されますから実行計算時間は O(n) となってしまい、O(1) でなければならない、という問題の要求を満たすことができません (しかし要素数に伴う必要メモリ量の変化はありませんから、 実行メモリ要求量 [space complexity] は O(1) です)。
では get_min() を実行計算時間 O(1) で処理するためにはどのような実装をする必要があるでしょうか？ここではこれを実現するために実行メモリ要求量 (space complexity) と実行計算時間 (time complexity) をトレードオフしたいと思います。つまり time complexity; O(1) を実現するために space complexity が O(n) となります。
具体的な話に入りましょう。まず最小値を保存しておくためのインスタンス変数 min_val を定義し「無限大」に初期化しておきます。push() が呼び出され新しい要素をスタックに積む際には、渡された値と min_val を比較し、渡された値の方が小さければその値で min_val を更新します。そうしておけば get_min() が呼び出されたときには min_val の値を返すだけで OK、ということになります。
しかし問題は pop() が呼び出されたときです。pop() が呼び出されたときにスタックから取り出し、削除し、返す値が min_val だったら...。この時我々の手元には「次に小さい値」の情報は一切ありません。この問題を解決するために、「最小値」と同時に「最小値の次に小さな値」の情報も同じスタックに積むようにします。そして、push() と pop() をこの操作に対応するように実装します。
push() の動作は次のようになります。渡された新しくスタックに積む値が min_val 以下であれば:
まず最初に「現在」の min_val をスタックに積みます
min_val を渡された値で更新します
渡された値をスタックに積みます
つまりスタックの最上段には 渡された本来スタックに積むべき「新たな最小値」、そのすぐ下には 「直前の min_val 値 == 次に小さな値」 という「セット」が積まれることになります。
逆に pop() の動作は次のようになります。もし取り出したスタック最上段の値が min_val であれば:
スタックからもう１つ値を pop() します
1 で取り出した価を min_val にセットします
最初に取り出した値 (最小値) を返します
ですから、push() 操作で最小値が渡されてきたら今までの最小値とともに「セット」としてスタックに積み、pop() 操作で最小値を取り出したらその次の最小値も「セット」として取り出す、という処理を行なうことで、１つだけのスタックで「最小値とその次に小さな値」のセットを扱うことが可能となるわけです。
主要操作の実行計算時間が全て O(1) のスタックを list を利用して実装するプログラム実装例：
from typing import Any
class MinStack:
def __init__(self):
self.stack: list[Any] = []
self.min_val = float('inf')
def push(self, x: Any):
if x <= self.min_val:
self.stack.append(self.min_val)
self.min_val = x
self.stack.append(x)
def pop(self) -> Any:
if self.stack:
val = self.stack.pop()
if val == self.min_val:
self.min_val = self.stack.pop()
return val
return None
def top(self) -> Any:
return self.stack[-1]
def get_min(self) -> Any:
return self.min_val
class MinStack:
def __init__(self):
self.stack: list[Any] = []
self.min_val = float('inf')
def push(self, x: Any):
if x <= self.min_val:
self.stack.append(self.min_val)
self.min_val = x
self.stack.append(x)
def pop(self) -> Any:
if self.stack:
val = self.stack.pop()
if val == self.min_val:
self.min_val = self.stack.pop()
return val
return None
def top(self) -> Any:
return self.stack[-1]
def get_min(self) -> Any:
return self.min_val
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
この実装では push(), pop(), top(), get_min() 全てのメソッドの実行計算時間は O(1) になります。ただし、単純に append したり pop する以外の操作を行なっていますので実質的な処理時間は多少長くなりますが、要素数 n に関わりなく常に constant time で実行されます。
Space complexity (実行メモリ要求量):
リスト内の全ての要素をループして最小値を探す方法であれば、要素数 n が増加したところでそれに応じて必要とするメモリ量が増加することはありませんから O(1) ですが、この方法では min_val を保存しておくための最悪 n 分の余分なメモリ量が必要となります。よって space complexity は O(n) になります。