# SOME WAYS TO COME UP WITH LESS PERFORMANT ALGORITHMS

### Incites other scripters to share some causes behind some less performant algorithms(Mainly about time and memory usage)

• DoubleX
• 03/08/2015 02:33 AM
• 868 views
Disclaimer:
Performance isn't everything, it isn't even always the most important thing. All the other programming aspects should be taken care of as well. Scripters should have a clear understanding of the importance and priority of each programming aspect in each part of their codes to ensure a working balance. They should also take their own current scripting proficiency into account to ensure none of their codes will ever be out of their control.

Let's start by showing how I came up with less performant algorithms lol

Example 1
Suppose I've to check if a battler's any new or removed states and the checking can be needed at any frame. The result is used by at most 1 method for at most once per frame and the usage timing can be different from that of changing states.

1st algorithm - I write a battler method being called per frame, which checks if the current state array is the same as that in the last frame and returns the result:
```def battler_state_change?
return false if @states == @last_states
@last_states = @states.clone
true
end
```

Performance - The time complexity of this algorithm's at least O(n) and the memory has to read and probably write(when the state array's changed) an array.
It seems acceptable for me at first, but after a while I reviewed this method and asked "Can it be better?". Fortunately, I came up with a more performant algorithm shortly afterwards.

2nd algorithm - I first use a variable to mark that a battler's added or removed a state, then write a method to reset that variable and returns true if that variable's true:
```alias clear_states_example clear_states
def clear_states
clear_states_example
@state_change = true
end

@state_change = true
end

alias erase_state_example erase_state
def erase_state(state_id)
erase_state_example(state_id)
@state_change = true
end

def battler_state_change?
return false unless @state_change
@state_change = false
true
end
```

Performance - The time complexity of this algorithm's O(1) and the memory has to read and probably write(when the state array's changed) a boolean value.

Performance comparison - The 2nd algorithm is clearly more performant than the 1st one, and the difference of their results can become non-trivial when there are lots of battlers each having lots of states. The fact that both can be run every frame significantly magnifies the difference, which may cause a less powerful machine to use a constant average fps drop to complain XD
Although the 2nd algorithm can be more prone to compatibility issues(like when some scripts that have to be placed below my script have rewritten clear_states, add_new_state or erase_state), they shouldn't be too hard to solve in most cases.
You may argue that the increased number of method calls might outweight what the 2nd algorithm gains, but it'd be true only if states are added and/or removed every several frames, which is extremely unlikely.

How did I come up with the 1st algorithm - It's done by directly translating the requirements into algorithms without even analyzing those requirements beforehand. That direct translation causes me to think that it's necessary to store the state array in the last frame and compare that with that in the current frame as the latter can be changed in any frame.
After analyzing those requirements for a while, however, I realized that if I can catch all the codes that changes the state array, I can just use an instance variable to mark that the state array's changed. It just have to be reset to its default value right after notifying the change to ensure correct notification.

