itsbonczek/kingpin — pull request #22 by stanislaw (2014-03-10 09:04:16+00:00)
Title: Temporary storage

This pull request depends on my previous pull request #21: "Tree building algorithm without duplication" and should be merged after it.

This changes address and fulfil the second of my promises about memory allocations:

> 1) I want eliminate these two large similar sections of buildTree() by writing a one instead, but the one without "X or Y" branching.

> 2) I want to reduce a number of malloc-allocations of temporary arrays even further to make a process of building of a tree a bit more faster.

> 3) Work on _mergeOverlappingClusters to back out of all these convertCoordinate and CGRect-based calculations. Strong knowledge of zooms and zoom scales described here: http://troybrant.net/blog/2010/01/mkmapview-and-zoom-levels-a-visual-guide/ promises to be extremely helpful to this issue - I just need to understand it better than I currently do. If I succeed on this, you will never need to make this step optional at all by disabling it by configuration flag - it might become unnoticeable when written efficiently. Hopefully, I will come up with this.

----

Having this pull request on top of kingpin - I now have 64ms as a lower bound of my performance results, when building tree on iPhone, which means kingpin is now 14-15x faster than original one (my first tests for 20000 were aroung 900-1000ms).

----

This is the point when I'm going to stop improving the tree building code of kinpin. The next step for me is to try to work out the `mergeOverlappingClusters` method to make it produce better results, i.e. now I am going to hack on clustering algorithm itself.