How to refactor a O(n^3) problem

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

withinboredom
Posts: 9
Joined: Mon Sep 15, 2014 4:29 pm UTC

How to refactor a O(n^3) problem

Postby withinboredom » Mon Sep 15, 2014 5:12 pm UTC

Obviously, context is needed to answer the question (but this isn't stack overflow), I'm more or less looking for a strategic approach...

O(n^3) - structure of the code

Code: Select all

foreach(allThese as oneThese) {
  calculateThings(oneThese.stuff);
  foreach(oneThese.allThem as oneThem) {
    do {
      someWork(oneThem.stuff, oneThem.counter);
      oneThem.counter ++;
    } while(oneThem.counter < oneThem.units)
  }
}

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: How to refactor a O(n^3) problem

Postby korona » Wed Sep 17, 2014 8:45 pm UTC

There is no recipe for this. You could try things like:
  • Don't calculate results for all things
  • Precompute some intermediate values
  • Use a different algorithm that is not O(n^3) (yeah, this is very helpful, I know)
  • Optimize (e.g. use different data structures or improve cache locality) the code so that O(n^3) is fast enough
But to really answer the question we need more context. It is also worth noting that sometimes there just isn't a better way than the obvious one.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: How to refactor a O(n^3) problem

Postby Qaanol » Wed Sep 17, 2014 11:59 pm UTC

If the calculations are linear, then you can use fast matrix multiplication such as Strassen’s algorithm. But unless n is at least several thousand, it won’t provide much if any benefit on a modern computer.
wee free kings

heatsink
Posts: 86
Joined: Fri Jun 30, 2006 8:58 am UTC

Re: How to refactor a O(n^3) problem

Postby heatsink » Thu Sep 18, 2014 2:26 pm UTC

One way of reducing asymptotic complexity is by taking advantage of algebraic properties of the problem you're solving. For example:

  • Given a collection of floating-point numbers, how do you find the one whose value is closest to a given number X? If you're doing many lookups on the same collection, then sorting the collection helps. Sorting exploits the ordering of reals: if X > Y and Y > Z, then we know that Y is a better match than Z, without even comparing X to Z. Binary search exploits this property to find a match in O(log(N)) time instead of O(N).
  • How do you compute N to the fourth power, for large integer N? You can multiply three times: N * N * N * N. Because multiplication is associative, you can refactor this as (N * N) * (N * N). This takes only two multiplications: compute (N * N) once, then multiply by itself. Binary exponentiation generalizes this reassociation technique to arbitrary powers.

The algebraic properties in these cases are ordering and associativity. These examples involve numeric properties, but the approach isn't limited to numbers. Anyway, I think that just hunting for properties you can use is helpful when you're working on a piece of code, even if you end up taking a solution from korona's list.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests