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

[alexti <al...@sh...>]

Stefan,

I think you iterate in some completely different manner. I am still unsure  
what you do when you encounter a "branch" during the iteration. For  
example station is connected to the city with 6 exits, so when you  
consider the route from the station to this city it can continue in 5  
different directions. How do you iterate over these directions?


> 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.
This is an interesting idea. This operation would be equivalent to my  
"evaluation". I would imagine it's faster when you are "extending" your  
route, but when you switch between "branches" you would have to "undo" by  
removing values added in the old branch. I wonder if it's faster that  
recomputing from scratch every time...

My run time is currently divided approximately 50-50 between the train  
revenue calculation and everything else (iterating over possible routes,  
including validity of those routes etc). Where do you spend most of the  
time?

Alex.



On Sun, 16 May 2010 15:32:28 -0600, Stefan Frey (web.de)  
<ste...@we...> wrote:

> 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.
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/