top | item 24772192

(no title)

rladd | 5 years ago

We can easily reduce this to effectively time=0 which is an infinite speedup.

Since the membership of any of the local cells in the global cells is static, we only have to compute this once. Then we add a globalCell parameter to each local cell to specify which global cell it's contained in.

If this uses up too much memory, we could go to a slower but still much, much faster than the blog post's method of something like:

- Create 2d array where the 1st dimension is a sorted list of local row values, one per global row value, that represent the maximum X value within any global cell. Then the the 2nd dimension are local column values, one per global column value that similarly correspond to the maximum Y value of any local cell per global cell. (mapping the coordinates to an array)

- Find the entry that the current local row value fits into (for example the entry with a value higher than the local row value, which is higher than the next list entry).

- This selects a second dimension array for that global row that has similar properties: it's only necessary to then find which value the local row fits into to determine the global cell (which would be the array's value at that index).

discuss

order

No comments yet.