[GRASS-dev] v.what.rast speedup - was Re: r.random: now with optional cover map parameter

[Glynn Clements]

Markus Neteler wrote:

> >> > since v.what.rast is (for me) extremely slow, I have added
> >> > cover map support to r.random.
> >> ..
> >> > PS: v.what.rast still running on just 300k points while I
> >> >     implemented above :-) Anyone who could make v.what.rast faster?
> >> 
> >> Maybe it's the qsort(), maybe it's the i,j loop within a loop.
> > 
> > The loop is certainly inefficient. Rather than shifting the entire
> > array down every time it finds a duplicate, it should keep separate
> > source and destination indices, e.g. (untested):
> > 
> >     for (i = j = 0; j < point_cnt; j++)
> >         if (cache[i].cat != cache[j].cat)
> > 	    cache[++i] = cache[j];
> >         else
> >             cache[i].count++;
> >     point_cnt = i + 1;

> I am afraid to say that I don't know how to implement the suggestion
> in v.what.rast...

--- vector/v.what.rast/main.c	17 Oct 2007 14:07:23 -0000	1.26
+++ vector/v.what.rast/main.c	21 Oct 2007 17:52:42 -0000
@@ -218,21 +218,14 @@
     qsort (cache, point_cnt, sizeof (struct order), by_cat);
 
     G_debug(1, "Points are sorted, starting duplicate removal loop");
-    i = 1;
-    while ( i < point_cnt ) {
-        if ( cache[i].cat == cache[i-1].cat ) {
-	    cache[i-1].count++;
-	    for ( j = i; j < point_cnt - 1; j++ ) {
-		cache[j].row = cache[j+1].row; 
-		cache[j].col = cache[j+1].col; 
-		cache[j].cat = cache[j+1].cat; 
-		cache[j].count = cache[j+1].count; 
-	    }
-	    point_cnt--;
-	    continue;
-	}
-        i++;
-    }
+
+    for (i = j = 0; j < point_cnt; j++)
+        if (cache[i].cat != cache[j].cat)
+	    cache[++i] = cache[j];
+        else
+            cache[i].count++;
+    point_cnt = i + 1;
+
     G_debug(1, "%d vector points left after removal of duplicates", point_cnt);
 
     /* Report number of points not used */

-- 
Glynn Clements <glynn at gclements.plus.com>