4 ms·
It's easy to see that altering an entry in an array (size N) is O(1) with mutability and at least O(log N) with immutability, and that affects many algorithms.
by ghusbands 2y ago
It's easy to see that altering an entry in an array (size N) is O(1) with mutability and at least O(log N) with immutability, and that affects many algorithms. Altering any small part of a larger data structure has similar issues. In the end, many algorithms gain a factor of log N in their time complexity.
- kstrauser 2y agoRight, but look at the bigger picture. Immutability removes a whole lot of order of operations concerns. That frees a smart compiler to use faster algorithms, parallelization, etc. in ways that might not be safely possible if the data might change in place. Yes, that may mean it's slower to deal with individual values. It may also mean that the resulting system can be faster than otherwise.
- ghusbands 2y agoWell, language benchmarks fairly uniformly show that to be untrue in general. None of the fastest languages have forced immutability. It's not like it's a novel, untested idea.
- sunshowers 2y agoI... think that's mostly because compilers haven't yet optimized for that case yet.