Skip to content

fix a critical bug in the set_box_info method of BoxMap - #7

Merged
Sandarr95 merged 1 commit into
HU-R2D2:release-v1.0from
chieltbest:release-v1.0
May 20, 2016
Merged

fix a critical bug in the set_box_info method of BoxMap#7
Sandarr95 merged 1 commit into
HU-R2D2:release-v1.0from
chieltbest:release-v1.0

Conversation

@chieltbest

@chieltbest chieltbest commented May 10, 2016

Copy link
Copy Markdown
Contributor

This fix takes the time complexity of the algorithm down to O(n^2) from an estimated O(2^n).
Also did a lot op optimisations to the code, increasing performance by a large margin.
Some benchmarks follow:

  • In both the optimised and unoptimised versions
    of the code the fix has been applied.
  • All test were done on an AMD FX-6350 @ 4.5Ghz,
    with the same test case for both versions.
  • The code was built using the supplied cmake build,
    using the release build configuration.
Test size total insertions unoptimised optimised
50 10000 1610+-100ms 195+-10ms
100 40000 33.2+-.1s 3.21+-.5s
150 90000 199+-3s 19.3+-.1s

From these tests it can be concluded that:

  1. There is an average speedup of around 860%.
  2. The algorithm conforms reasonably well to the calculated O(n^2) complexity.

This fix takes the time complexity of the
 algorithm down to O(n^2) from an estimated O(2^n).
Also did a lot op optimisations to the code,
 increasing performance by a large margin.
Some benchmarks follow:
- In both the optimised and unoptimised versions
 of the code the fix has been applied.
- All test were done on an AMD FX-6350 @ 4.5Ghz,
 with the same test case for both versions.
- The code was built using the supplied cmake build,
 using the release build configuration.

Test size | total insertions | unoptimised | optimised
50        | 10000            | 1610+-100ms | 195+-10ms
100       | 40000            | 33.2+-.1s   | 3.21+-.5s
150       | 90000            | 199+-3s     | 19.3+-.1s

From these tests it can be concluded that
 there is an average speedup of around 860%.
It can also be observed that the algorithm conforms
 reasonably well to the calculated O(n^2) complexity.
@Sandarr95
Sandarr95 merged commit 68d1695 into HU-R2D2:release-v1.0 May 20, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants