※この記事は、個人技術ブログ CodeArchPedia.com の技術メモ（要約）です。
データ分析で時系列データを扱っていると、「今の値より大きい直前の値のインデックス」を高速に知りたい場面に必ず遭遇します。特に株価やセンサーデータのトレンド特定では必須の操作です。しかし、Pandasで素直に書くと計算量が跳ね上がり、数百万行のデータでは処理が止まってしまいました。
何が起きたか（課題）
現在の要素よりも大きい直前の要素のインデックスを Pandas のループで探そうとすると、計算量が O(N²) になってしまうのが最大の問題でした。これはデータサイズが大きくなるほど、処理時間が爆発的に増大することを意味します。
- 数万件のデータで数時間かかるボトルネックが発生した。
- 素朴な
series[:i][series[:i] > series[i]]のようなスライス検索は直感的だが、大規模データには全く向かない。 - O(N²) の実装では、実運用で求められる応答速度を達成できない。
どう解決したか（概要）
この種の系列処理を高速化する定石として、「単調スタック（Monotonic Stack）」アルゴリズムを採用しました。この手法により、全ての要素を一度だけ処理すればよいため、計算量を線形時間 O(N) に劇的に改善できます。これが現場で求められるパフォーマンスを実現するベストプラクティスです。
単調スタックの動作原理
処理するインデックスをスタックに格納し、現在の値がスタックのトップよりも大きい、または等しい場合、スタックのトップを順次ポップしていきます。これにより、スタックのトップには常に「現在の要素より大きい直前のインデックス」が残る構造を作り出します。この処理を NumPy 配列に対して適用することで、Python のオーバーヘッドを減らし、最速の処理を実現しました。
下記は O(N) で単調スタック処理を実行し、結果を返す最適化された関数の概要です。
import numpy as np
def find_previous_larger_index_optimized(arr: np.ndarray):
# O(N)で単調スタック処理を実行し、結果を返す
...
モダンな Polars を使う場合でも、複雑な逐次ロジックが必要なため、一度 NumPy 配列に変換してこの最適化された O(N) 関数を UDF (User Defined Function) 経由で呼び出すのが最も高性能なアプローチでした。
効果（Before/After）
O(N²) の素朴な Pandas ループ処理と比較して、NumPy を利用した単調スタック O(N) 解法を導入した結果、処理速度は劇的に向上しました。
| 比較項目 | 計算量（オーダー） | 実測パフォーマンス |
|---|---|---|
| Pandas 素朴なループ | O(N²) | 非常に遅い（ボトルネックの原因） |
| NumPy + 単調スタック (推奨) | O(N) | 最速 |
データセットが大きくなるほど、O(N²) のコードは事実上使用不可能になりますが、O(N) 解法なら数百万件のデータでもストレスなく処理を完了できます。速度を最優先する現場でのデータ分析基盤を確立できました。
🚀 詳細な設定とコードはこちら
具体的な NumPy の実装コード全文や、Polars で O(N) 関数を呼び出すための UDF の詳細な定義、そして O(N²) の非推奨な実装コード全体については、元のブログで公開しています。