Re: [Rails-devel] Improved revenue prediction / different scenario

[Stefan F. (web.de) <ste...@we...>]

Alex,
answers and comments see below:

> I am curious, how do you avoid dynamic memory allocation during the
> iteration through the routes? With the switch to the two-phased approach I
> also couldn't avoid some dynamic sizing in the second phase graph.
>

I convert all information from the graph and other objects into a simple 
arrays, where I define the size at the initialization of the revenue 
calculator (usually to the maximum number of trains, vertices, edges etc).
Thus I never create any objects throughout the iterations.

The dynamic data arrays are:
    // dynamic train data
    private final int[] trainCurrentValue;
    private final int[] trainMajors;
    private final int[] trainMinors;
    private final boolean[][] trainVisited; // dimensions: train, vertex
    private final int[][] trainVertexStack; // dimensions: train, vertex
    private final int[][] trainEdgeStack; // dimensions: train, edge
    private final int[] trainStackPos;
    private final int [] trainBottomPos;
    private final int [] trainStartEdge;

    // dynamic bonus data
    private final int [][] bonusTrainVertices; // dimensions: bonus, train

> >> What exactly 5,651k predictions in your case mean?
> >
> > Evaluations count the call to the function that sums up the value of all
> > trains after all trains are finished.
>
> Can you tell from this number how many times revenue of the route has been
> computed?

In fact I do not sum up  the revenue of the routes from vertex values each 
time, but I update the currentTrainValues each time a vertex is encountered 
or left. The only summation is done over the set of trains. The separation 
into single trains (instead of updating a joint value) allows the revenue 
prediction of the current running train. 

>
> > Predictions count the call to the function used after each station visit.
> >
> > Actually the latest refactoring (I do not evaluate anymore until I reach
> > the
> > second station, previously I set that to zero) reduced the number of
> > evaluations and predictions:
> > The number of evaluations drops to 480k, the number of predictions to
> > 2,950k, the number of edges travelled does not change.
> > Speed improvement is minor (10-15%).
>
> This sounds like what I was calling revenue of the route computation. Is
> it the place were you total value of cities and apply bonuses?

As mentioned above, I do not total city values at the evaluation, but 
continuously. The only summation is over trains.

Bonuses are added to the current train value when they are scored or 
(un-)scored again. For each bonus/train combination a counter is initialized 
with  the number of required vertices (this is the bonusTrainVertices array 
above). Each time a trains visit a required vertex, the counter for that 
bonus is decreased. If zero is reached the bonus value is added. If the 
counter increases to one again, the bonus value is subtracted.