Some ways to come up with less performant algorithms

[DoubleX]

Example 10

Spoiler

Suppose I've to let users use actor, class, weapon, armor, enemy, state notetags(each of such data can have more than 1 such effective notetags) that returns results by evaluating the RGSS3 codes they stored as notetag values, and the combined notetag results(the RGSS3 codes of all effective notetags will be evaluated) can be used per battler per frame. The final atb rate can only be changed due to change of any part of the base atb rate, some effective notetag becoming ineffective(or vice versa), or the same effective notetag being possible to return different results, and the first 2 reasons are unlikely to change frequently in most cases(DoubleX RMVXA Enhanced YSA Battle System: Classical AT:

# 7. <ecatb rate: RX> |# Sets the atb fill rate of the battler as RX, which can be set in Rate |# Notetag Values |

    #--------------------------------------------------------------------------|    #  Rate Notetag Values                                                     |    #  - Setups RX used by <ecatb rate: RX> notetags                           |    #--------------------------------------------------------------------------|    # RX are used at:    # 1. Game_BattlerBase    #    - base[:val] = note[self, base] in set_ecatb_gain_rate    # The base atb rate can be referenced by val[:val]    # The number of battlers counted for method sums can be referenced by    # val[:size]    # The method sum of all battlers counted can be referneced by    # val[:sum][method_name]    # method_name must be included in :ecatb_battlers_def_sum    # RX are strings of RGSS3 codes    # RX must return a real number and should return a floating-point number    # The naming of RX can only use alphanumeric characters    # The below RX are examples to help you set your RX    # You can freely use, rewrite and/or delete these examples    # Mutliplies the atb fill rate by the battler's agi / all battlers'    # average agi    # all battlers is the value of :def_sum_battlers    R1 = %Q(val[:val] * agi * val[:size] / val[:sum][:agi])    # Sets the atb fill rate as x% per frame    R2 = %Q(x)    # Sets the atb fill rate as the value of variable with id x * 100% per frame    R3 = %Q($game_variables[x])    # Adds new RX here

      # Sets the priority of the ecatb rate notetags to be used      # Its corresponding method's created under Game_Actor and Game_Enemy      # It must return an array with elements being either :states, :enemies,      # :armors, :weapons, :classes or :actors      # Example: To set actors to have a higher priority than that of states,      #          set this as %Q([:actors, :states])      :ecatb_rate_ord => %Q([:actors, :classes, :weapons, :armors, :enemies,                              :states]),

I also have to always ensure 100% correctness, even if some RGSS3 codes will consistently return random values(like constantly calling rand) per evaluation.

1st algorithm - I always reevaluate all RGSS3 codes of all effective notetags whenever the results need to be used, as I've absolutely no control of when the same RGSS3 codes written by those users will return different results even when nothing else the script knows changes(Modified from DoubleX RMVXA Enhanced YSA Battle System: Classical AT:

Spoiler

  #----------------------------------------------------------------------------|  #  Caches the base atb rate and notetag lambdas and always evaluates them all|  #----------------------------------------------------------------------------|  def ecatb_gain_rate # New; Hotspot    # Reloads the base atb rate and rate notetag lambdas only if they can change    if BattleManager.ecatb_base_change # The base atb rate change flag      @ecatb_base = BattleManager.ecatb_base.clone # The base atb rate    end    if @ecatb_battler_change[:rate] # The effective rate notetag change flag      @ecatb_battler_change[:rate] = false      reload_ecatb_notesrate) # Stores all new lambdas in @ecatb_notes[:rate]    end    #    base = @ecatb_base    @ecatb_notes[:rate].each { |note| base[:val] = note[self, base] }    base[:val] # The final atb rate  end  end # ecatb_gain_rate@ecatb_battler_change[:rate] will be set as true whenever any actor/class/weapon/armor/enemy/state data the battler's using changes or the battler's refreshed(including action point, tp change, state turns update and action confirmation in this case), as the effective rate notetag list shouldn't change unless at least 1 such data changes or at least 1 other known(by the script) battler state changes.

Performance - While both BattleManager.ecatb_base_change and @ecatb_battler_change[:rate] are improbable to be frequently set as true, every lambda stored in @ecatb_rate[:atb] will always be called whenever a battler calls ecatb_gain_rate, which can(and most of the time will indeed)be called per frame, meaning the total number of lambda calls can be the sum of all effective lambdas of all battlers per frame. This also means that that many lambdas need to be stored to be called by their respective battlers thorough the entire battle.

2nd algorithm - I add a script call to let users specify that the notetag RGSS3 code evaluation result can change due to some factors unknown by the script even for the exact same notetag RGSS3 code(and add some timings for them to use it), and only reevaluates all RGSS3 codes of all effective notetags when any part of the base atb rate changes, any effective notetags can become ineffective(or vice versa), or the same effective notetag can return different results, as these 3 are the only reasons to change the final atb rate, meaning I can cache the final atb rate and return that cached value when neither of those reasons to change's met(DoubleX RMVXA Enhanced YSA Battle System: Classical AT:

Spoiler

Added script call and user configurations:

