[GRASS-dev] Re: [GRASS-user] v.what.rast (large file)

[Glynn Clements]

Massimo Di Stefano wrote:

> i've a large  point vector file (ascii 160 mb)

> can i divide my area in many subregion
> and then patch the results ?

The categories are modified in-place, so you can just run the command
on each subregion; there's no need to "patch" anything.

AFAICT, the problem is in the code which deletes duplicate categories:

    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++;
    }

This is O(n^2), but thiscould be done in O(n). The problem is that
it's shifting the remainder of the array down by one place at each
step, when it could move each entry to its final destination in one
go. E.g. (untested):

    i = j = 1;
    while ( i < point_cnt ) {
        while ( i < point_cnt && cache[i].cat == cache[j-1].cat ) {
            cache[j-1].count++;
            i++;
        }
        cache[j].row   = cache[i].row; 
        cache[j].col   = cache[i].col; 
        cache[j].cat   = cache[i].cat; 
        cache[j].count = cache[i].count; 
        i++;
        j++;
    }
    point_cnt = j;

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