Re: [Rails-devel] Route calculation validations

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

I've figured I could do a quick experiment and change the order of train  
iteration. So here are new results:
8+10 - 3649121, 4.5s
8+D - 16097719, 22.7s

8+D case is much faster now and 8+10 is slightly faster. I am not sure I  
understand this result - number of evaluations is nearly identical (I am  
not entirely sure if it's supposed to be identical or not and anyway I  
don't trust my ability to calculate each route only once :) ). So why the  
time went down? Besides, I expected this swap to improve diesel case, but  
8+10 being faster than 10+8 surprises me...



On Mon, 19 Apr 2010 22:49:51 -0600, alexti <al...@sh...> wrote:

> Hi Stefan,
>
> Here are my numbers. It's pointless to compare edges, because I'm using
> 2-phased approach, so I'm only giving number of revenue evaluations. I
> also assume that you're talking about 10+8 when you say "10+6" (that  
> seems
> obvious from the attached stats). The good news is that the optimal
> revenue we're getting is identical in all cases. The bad news is that
> everything else is different. I have much higher number of revenue
> evaluation. I suspect that I evaluate something unnecessary (considering
> that I never find any better route :) ). That's not necessarily bad -
> perhaps if I get rid of it I can compute things faster. It's interesting
> that none of our methods is good for diesel plus other train. What's
> worse, I think that this time can deteriorate dramatically on the  
> examples
> with more cities. The root of the problem is that there might be a lot of
> different diesel routes with very small value variation (like within
> 10-30$) which would mean that in each case the remaining graph will have
> to be evaluated for the 8 train...
>
> Btw, in what order do you iterate over trains? I go from longest to
> shortest. On some earlier tests I've decided that it worked better, but
> now I wonder if the diesel case might be an exception...
>
> 8 - 5601, 0.003s
> D - 957676, 1.4s
>
> 10+8 - 3649238, 5.8s
> D+8 - 16110745, 74.5s
>
> Thanks,
> Alex.
>
>
>
> On Mon, 19 Apr 2010 14:01:14 -0600, Stefan Frey <ste...@we...>  
> wrote:
>
>> Hi Alex,
>> I have attached a document that contains the detailed numbers for  
>> several
>> train combinations without and with the revenue prediction active.
>>
>> The following figures are defined:
>> revenue evaluation: how often the revenue of all trains is evaluated
>> edges travelled: how many edges were followed during the search
>> predictions: how often the potential maximum revenue was predicted.
>>
>> My desktop is even slower as my laptop, as it is slightly older and has
>> an AMD
>> processor.
>>
>> It clearly shows that revenue predictions is strongest for train
>> combinations
>> and non-diesel trains. Running a diesel alone is not any faster, unless
>> an
>> optimal solution is found (early).
>>
>> Stefan
>>
>> I sent that to the develop list, as others might also be interested in
>> those
>> numbers. I extract the main figures below,
>> all runs on the test scenario A.
>>
>> 8 train alone:
>> without prediction: 3.8k evaluations, 16.4k edges, time: < 1 sec
>> with prediction: 62 evaluations, 858 predictions, 2.3k edges, < 1 sec
>>
>> 8 and 10 trains:
>> without prediction: 1.9M evaluations, 11.0M edges, time: 90 sec
>> with prediction: 25k evaluations, 143k predictions, 387k edges, time: 4
>> sec
>>
>> This clearly shows the strong increase of possible solutions, if more
>> than one
>> train is involved. It is around 1:500!
>>
>> Diesel train:
>> without prediction: 424k evaluations, 3.3M edges, time: 25 sec
>> with prediction: 335k evaluations, 753k predictions, 2.6M edges, time:
>> 23 sec
>> (In this example an optimal solution is found, but late).
>>
>> A diesel is less complicated than the combination of an 8 and 10, but  
>> the
>> revenue prediction does no help.
>>
>> Diesel and a 6 train:
>> without prediction: 7.3M evaluations, 52.5M edges, time: 480 sec
>> with prediction: 231k evaluations, 2.8M predictions, 6.2M edges, time:
>> 56 sec
>>
>> Adding a 6 train, increases the running time by 20 without prediction,
>> but
>> only a little more than doubles with prediction.
>>
>>
>>
>> On Sunday 18 April 2010 17:44:04 you wrote:
>>> Hi Stefan,
>>>
>>> I would agree about the name of the first number.
>>>
>>> (1) should be ok, I do the same, and there is no good reason for the
>>> algorithm to try evaluating route that just extend already evaluated
>>> route
>>> by some stations the train can't reach anyway. Or we could run the test
>>> on
>>> "express" train that can skip anything. Express trains (or any train
>>> capable of skipping cities) actually make me wonder what are possible
>>> rules about visiting the same hex. In some games train is not allowed  
>>> to
>>> visit the same hex twice (when there are 2 separate cities on the  
>>> tile).
>>> If there is any game with this rule and with express trains, then
>>> there's
>>> a question - if the train skips one city in the hex and counts another  
>>> -
>>> is it valid route?
>>>
>>> (2) I apply the same method to the routes, but I didn't evaluate "half"
>>> routes - I only evaluate complete route (consisting of those 2 parts).
>>> How
>>> can you do differently? - There might be bonus for visiting 2 cities in
>>> different halves, or something like east-west run.
>>>
>>> If it's difficult to extract this number from your code now, we could
>>> set
>>> up example with the station in the dead-end, so there's only one way to
>>> leave it.
>>>
>>> Number of segments is relevant to the two-phased approach only. It is
>>> number of edges in the "coarse" graph (which is the same as number of
>>> distinct ways to travel between any pair of cities). You were asking
>>> about
>>> this number earlier to evaluate amount of memory that would need to be
>>> stored.
>>>
>>> I've also done profiling and it appears that storing segment exclusions
>>> as
>>> a vector of segments excluded by each segment is fine - this is not a
>>> bottleneck. So I haven't tried 2D array of booleans approach. But maybe
>>> I
>>> should try some different cases (for example set of 4 trains (2,2,3 and
>>> 3)
>>> - that may have a bottleneck in different places comparing to the case
>>> of
>>> few long trains).
>>>
>>> Thanks,
>>> Alex.
>>>
>>> On Sun, 18 Apr 2010 13:28:24 -0600, Stefan Frey <ste...@we...>
>>> wrote:
>>> > Hi Alex,
>>> > I would call the first statistic "number of  route evaluations" and  
>>> it
>>> > counts
>>> > every call to the evaluation function. This figure is also available
>>> for
>>> > multiple-train runs. If we have the same number, it is almost sure
>>> that
>>> > the
>>> > two algorithms work identical. If not, it proves nothing, see below.
>>> >
>>> > Potential problems:
>>> > 1) I terminate trains as soon as possible, thus numbers depend on the
>>> > sequence
>>> > of vertexes visited.
>>> >
>>> > 2) I have train runs divided in two half trains: First the head train
>>> > starts
>>> > and each station the train can return to its start token and then the
>>> > bottom
>>> > train runs. To avoid duplication of routes (due to symmetry) the
>>> bottom
>>> > train
>>> > can only start to the side with increased orientation. If I remember
>>> > that is
>>> > a different approach to yours.
>>> >
>>> > So if we want to compare figures we have to run a train with infinite
>>> > length
>>> > (to avoid termination) and is not allowed to run twice from the start
>>> > vertex.
>>> >
>>> > I will have to adjust my codes to accommodate for such a test.
>>> >
>>> > The other statistic I am not fully clear about: Wat is exactly the
>>> > number of
>>> > segments? If this is related to the two-phase approach I assume this
>>> is
>>> > the
>>> > maximum number of connections between two stations on the map?
>>> > And I guess, that this might be the answer to the unrelated question  
>>> I
>>> > raised
>>> > before. This strengthens the case of your approach. I will implement
>>> it
>>> > as
>>> > soon as I have some time left, which will be most likely after the
>>> next
>>> > release.
>>> >
>>> > Stefan
>>> >
>>> > On Sunday 18 April 2010 06:34:51 you wrote:
>>> >> Hi Stefan,
>>> >>
>>> >> I thought it might be useful to compare how many routes we try  
>>> during
>>> >> the
>>> >> complete route search. We should be getting the same number. If we
>>> are
>>> >> not
>>> >> it will indicate that one of us (or both) have a bug. I suppose to
>>> test
>>> >> it
>>> >> we would need to run a single sufficiently long train (or maybe try
>>> for
>>> >> various train lengths) on the same track.
>>> >>
>>> >> I've also checked on number of segments in two-phased approach. In
>>> the
>>> >> scenario B there are just 153 segments.
>>> >>
>>> >> Thanks,
>>> >> Alex.
>>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> 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/