#    5. ecatb_note_change[note] = true                                         |#       - Notifies at least a value of a notetag with type note of a data used |#         by the battler has changed                                           |#       - note can be :act, :atb, :charge, :cooldown, rder_icon,             |#         rder_opacity,rder_scale, rder_z, :rate, :se, :speed, :start_0, |#         :start_1, :start_2, meaning gradual action gain, charge rate,        |#         bar color, cooldown rate, order icon, order opacity, order scale,    |#         order z, atb gain rate, speed reduce, battler ready se and start     |#         value notetags with normal, preemptive and surprise start types      |#         respectively                                                         |#       - This script call can also be used to change the charge, cooldown, atb|#         gain rate and bar colors per frame when it's called per frame        |

      # Sets something to happen right before updating the atb clock      # Its corresponding method's created under Scene_Battle      # Example: To support changing atb, charge and cooldown bar colors of all      #          battlers per frame, set this as      #          %Q(all_battle_members.each { |mem|      #               mem.ecatb_note_change[:atb] =      #               mem.ecatb_note_change[:charge] =      #               mem.ecatb_note_change[:cooldown] = true      #             })      :pre_ecatb_update => %Q(),      # Sets something to happen right after updating the atb clock      # Its corresponding method's created under Scene_Battle      # Example: To call a common event with id x right after updating the atb      #          clock, set this as %Q($game_temp.reserve_common_event(x))      :post_ecatb_update => %Q()

Spoiler

  #----------------------------------------------------------------------------|  #  Caches and returns the atb rate                                           |  #----------------------------------------------------------------------------|  def ecatb_gain_rate # New; Hotspot    # Reevaluates the atb rate only if any of its determinators' changed    return @ecatb_rate[:atb] unless BattleManager.ecatb_base_change ||    ecatb_battler_change?(:rate)    @ecatb_rate[:atb] = set_ecatb_gain_rate(BattleManager.ecatb_base.clone)    #  end # ecatb_gain_rate  #----------------------------------------------------------------------------|  #  Evaluates the value of all atb gain rate notetags using its ordering      |  #----------------------------------------------------------------------------|  # base: The base atb gain rate  def set_ecatb_gain_rate(base) # v0.05a+; New; Potential Hotspot    ecatb_rate_ord.each { |data|      next unless send(@ecatb_item[data][0])      send(@ecatb_item[data][1]).each { |item|        (0..(item.ecatb_notes[:rate].size - 1)).each { |index|          next unless note = item.ecatb_notes[:rate][index]          base[:val] = note[self, base]        }      }    }    base[:val]  end # set_ecatb_gain_rate

  #----------------------------------------------------------------------------|  #  Checks if any new notetag added, old one gone or its value changed        |  #----------------------------------------------------------------------------|  # note: The notetag type to be checked  def ecatb_battler_change?(note) # New; Hotspot    change = @ecatb_note_change[note]    @ecatb_note_change[note] &&= !change    return change unless @ecatb_battler_change[note]    !(@ecatb_battler_change[note] = false)  end # ecatb_battler_change?

@ecatb_note_change[:rate] will only be true by using the ecatb_note_change[:rate] = true script call.

Performance - Both BattleManager.ecatb_base_change and @ecatb_battler_change[:rate] are improbable to be frequently set as true, meaning the only reason to change that are reasonable to be met frequently is @ecatb_note_change[:rate] being set as true, which must be explicitly done by the users, so all the effective lambdas will be normally loaded and evaluated frequently for such users, but usually they will only be loaded and evaluated sparsely for almost all of the other users. Moreover, no such lambda will ever be stored by any battler in both cases as well.

Performance Comparison - In terms of memory usage, the 2nd algorithm nearly always beats the 1st one, as no lambda will ever be stored by any battler in the former, while all effective lambdas will be stored by all battlers thorough the entire battle. In terms of time performance, the 2nd algorithm will be slightly worse than the 1st one for users that frequently use the ecatb_note_change[:rate] = true script call, as both that added script call and @ecatb_note_change[:rate] check do have running time(albeit trivial compared to loading and evaluating all effective lambdas), but the 2nd algorithm will be drastically better then the 1st one for almost all of the other users, as the former's only expected to load and evaluate all effective lambdas sparsely while the latter will always evaluate them all per ecatb_gain_rate call, which can(and most of the time will indeed)be called per frame, meaning the total number of lambda calls can be the sum of all effective lambdas of all battlers per frame. As it's reasonable to assume that the majority of users won't use the ecatb_note_change[:rate] = true script call frequently, overall the 2nd algorithm will still beat the 1st one in terms of time performance when all users are considered.

How did I come up with the 1st algorithm - It's done by not realizing that sometimes asking users to take some responsibilities can indeed do more good than harm for them. When I've absolutely no control on when the same user configurations will return different results even when nothing else the script knows changes, just ask the users to notify the script for such possible changes. In this case, those having to use the added ecatb_note_change[:rate] = true script call frequently are typically more advanced users writing RGSS3 codes using rand(possibly returning different results per call) or some other frequent yet unhandled changes(those the script doesn't know) coming from some other custom scripts(which are compatibility issues), so it's crystal clear and obvious that using that script call frequently is really effortless for them. The added responsibility and running time cost are relatively trivial for those users, but the time and memory performance boost for almost all of the other users are much more enormous, meaning the added responsibility's actually an excellent and might be the best balance for both user groups.