kenrick95
[Performance] Optimize performance by reducing search space with pruning
Background
While b9ab611cb9bdbd4591dde56c80afe5c99fc00ba8 is a stop-gap to terminate the traversal of the search-space prematurely for the backtracking algorithm when 10k results is reached, it might be insufficient under cases where users have selected a designated "free-time".
When a "free-time" is selected, the backtracking algorithm might have to traverse a larger search-space to find the required solution. On top of that, there might not be a solution in the search space. As such, the 10k hard limit will not be reached, causing the algorithm to run sufficiently long, causing a 503 TIMEOUT.
Example
Let's use the AY2023-2024 example for computer engineering. [source]
The number of indexes for each of the mod can be is as such:
| Module | Number of Index(es) |
|---|---|
| SC1003 | 35 |
| SC1005 | 23 |
| SC1013 | 27 |
| MH1810 | 71 |
| EG1001 | 51 |
| CC0003 | 658 |
| CC0005 | 644 |
The search space has a size of (product of number of indexes in each module) 33,350,314,236,120 (33 trillion).
Problem
If users did not specify a "I want a free day", the page will quickly return the first 10k valid results. However, if users specifies that they want a free day, the search space will be too large and will cause a timeout before ANY valid results is returned.
Solution
Given that users have provided the blocks of free time that they want, indexes in each module can be pruned if they clash with the free time blocks that users provided. The fix should take advantage of the fact that users' provided free time is actually not DEPENDENT on any other modules<>indexes. Hence this can be done ahead of traversal.
The pruning of indexes will have a linear run time of O(N), where N is the sum of indexes of the modules provided by user.
The pruning can take place after check exam schedule. This will drastically reduce the search space required to traverse by the backtracking algo.
https://github.com/kenrick95/plan/blob/e98560c2d5c38e1aed1e2f8d4d2134d444d201d5/back_end/scheduler.php#L44-L69
Impact
Basically any modules that have a large set of indexes (usually common mods) which Y1 students are suppose to take.
Difficulty
Low, need to implement a prune function to return the list of indexes for each module that does not clash with user's free time by reusing check_clash function.
@voonhous Thanks for the feedback
I might be wrong, since the codes was written almost 10 years ago, but I think we already did that? We marked the timetables' slots here as occupied before we even start with the generate_timetable
https://github.com/kenrick95/plan/blob/e98560c2d5c38e1aed1e2f8d4d2134d444d201d5/back_end/scheduler.php#L45
though if you think you can optimize it further, feel free to send a pull request
