Re: [Rails-devel] Automatic route calculation

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

On Sun, 21 Mar 2010 11:59:01 -0600, brett lentz <bre...@gm...>  
wrote:

> On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
>> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
>> wrote:
>>
>>> http://en.wikipedia.org/wiki/Big_O_notation
>>>
>>> O(n!) means that for each vertex/edge that's added to the calculation,
>>> the time it takes for the algorithm to reach a solution grows by a
>>> factorial order of magnitude.
>> Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that  
>> if
>> you go from 1000 to 2000 than your time will increase by 2000!/1000!
>> factor. In 18xx games there is also an interesting property of adding an
>> edge unconnected to the station does not increase time at all and this  
>> is
>> not uncommon in many games (at first because the track is not connected
>> and later because it is blocked).
>>
>> Alex.
>
> You're right. Our problem isn't strictly the traveling salesman (which
> is usually where O(n!) is seen).  I don't expect your algorithm to be
> O(n!), but maybe closer to O(n^2) or O(2n).
>
> ---Brett.

Unfortunately, I haven't done any formal analysis of my algorithm and I  
didn't know what is its asymptotic behaviour and how it behaves on a more  
typical range of n. Besides, on the modern hardware there are some  
interesting dependencies related to the memory speed vs CPU speed. There's  
a dramatic performance drop when the working data set stops fitting into  
the cache.

Talking about software design, should the route calculation be run in a  
separate thread, so that the user doesn't experience "screen freeze" if  
for some reason it's taking too long? Also, as John has suggested, we  
could time-out or let the user cancel the calculations in those cases.

Alex.