[Mapserver-dev] Speed Improvement Fix.

[Alan Steremberg]

Actually it was O(n^2) :-)


----------------------------
 Alan Steremberg
 415-543-5021 x 103
 http://www.wunderground.com

On Wed, 5 Nov 2003, Alan Steremberg wrote:

>
> Hi,
>
> I am not sure if this changes the drawing behaviour, but I was able to
> speed up one of the layers I was drawing by a factor of 4-6.
>
> Here is the issue:
>   When drawing Overlay symbols, mapdraw caches everything using
> 'insertFeatureList'.  insertFeaturelist is a linked list with a tail
> insertion. This is n*log(n).  I switched the algorithm to a head insertion
> which is time n.  It is possible that the lines will now draw backwards
> (not sure if this is a problem) if it is, we should change the linked list
> structure to have a last pointer that we can keep updated.
>
> here is my modification:
>
> mapfile.c:
>
> /* AJS -- link the list the other way?? */
> /* BEFORE --> */
> #if 0
>   node->next = NULL;
>
>   previous = NULL;
>   current = *list;
>   while(current != NULL) {
>     previous = current;
>     current = current->next;
>     i++;
>   }
>
>   if(previous == NULL) {
>     *list = node;
>   } else
>     previous->next = node;
> #endif
> /* AJS */
> /* AFTER, two lines of code */
>     node->next=*list;
>     *list=node;
>
>
> Thoughts?
>
>
> Alan
>
> ----------------------------
>  Alan Steremberg
>  415-543-5021 x 103
>  http://www.wunderground.com
> _______________________________________________
> Mapserver-dev mailing list
> Mapserver-dev at lists.gis.umn.edu
> http://lists.gis.umn.edu/mailman/listinfo/mapserver-dev
>