Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Avoid array insertion in iterative refinement #115

Closed
schillic opened this issue Jan 6, 2018 · 0 comments
Closed

Avoid array insertion in iterative refinement #115

schillic opened this issue Jan 6, 2018 · 0 comments
Assignees
Labels
performance 🐎 More efficient code

Comments

@schillic
Copy link
Member

schillic commented Jan 6, 2018

In the "iterative refinement" of polygons we use array insert!, which is not efficient (in practice it might be okay because we start at the front and walk to the end).
An efficient alternative is to have two arrays, one for finished refinements and one for unfinished ones:

initialize with box direction approximations
[] [a b c d]
turn around initial array
[] [d c b a]
# actually just initialize in opposite order, but for clarity this is described in this way
pick a
[] [d c b]
refine a to (d, e)
add them in the opposite order
[] [d c b e d]
pick d
assume it is not refinable, so add it to the left
[d] [d c b e]
pick e
[d] [d c b]
assume it is not refinable, so add it to the left
[d e] [d c b]
...
@schillic schillic added the performance 🐎 More efficient code label Jan 6, 2018
@schillic schillic self-assigned this Oct 26, 2018
schillic added a commit that referenced this issue Nov 2, 2018
#115 - Avoid array insertion in iterative refinement
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance 🐎 More efficient code
Projects
None yet
Development

No branches or pull requests

1 participant