4 ms·
I think this was discussed in Jon Bentley "programming pearls"? Also in the same book it was mentioned that the disjoint cycles method (also mentioned in the a
by praptak 9mo ago
I think this was discussed in Jon Bentley "programming pearls"?
Also in the same book it was mentioned that the disjoint cycles method (also mentioned in the article) was worse for paging/caching than the three reverses method.
- ot 9mo agoThat's probably true for small primitive types, but if your objects are expensive to move (like a large struct) it might be beneficial to minimize swaps.
- praptak 9mo agoYeah, it might be interesting to run some profiling of both algorithms and see how they perform dependent on the size of the blocks being swapped (which doesn't even have to be equal to the size of the object in the array).
- taeric 9mo agoIt is discussed in that book. Very fun read, all told. Highly recommended if folks find this sort of thing fun. I think I should thumb through it again. :D
- jnellis 9mo agoJava chooses to use the cycle method mostly. They also reference Bentley. https://github.com/openjdk/jdk/blob/f1e0e0c25ec62a543b9cbfabd630fc4ef17a8b5c/src/java.base/share/classes/java/util/Collections.java#L782 https://github.com/openjdk/jdk/blob/f1e0e0c25ec62a543b9cbfab...