On a side note, if a state's added and removed again before calling battler_state_change? again, algorithm 1 will say the state array didn't change but algorithm 2 will say the state array changed(I don't know if there are some other cases which can also cause this). If this case's non-trivial, then pick the one giving the desired result, as correctness almost always comes before performance, unless all the correct choices have intolerable performance issues(and in this case they don't in general).

Example 2(Slightly modified version of the YSA-CATB Percentage Addon)
Suppose I've to update the position of all the 5 atb bars(back, atb, charge, cooldown, percentage) of each enemy per frame to ensure they're all always placed directly below each enemy's sprite.

1st algorithm - I use the enemy sprite x and y positions to set all that enemy's atb bars directly below that enemy's sprite, and ensure they won't overlap with the status window(mostly the original Yami's algorithm with quite some minor twists, added support to that script and some compatibility issues):
(Both @type and @start_width are fixed once set; update_position is the only method changing the atb bar positions)
```#----------------------------------------------------------------------------|
#  Rewrite method: update_position                                           |
#----------------------------------------------------------------------------|
def update_position
dx = @battler.screen_x - @start_width / 2
dy = @battler.screen_y
# Added to set the x and y offset of percentage text
if @type == :percent
dx += TEXT_X_OFFSET
dy += TEXT_Y_OFFSET
end
#
rect.x = dx
dh = rect.height + 1
# Rewritten to ensure the percent bar won't overlap with the status window
dh += 2 unless @type == :back || @type == :percent
dy = [dy, Graphics.height - dh - 120].min
dy += 1 unless @type == :back || @type == :percent
#
# Added to be compatible with DoubleX RMVXA Enemy MP/TP Bars Addon to YEA-BattleEngine and YEA-EnemyHPBars
dy -= ENEMY_MP_GAUGE_HEIGHT + ENEMY_TP_GAUGE_HEIGHT if TP_MP_ADDON
dy -= YEA::BATTLE::ENEMY_GAUGE_HEIGHT if \$imported["YEA-EnemyHPBars"]
#
rect.y = dy
end # update_position
```

Performance - Right now it's just too complicated for me to analyze, but my data suggests that the above code's quite expensive.
It' still great though as it does almost nothing redundant and the codes are nearly optimized(as it's mostly the Yami's original algorithm with some minor twists to boost the performance a bit further :)).

2nd algorithm - I first check if the enemy sprite x and y positions are changed, and use the 1st algorithm only if at least 1 of them changed:
(Both @type and @start_width are fixed once set; update_position is the only method changing the atb bar positions)
```#----------------------------------------------------------------------------|
#  Rewrite method: update_position                                           |
#----------------------------------------------------------------------------|
def update_position
dx = @battler.screen_x
dy = @battler.screen_y
# Added to update the atb positions only if the battler's position's changed
return if @last_x == dx && @last_y == dy
@last_x = dx
@last_y = dy
dx -= @start_width / 2
#
# Added to set the x and y offset of percentage text
if @type == :percent
dx += TEXT_X_OFFSET
dy += TEXT_Y_OFFSET
end
#
rect.x = dx
dh = rect.height + 1
# Rewritten to ensure the percent bar won't overlap with the status window
dh += 2 unless @type == :back || @type == :percent
dy = [dy, Graphics.height - dh - 120].min
dy += 1 unless @type == :back || @type == :percent
#
# Added to be compatible with DoubleX RMVXA Enemy MP/TP Bars Addon to YEA-BattleEngine and YEA-EnemyHPBars
dy -= ENEMY_MP_GAUGE_HEIGHT + ENEMY_TP_GAUGE_HEIGHT if TP_MP_ADDON
dy -= YEA::BATTLE::ENEMY_GAUGE_HEIGHT if \$imported["YEA-EnemyHPBars"]
#
rect.y = dy
end # update_position
```

Performance - It's O(1) and several added memory access to some integer values + that of the 1st algorithm when the enemy sprite position changes, otherwise it's just O(1) and several added memory access to some integer values, unless the screen_x or screen_y readers are rewritten to some insane stuffs.

Performance Comparison - In most cases, it'll perform significantly better than the 1st algorithm, as normally it's quite unlikely that an enemy sprite x and y positions will change frequently(let alone per frame), and the position checking's cheap while the 1st algorithm's expensive. The average fps boosted by at least 2 by switching from the 1st algorithm to the 2nd algorithm in my machine, which can be noticeable.

How did I come up with the 1st algorithm - It's done by directly implementing my percentage addon to YSA-CATB and solving compatibility issues without asking "Can really great codes be even better?". This causes me to merely did some minor optimizations instead of rethinking the Yami's algorithm.
As my percentage addon sucks hard(it still is) and causes a 30+ average fps drop(from roughly 119 to roughly 88) in my machine, I had to optimize every last bit of the addon. Then I realized that all the atb bar positions need to be changed only if the enemy sprite's position's changed, as the 1st algorithm won't change the formers at all unless the latter's changed. So I decided to call the 1st algorithm only if the latter's changed to reduce the amount of redundant code executions.

Example 3(Slightly modified version of (DoubleX)Intercept Magic)
Suppose I've to read some notetags used by that script from the database.

1st algorithm - I check each line against all notetags to be read:
```#----------------------------------------------------------------------------|
#  New method: load_notetags_intercept_magic                                 |
#----------------------------------------------------------------------------|
@intercept_tier = 0
@intercept_chance =100
@battler_intercept = {}
@intercept_mp = @intercept_tp = @hit_intercept_mp = @hit_intercept_tp = false
@note.split(/[\r\n]+/).each { |line|
if line =~ /<(?:INTERCEPT_TIER|intercept tier):[ ]*(\d+)>/i
@intercept_tier = \$1.to_i if \$1.to_i > @intercept_tier
end
if line =~ /<(?:INTERCEPT_MP|intercept mp)>/i
@intercept_mp ||= @intercept_tier > 0
end
if line =~ /<(?:INTERCEPT_TP|intercept tp)>/i
@intercept_tp ||= @intercept_tier > 0
end
if line =~ /<(?:HIT_INTERCEPT_MP|hit intercept mp)>/i
@hit_intercept_mp ||= DoubleX_RMVXA::Intercept_Magic::Intercept_MP_Limit && @intercept_mp
end
if line =~ /<(?:HIT_INTERCEPT_TP|hit intercept tp)>/i
@hit_intercept_tp ||= DoubleX_RMVXA::Intercept_Magic::Intercept_TP_Limit && @intercept_tp
end
if line =~ /<(?:ALLY_INTERCEPT|ally intercept)>/i
@battler_intercept[:ally] = true
end
if line =~ /<(?:ENEMY_INTERCEPT|enemy intercept)>/i
@battler_intercept[:enemy] = true
end
if line =~ /<(?:INTERCEPT_CHANCE|intercept chance):[ ]*(\d+)>/i
@intercept_chance = \$1.to_i / 100.0 if \$1.to_i < @intercept_chance
end
}
```

Performance - I don't know the performance of reading regular expressions(O(n)? O(n^2)? Just my wild guesses for its time complexity), but it's also determined by the number of lines of the item and that of the notetags to be read. The more notetags to be read, the more time the above algorithm needs. The memory usage depends on what and how many notetags are read, and right now it's too complex for me to analyze.
I was satisfied. It works and theoretically it does what it just need to do.

2nd algorithm - Similar to the 1st one, but once a notetag's read the method jumps right to the next line. Also, I check the most frequent notetag first:
```#----------------------------------------------------------------------------|
#  New method: load_notetags_intercept_magic                                 |
#----------------------------------------------------------------------------|
@intercept_tier = 0
@intercept_chance =100
@battler_intercept = {}
@intercept_mp = @intercept_tp = @hit_intercept_mp = @hit_intercept_tp = false
@note.split(/[\r\n]+/).each { |line|
case line
when /<(?:INTERCEPT_TIER|intercept tier):[ ]*(\d+)>/i
@intercept_tier = \$1.to_i if \$1.to_i > @intercept_tier
when /<(?:INTERCEPT_MP|intercept mp)>/i
@intercept_mp ||= @intercept_tier > 0
when /<(?:INTERCEPT_TP|intercept tp)>/i
@intercept_tp ||= @intercept_tier > 0
when /<(?:HIT_INTERCEPT_MP|hit intercept mp)>/i
@hit_intercept_mp ||= DoubleX_RMVXA::Intercept_Magic::Intercept_MP_Limit && @intercept_mp
when /<(?:HIT_INTERCEPT_TP|hit intercept tp)>/i
@hit_intercept_tp ||= DoubleX_RMVXA::Intercept_Magic::Intercept_TP_Limit && @intercept_tp
when /<(?:ALLY_INTERCEPT|ally intercept)>/i
@battler_intercept[:ally] = true
when /<(?:ENEMY_INTERCEPT|enemy intercept)>/i
@battler_intercept[:enemy] = true
when /<(?:INTERCEPT_CHANCE|intercept chance):[ ]*(\d+)>/i
@intercept_chance = \$1.to_i / 100.0 if \$1.to_i < @intercept_chance
end
}