search

mikemcbride / vue-sudoku

Sudoku solver written in Javascript
https://sudoku.mcbrides.us
MIT License
5 stars 1 forks source link

Faster array methods #12

Closed mikemcbride closed 4 years ago

mikemcbride commented 4 years ago

This adds some more optimizations around the array methods. I did a few things:

  1. Used @arr utils for faster array methods
  2. Refactored some method calls that were getting heavy traffic to be more optimal (lots of work on getRelatedCells)
  3. Abstracted some code that was repeated multiple places into reusable methods
  4. Found some minor optimizations along the way during these refactors

Nothing mind-blowing here, but generally it's faster. Oddly enough, some puzzles take more calculations to complete than they previously did, but they still get solved faster. Not really sure what to make of that? It's kind of arbitrary anyway.

vercel[bot] commented 4 years ago

This pull request is being automatically deployed with ZEIT Now (learn more). To see the status of your deployment, click below or on the icon next to each commit.

🔍 Inspect: https://zeit.co/mcbridem/vue-sudoku/dkkbed04o ✅ Preview: https://vue-sudoku-git-faster-array-methods.mcbridem.now.sh

mikemcbride commented 4 years ago

I was able to add in some more optimizations around the array utilities. I added in a property to the cells for "related cells" which made it significantly easier to fetch all related cells. I removed a handful of class methods because of this and refactored a couple of others to be significantly more simple.

Then I wanted to try something out just to see what happened. Right now we're doing this thing where we wrap each iteration in a sleep for 0ms to trigger the UI re-rendering so it can show what the computer is doing. It looks neat. I wanted to see what happened if we removed this and just ran it synchronously. The results were pretty staggering. Every puzzle finishes in half the time or less than what it initially did, and in some cases, especially with difficult puzzles, it's even more drastic. So I thought, why not throw in a spinner to indicate progress, then remove it when we're done?

I did that, but the puzzle solving blocks the main thread so our spinner didn't render. I decided to try and execute the puzzle solving in a web worker to get it off the main thread. That worked out beautifully, so now we lose the gimmicky "look at my puzzle being solved" but we add a nice looking loader and the puzzles all solve significantly faster.

Comparison operations and solve time before and after this PR. I ran the puzzle that takes this algorithm the longest to solve (in the app, it's puzzle number 8)

before after
total calculations 201283 199469
solve time 7.422s 1.544s

Pretty pleased with these results so far.