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.
As a commenter noted as well, you can perform the swap using two std::rotate calls vs. three (less than 2N operations). This said, Raymond’s use of reverse is still most efficient at N operations (not considering paging/caching issues).
There's something about this that's unsatisfying to me. Like it's just a trivia trick.
My first read of this was "this seems impossible." You're asked to move bits around without any working space, because you're not allowed to allocate memory. I guess you could interpret this pedantically in C/C++ land and decide that they mean no additional usage of the heap, so there's other places (registers, stack, etc.) to store bits. The title is "in constant memory" so I guess I'm allowed some constant memory, which is vaguely at odds with "can you do this without allocating additional memory?" in the text.
But even with that constraint ... std::rotate allocates memory! It'll throw std::bad_alloc when it can't. It's not using it for the core algorithm (... which only puts values on the heap ... which I guess is not memory ...), but that function can 100% allocate new memory in the right conditions.
It's cool you can do this simply with a couple rotates, but it feels like a party trick.
The problem seems less arbitrary if the chunks being rotated are large enough. Implicit in the problem is that any method that would require additional memory to be allocated would probably require memory proportional to the sizes of stuff being swapped. That could be unmanageable.
As for whether std::rotate() uses allocations, I can't say without looking. But I know it could be implemented without allocations. Maybe it's optimal in practice to use extra space. I don't think a method involving reversal of items is generally going to be the fastest. It might be the only practical one in some cases or else better for other reasons.
11 comments
[ 3.0 ms ] story [ 32.0 ms ] threadAlso 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.
As a side note, love how Raymond handled that, no fluff and straight to the point. Beginners mind and all that.
My first read of this was "this seems impossible." You're asked to move bits around without any working space, because you're not allowed to allocate memory. I guess you could interpret this pedantically in C/C++ land and decide that they mean no additional usage of the heap, so there's other places (registers, stack, etc.) to store bits. The title is "in constant memory" so I guess I'm allowed some constant memory, which is vaguely at odds with "can you do this without allocating additional memory?" in the text.
But even with that constraint ... std::rotate allocates memory! It'll throw std::bad_alloc when it can't. It's not using it for the core algorithm (... which only puts values on the heap ... which I guess is not memory ...), but that function can 100% allocate new memory in the right conditions.
It's cool you can do this simply with a couple rotates, but it feels like a party trick.
As for whether std::rotate() uses allocations, I can't say without looking. But I know it could be implemented without allocations. Maybe it's optimal in practice to use extra space. I don't think a method involving reversal of items is generally going to be the fastest. It might be the only practical one in some cases or else better for other reasons.
A B C D E
A C B D E -- after rotate B, C
A D C B E -- after rotate C-B, D
Complexity would seem to be the same as the reverse method, since every element in the original B-D range is getting moved twice.
Anyways, here is what google search AI gave me as an example of how that would work (I don't know this stuff well enough myself):
; Assume ymm0 contains [A, B, C, D] (Q0=A, Q1=B, Q2=C, Q3=D)
; The immediate 0xd8 (11011000 in binary) means:
; - Keep Q0 (index 0)
; - Swap Q1 (index 1) with Q2 (index 2) (110, 011 in binary for bits 1,2)
; - Keep Q3 (index 3)
vpermq ymm0, ymm0, 0xd8
; ymm0 now contains [A, C, B, D]