Re:The true cost of linked lists
by hinkley on Monday June 06, 2022 @09:29PM
(#31648783)
But it still falls down so quickly that the smart money is on actually paying attention to the Devil (the details).
In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2.
Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.
In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2.
Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.