Some things are inherently complicated and slow ... put them in the right place
One of the first lessons I learned when I started working as a software developer professionally was that you don't always have to make an action fast, sometimes its just enough to make it seem fast to a user. This lesson was learned in the 1990s in the context of a Windows application. What we did was quickly draw part of the screen (or a splash image) immediately then do the time consuming work in the background so that by the time the user was ready to interact with the application we'd be ready for them.
Recently I was reminded of this lesson on a website I'm working on. We have a complicated report to show on the user's homepage. My first implementation involved generating the report in real-time when the page is loaded but this was very slooooow. Some profiling and analysis let us make it somewhat faster but not fast enough.
I was stumped until I remembered my old lesson. If it wasn't possible to generate the report quickly, perhaps we could do it sometime when the user wouldn't mind.
Luckily this is a Rails application and ActiveRecord Callbacks make it easy to do this. I could pregenerate the report and update a portion of it each time something is saved. Users expect a save to take some time and don't do it that often. Then generating the homepage becomes just a simple matter of displaying the existing rows.
First I setup my models to call into the report generator every time they change
Then I implement the complicated (and slow) logic to pre-compute the rows in the report in a library class
Finally I can show the report on the homepage with some boring (and fast) Rails code
and the View:
The interesting insight for me is that when optimizing there are sometimes hard problems that can't be solved. Its important not to lose sight of the goal you're aiming at (a satisfying user experience) and that sometimes involves spending the computational time somewhere where the user won't mind.