[GRASS-dev] New r3.stats version

Hi folks,
i have implemented a new version of r3.stats.
This version uses a tree based search algorithm to
calculate the range table. This approach is much faster
then the linear range search i had implemented bevor.
Now the complexity should be O(n log(n)) and not O(n^2).

The limit of 100000 range table entries is now obsolet
and was removed. :slight_smile:

Futhermore i have replaced the heapsort code with the GPL implementation used in r3.univar.

The latest code is available here:
http://www-pool.math.tu-berlin.de/~soeren/grass/modules/r3.stats.tar.bz2

I have compared the results of r3.stats which r.stats. And as i said befor, there is a ugly bug in the range table calculation of r.stats
which im not able to solve. Does anybody know if this bug is also present in the kergis code?
AFAICT r3.stats calculates the right results.

The next step will be a replacement of the equal value group search
algorithm, which needs to read the whole raster3d map into the memory.
I think using a linked list would be much faster and less memory consuming.

Any suggestions are welcome!

Best regards
Soeren

Hi folks,
breaking news. :wink:

I have rewritten the equal value group calculation algorithm.
Now a "linked list" is used to search equal value groups.
The memory consumption depends now on the number of equal values.
The raster3d map will not copied into the memory anymore.

To sort the "linked list", a modified heapsort algorithm was implemented.

The latest code is available here:
http://www-pool.math.tu-berlin.de/~soeren/grass/modules/r3.stats.tar.bz2

Sören Gebbert schrieb:

Hi folks,
i have implemented a new version of r3.stats.
This version uses a tree based search algorithm to
calculate the range table. This approach is much faster
then the linear range search i had implemented bevor.
Now the complexity should be O(n log(n)) and not O(n^2).

The limit of 100000 range table entries is now obsolet
and was removed. :slight_smile:

Futhermore i have replaced the heapsort code with the GPL implementation used in r3.univar.

The latest code is available here:
http://www-pool.math.tu-berlin.de/~soeren/grass/modules/r3.stats.tar.bz2

I have compared the results of r3.stats which r.stats. And as i said befor, there is a ugly bug in the range table calculation of r.stats
which im not able to solve. Does anybody know if this bug is also present in the kergis code?
AFAICT r3.stats calculates the right results.

The next step will be a replacement of the equal value group search
algorithm, which needs to read the whole raster3d map into the memory.
I think using a linked list would be much faster and less memory consuming.

Done. :slight_smile:

Best regards
Soeren

Any suggestions are welcome!

Best regards
Soeren

_______________________________________________
grass-dev mailing list
grass-dev@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass-dev