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.

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.

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.

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.

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