CubeTime icon indicating copy to clipboard operation
CubeTime copied to clipboard

improve best and current aoX calculations

Open pdtxie opened this issue 2 years ago • 2 comments

pdtxie avatar Feb 26 '23 10:02 pdtxie

changed $O(m \cdot n \cdot logm)$ naive implementation to $O(n \cdot logm)$ with multimap, and written in c++ testing shows ~100x better performance at session of ~30k:

execution time with 30k elements:

alg time
swift old alg 3.582392398 seconds
swift new alg 0.368188858 seconds
c++ new alg (same implementation) 0.02997591 seconds

(9f46f1b3a0d04acec07920c00c59edc58d451a10)

pdtxie avatar Feb 26 '23 10:02 pdtxie

Re-opening, still one optimization: currently mapping the Solve objects to times... if we update the code to obj-c++ and access a passed solves array directly it may be faster (?)

xbjfk avatar Feb 26 '23 21:02 xbjfk