4 ms·

100x faster means improving the coefficients. A* is optimal in terms of asymptotic execution time, but that doesn't mean you can't improve the overall running t

• semi-extrinsic 10y ago
  The classic example is matrix multiplication, where we know of incresingly sophisticated algorithms with increasingly better asymptotic performance, but in practice most matrix multiplications are for sub-100x100 (IIRC) matrices where the naive algorithm we all learned as undergrads is fastest.
  • derefr 10y ago
    > in practice most matrix multiplications are for sub-100x100 (IIRC) matrices I would say that you have the causation reversed: we just don't bother doing large matrix multiplications, because they're so expensive (and yet still don't usually cross the intercepts into making the "better" algorithms worth it, due to those algorithms having ridiculous constant coefficients.) I would love to run Floyd-Warshall on my 40-million point network graph—but it just ain't gonna happen.
    • semi-extrinsic 10y ago
      > we just don't bother doing large matrix multiplications, because they're so expensive Sure, I agree. I'm not a specialist in numerical lin.alg., but I've heard it said that if you're spending a lot of time on large dense matrix multiplications, you're probably approaching the problem in the wrong way.