I'm writing a "timetable generator" program for a faculty at a university.Quote:
Originally Posted by PredicateNormative
The program takes, as input, the courses a student wishes to take. Typically, a student will take 5 courses at a time, and each course can have a lecture component, a tutorial component and a practical component. There are typically multiple timeslots to choose from for each component of a course, so that a student can assemble a working timetable.
Thus, for any given set of courses, a certain number of timetables are possible, given by
TOTAL_POSSIBLE = n_lecture(1) * n_tutorial(1) * n_practical(1) * n_lecture(2) * n_tutorial(2) * ...
where n_lecture(1) is the number of possible timeslots for the lecture component of course 1, n_tutorial(1) is the number of possible timeslots for the tutorial component, and so on.
Of course, not all possible timetables are valid, because some timeslots conflict with each other. The purpose of the program is to "weed out" the ones that conflict, and display to the user the ones that are valid.
For most sets of courses, this process takes at most a few seconds. However, the occasional set of courses will come up where every course has all three of the components, and every course has 5-10 possible timeslots for each of the components. In situations like this, TOTAL_POSSIBLE can takes values in the hundreds of billions. Of the hundreds of billions of possible timetables, I estimate that between 10 and 100 million are valid.
Now the "weeding" algorithm is very efficient: it does NOT, as a naive solution might, generate all the possible timetables, then check each one, and remove the invalid ones - this would be ridiculous in a case like the onoe above, where there are hundreds of billions of possible timetables. In fact, the algorithm barely uses any additional memory other than the memory required to store the valid timetables.
But if we have, say, 80 million valid timetables, that's still 80 million timetables x 45 bytes per timetable = 3.6 GB of memory I need.
Using the standard allocator, the algorithm gets around to generating 8 million before throwing bad_alloc. Using Loki::SmallObjAlloc, I can now reach 16 million - a definite improvement. But I've still got a long way to go to 80 million, and as I said, it seems that under 32-bit Windows, my only option will be to somehow manually "page" the timetables to the hard drive, which will be a pain in the behind, because it will slow sorting the timetables (already a time-consuming operation with 80 million of them) to a crawl (and sorting becomes especially necessary with 80 million timetables - after all, what student will look through all 80 million of them to find the one that works best!)
