perf: optimize nested foldl in Glushkov/Matcher.lean step/initialStep (O(n²) → O(n log n))
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 35/100
- issue の種類
- リファクタリング
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 領域
- compilers, performance
調査の方向性
Lck/Regex/Glushkov/Matcher.lean から始め、引用された行の step と initialStep に注目し、それらにネストされた foldl 操作を追跡してください。状態集合の候補データ構造を現在の動作と比較します。マッチング結果を維持したまま、ステップごとの計算量を O(n²) から O(n log n) に近づけて削減できれば完了です。
索引モデルが issue の本文から書いたものです。
説明
Problem
The step and initialStep functions in Lck/Regex/Glushkov/Matcher.lean (lines 45-55, 65-75) use nested foldl operations that produce O(n²) complexity for large NFAs.
Impact
For a pattern with n positions, each step scans all active states and for each computes a set union — resulting in O(n²) per character of input.
Suggested Fix
Consider using a more efficient data structure (e.g., a bitset or sorted set with efficient union) to bring the per-step cost to O(n log n).
References
Raised in AI code review.
- 主要言語
- Lean
- スター
- 2
- フォーク
- 1
- PR マージ指標
- 30日以内にマージされた PR はありません
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
lambdaclass/lambda_compiler_kit のほかの issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 72/100
-
難易度 1/5 1時間未満 初心者へのやさしさ 68/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
-
enhancement
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 50/100
lambdaclass/lambda_compiler_kit の issue をすべて見る
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
-
internal.h中，漏掉了1个定义。 オープン
難易度 1/5 1時間未満 初心者へのやさしさ 95/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
oxc-project/oxc#26944 ·