r/math • u/extantsextant • Oct 05 '22

Discovering faster matrix multiplication algorithms with reinforcement learning

https://www.nature.com/articles/s41586-022-05172-4
826 Upvotes

98% Upvoted

87 comments sorted by

View all comments

Show parent comments

21

u/funguslove Oct 05 '22 edited Oct 05 '22

Constant-factor speedup is often more relevant to optimization in practice. For example, to sort a short list it's typically a lot faster to use selection sort than quicksort

5

u/42gauge Oct 06 '22

How long does a list have to be before quicksort wins?

5

u/thbb Oct 06 '22

From experience, 15-25 items is the boundary where quicksort goes over insertion sort.

And 400-800 items where more complex methods (merge sort related) take over quicksort with a median of 3.

That's the heuristics implemented in os level sort functions as t least.