[pgrouting-dev] Non-scheduled Routing algorithm

[Anton Patrushev]

Hi Kishore,

I agree with Steve - mapping text vertex labels to integers makes more sense.
Same for Pl/pgSQL performance - I think it is OK to have it done like
this. The problems with Pl/pgSQL is its language limitation which
limits us in programming techniques, but it is OK as long as you can
solve your problem with what you have.


Anton.

On 6/14/11, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:
> On 6/13/2011 1:28 PM, Kishore Kumar wrote:
>> Hi,
>>
>> I am facing the following issues in the prototype code[1]:
>>
>> 1. As I am internally calling Dijkstra function and the Dijkstra
>> implementation assumes that vertex id and edge id are integers but
>> according to GTFS, stop id and route id can be text also. This can be
>> solved by:
>>   a. Generating a new table that maps Auto-generated integers to Stop
>> Ids(Map<Integer,Text>)
>>   b. Modifying Dijkstra implementation to accept vertex id of type text
>
> I think I would do a. above. The reason is text id's are really for
> people and and integer id's computers like. And it is likely that doing
> b., you would need to remap the text labels to integer anyway for
> performance reasons.
>
>> 2. Since the non-scheduling algorithm is not directly doing any lower
>> level calculations, I implemented the prototype using PL/pgSQL
>> language. Is rewriting the same logic in c is required and does it
>> provide any significant performance boost? According to a post in
>> pgsql-performance list[2], "I wouldn't expect the queries called by
>> the pl/pgsql function to be much faster if called through SPI from C
>> instead.". Hence, my current thought is to give real-life data as
>> input and check for performance problems and if performance is bad,
>> write the code in c.
>
> I do not have direct test experience to back this up, but assuming pgsql
> as a language is implemented similar to Perl or python the standard is
> to compile the source to bytecode and then run a bytecode interpreter.
> This gives very good perfomance when 90% of the time is spend in library
> functions that really are compiled C/C++ and called from the
> interpreter. Where you start to run into performance problems is when
> you have a lot of code or a lot of looping and evaluating expressions.
> That said, the rule for optimizing code is to measure first and then
> remove the worse bottle neck, and then repeat until you are happy with
> the results. So I see no problem with a prototype in pgsql, and later it
> or part of it can be rewritten to C if there are performance issues.
>
> Hope this helps,
>    -Steve
>
>> Thanks&  Regards,
>> J Kishore kumar.
>>
>> [1] -
>> https://github.com/pgRouting/pgrouting/blob/gsoc-multimodal/extra/transit/sql/nonscheduled.sql
>> [2] -
>> http://archives.postgresql.org/pgsql-performance/2010-05/msg00199.php
>>
>> On Sun, Jun 12, 2011 at 1:30 PM, Anton Patrushev
>> <anton.patrushev at georepublic.de>  wrote:
>>> Hi Kishore,
>>>
>>> Ah, now I got it. Well, here in Russia some bus routes also don't have
>>> fixed schedule and are regulated by number of buses/trips. Thus I
>>> think the idea makes sense.
>>>
>>> Anton.
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>


-- 
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Anton Patrushev
CTO

eMail: anton.patrushev at georepublic.de
Web: http://georepublic.de

Tel: +49 (089) 420 959 519
Sip: 1959519 at sipgate.de

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl