Return to Video

03xpsps-01 Fsm Optimization Solution

  • 0:00 - 0:06
    この問題は少し難しいので
    2つ星レベルに分類します
  • 0:06 - 0:10
    ここでは有限状態機械を最適化していきます
  • 0:10 - 0:15
    図のような有限状態機械があったとします
  • 0:15 - 0:21
    ステート1には受理状態が1つあり
    他にもいくつかステートがあります
  • 0:21 - 0:23
    図をよく見て考えてください
  • 0:23 - 0:28
    bの道を通ってステート2に進めば
    受理状態には行けません
  • 0:28 - 0:32
    ステート2、ステート3またはステート4から
    ステート1に行く道はなく
  • 0:32 - 0:36
    この道を行く文字列はどれも失敗に終わります
  • 0:36 - 0:40
    この状態機械はステート1以外を
    含まないのと同じです
  • 0:40 - 0:42
    ならばもっとシンプルにしましょう
  • 0:42 - 0:44
    でも何のためにですか?
  • 0:44 - 0:49
    Webブラウザを作るために
    多くの正規表現を使ってきました
  • 0:49 - 0:55
    正規表現は有限状態機械として表され
    そして処理されます
  • 0:55 - 1:01
    つまりブラウザの高速化に
    有限状態機械の小型化は必須なのです
  • 1:01 - 1:03
    ではコードを書いていきます
  • 1:03 - 1:07
    この有限状態機械の定義を基に考えましょう
  • 1:07 - 1:11
    まず実行に関係しないステートを識別し
  • 1:11 - 1:15
    それらを死状態として定義から取り除きます
  • 1:15 - 1:19
    ただし最適化前に使われていた言語をそのまま保ち
  • 1:19 - 1:25
    まったく同じ文字列と一致するようにしたまま
    取り除く必要があります
  • 1:25 - 1:28
    どのように進めるか計画を立てましょう
  • 1:28 - 1:31
    これが計画です
  • 1:31 - 1:37
    ステップ1では生状態と死状態を探します
  • 1:37 - 1:41
    生状態を探しそれ以外は死んでいると推測します
  • 1:41 - 1:43
    具体的な方法はこうです
  • 1:43 - 1:48
    まずは辞書を反復しすべてのステートを探します
  • 1:48 - 1:53
    そしてそれぞれのステートに
    nfsmacceptsを実行します
  • 1:53 - 1:56
    これはレッスン1の宿題に出てきました
  • 1:56 - 1:59
    有限状態機械の定義として
  • 1:59 - 2:06
    開始ステートと受理状態
    そして遷移の辞書を受け取り
  • 2:06 - 2:11
    あるステートから受理状態に
    たどりつけるかどうかを見るプロシージャでした
  • 2:11 - 2:15
    nfsmacceptsに図の定義とステート3を与えると
  • 2:15 - 2:20
    ステート1には行けず
    つまりどの受理状態にも行けません
  • 2:20 - 2:22
    ステート1を与えると成功します
  • 2:22 - 2:25
    これを生と死の定義として
  • 2:25 - 2:30
    生状態と死状態を見分けていきます 楽しいですね
  • 2:30 - 2:37
    ステップ2では死状態を持たない
    新しい有限状態機械を作ります
  • 2:37 - 2:43
    賢くきれいな定義を作るために
    注意すべきことがあります
  • 2:43 - 2:46
    死状態につながる遷移は含めません
  • 2:46 - 2:49
    すべての死状態を取り除き
  • 2:49 - 2:55
    生状態へとつながらないステートも
    取り除いていきます
  • 2:55 - 2:57
    詳細を確認しましょう
  • 2:57 - 3:01
    各エッジのステートと辞書のエントリを見ます
  • 3:01 - 3:06
    今のステートが死状態なら
    新しい有限状態機械にコピーしません
  • 3:06 - 3:11
    そうでなければ元の有限状態機械にあった
    すべての行き先を見て
  • 3:11 - 3:15
    生状態のものをすべてコピーする準備をします
  • 3:15 - 3:20
    生状態がない場合は
    そのエッジを取り除きコピーはしません
  • 3:20 - 3:25
    図にあるすべてのステートで
    そのプロセスを繰り返したら
  • 3:25 - 3:29
    それに基づき受理状態のリストを更新します
  • 3:29 - 3:33
    死んでいる受理状態は必要ありません
  • 3:33 - 3:35
    解答を見てみましょう
  • 3:35 - 3:40
    まずレッスン1の宿題からnfsmacceptsのコードを
  • 3:40 - 3:45
    そっくりそのままコピーしました
    何も変えていません
  • 3:45 - 3:49
    次は有限状態機械のトリミングです
  • 3:49 - 3:52
    先ほど説明したようにすべてのステートを探します
  • 3:52 - 3:55
    コピーが存在することもあります
  • 3:55 - 3:59
    少しトリミングに時間がかかるかもしれませんが
  • 3:59 - 4:04
    実行にかかる時間が節約できれば問題ありません
  • 4:04 - 4:11
    各ステートが生きているかどうかは
    nfsmacceptsを実行すれば分かります
  • 4:11 - 4:14
    もし生きていたら生状態のリストに加えます
  • 4:14 - 4:18
    では新しいエッジの辞書を作成しましょう
  • 4:18 - 4:24
    もし古い辞書のエッジの遷移元に生状態があれば
  • 4:24 - 4:27
    それを基に更新していきます
  • 4:27 - 4:34
    新しい行き先を計算し
    死んでいる行き先を取り除くわけです
  • 4:34 - 4:38
    古いエッジの行き先が生きていたら
    リストに追加します
  • 4:38 - 4:44
    しかし新しい有限状態機械に
    新しいエッジを設定するのは
  • 4:44 - 4:48
    行き先が空でない場合のみです
  • 4:48 - 4:52
    どこにも行き着かず失敗するエッジはいりません
  • 4:52 - 4:56
    エッジが存在しない場合は失敗すると推測します
  • 4:56 - 5:02
    最後に受理状態を生きているものだけとする
    更新を加えてください
  • 5:02 - 5:08
    そして新しいエッジと新しい受理状態の
    タプルを返します
  • 5:08 - 5:11
    これで完了です
  • 5:11 - 5:15
    見てください Trueと出ています
  • 5:15 - 5:17
    Trueは真です
  • 5:18 - 5:23
    いいですね すばらしいです
Title:
03xpsps-01 Fsm Optimization Solution
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
05:24

Japanese subtitles

Revisions