Last active
June 27, 2022 23:59
-
-
Save quanon/935466e46f87a82e05f739b94bad93e7 to your computer and use it in GitHub Desktop.
Manage job states with DFA
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 決定性有限オートマトン (DFA) | |
class DFA | |
class InvalidEvent < StandardError; end | |
attr_reader :current_state | |
def initialize(current_state:, accept_states:, rules:) | |
@current_state = current_state | |
@accept_states = accept_states | |
@rules = rules | |
end | |
# 受理状態かどうか。 | |
def accepting? | |
@accept_states.include?(@current_state) | |
end | |
# イベントを発生させる。 | |
def fire(event) | |
next_state = @rules.get_next_state(state: @current_state, event: event) | |
raise(InvalidEvent) unless next_state | |
@current_state = next_state | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'delegate' | |
# 決定性有限オートマトン (DFA) のルール集 | |
class DFARules < DelegateClass(Array) | |
def initialize(rules) | |
super(rules) | |
end | |
# 特定の状態で特定のイベントが発生した後の状態を取得する。 | |
def get_next_state(state:, event:) | |
rule = find { _1.apply_to?(state: state, event: event) } | |
rule&.follow | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 有限オートマトン (FA) のルール | |
class FARule | |
def initialize(state:, event:, next_state:) | |
@state = state | |
@event = event | |
@next_state = next_state | |
end | |
# 特定の状態で特定のイベントが発生した際にこのルールを適用できるかどうか。 | |
def apply_to?(state:, event:) | |
@state == state && @event == event | |
end | |
# このルールを適用した後の状態。 | |
def follow | |
@next_state | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require_relative './fa_rule' | |
require_relative './dfa_rules' | |
require_relative './dfa' | |
class JobState | |
INITIAL_STATE = :working | |
EVENTS = %i(succeed fail retry cancel).freeze | |
STATES = %i(working succeeded failed canceled).freeze | |
RULES = [ | |
FARule.new(state: :working, event: :succeed, next_state: :succeeded), | |
FARule.new(state: :working, event: :fail, next_state: :failed), | |
FARule.new(state: :failed, event: :retry, next_state: :working), | |
FARule.new(state: :failed, event: :cancel, next_state: :canceled) | |
].freeze | |
def initialize(current_state: INITIAL_STATE) | |
@dfa = DFA.new( | |
current_state: current_state, | |
accept_states: %i(succeeded canceled), | |
rules: DFARules.new(RULES) | |
) | |
end | |
# ジョブの現在の状態。 | |
def current_state | |
@dfa.current_state | |
end | |
EVENTS.each do |event| | |
define_method(event) { @dfa.fire(event) } | |
end | |
STATES.each do |state| | |
define_method(:"#{state}?") { @dfa.current_state == state } | |
end | |
# ジョブが完了したかどうか (= DFA が受理状態か) 。 | |
def finished? | |
@dfa.accepting? | |
end | |
end | |
if __FILE__ == $PROGRAM_NAME | |
require 'minitest' | |
require 'minitest/autorun' | |
class JobStateTest < Minitest::Test | |
def test_dfa | |
job_state = JobState.new | |
assert_equal(true, job_state.working?) | |
assert_equal(false, job_state.finished?) | |
job_state.fail | |
assert_equal(false, job_state.working?) | |
assert_equal(true, job_state.failed?) | |
job_state.retry | |
assert_equal(true, job_state.working?) | |
job_state.succeed | |
assert_equal(true, job_state.succeeded?) | |
assert_equal(true, job_state.finished?) | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'aasm' | |
require_relative './fa_rule' | |
require_relative './dfa_rules' | |
require_relative './dfa' | |
class JobStateWithAasm | |
include AASM | |
aasm do | |
state :working, initial: true | |
state :succeeded, :failed, :canceled | |
event :succeed do | |
transitions from: :working, to: :succeeded | |
end | |
event :fail do | |
transitions from: :working, to: :failed | |
end | |
event :retry do | |
transitions from: :failed, to: :working | |
end | |
event :cancel do | |
transitions from: :failed, to: :canceled | |
end | |
end | |
def finished? | |
succeeded? | |
end | |
end | |
if __FILE__ == $PROGRAM_NAME | |
require 'minitest' | |
require 'minitest/autorun' | |
class JobStateWithAasmTest < Minitest::Test | |
def test_dfa | |
job_state = JobStateWithAasm.new | |
assert_equal(true, job_state.working?) | |
assert_equal(false, job_state.finished?) | |
job_state.fail | |
assert_equal(false, job_state.working?) | |
assert_equal(true, job_state.failed?) | |
job_state.retry | |
assert_equal(true, job_state.working?) | |
job_state.succeed | |
assert_equal(true, job_state.succeeded?) | |
assert_equal(true, job_state.finished?) | |
end | |
end | |
end |
require 'benchmark/ips'
require_relative './job_state'
require_relative './job_state_with_aasm'
Benchmark.ips do |x|
x.config(time: 5, warmup: 2)
x.report('JobState') do
job_state = JobState.new
job_state.working?
job_state.fail
job_state.failed?
job_state.retry
job_state.working?
job_state.succeed
job_state.succeeded?
end
x.report('JobStateWithAasm') do
job_state = JobStateWithAasm.new
job_state.working?
job_state.fail
job_state.failed?
job_state.retry
job_state.working?
job_state.succeed
job_state.succeeded?
end
x.compare!
end
Warming up --------------------------------------
JobState 32.137k i/100ms
JobStateWithAasm 569.000 i/100ms
Calculating -------------------------------------
JobState 320.831k (± 0.2%) i/s - 1.607M in 5.008428s
JobStateWithAasm 5.682k (± 0.8%) i/s - 28.450k in 5.007612s
Comparison:
JobState: 320830.8 i/s
JobStateWithAasm: 5681.7 i/s - 56.47x (± 0.00) slower
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
http://www.plantuml.com/plantuml/uml/SoWkIImgAStDuIh9BCb9LNZSjEDny_B7pTCUDwvxthNjMMltoyRjpvVlvehMYbNGrRLJACyloixCI-U2qc2nujBavDJKbDGK1IiO6qK-BJ4p1oG9Pd11U629vCIyv5I8L78ga8cGHDW4b2jABIcgv8AQ39K5keSBeXqXeC3ba9gN0lGC0000