Re: [OT] Swapping buffers in place.

Do you know a priori when the second half is shorter than the first? The obvious thing to me is to have a third buffer equal in size to the difference between the two where you store the part that you're about to overwrite.

The clever way that struck me while trying to get around that is to reverse the whole thing, then reverse each of the sub-buffers. It takes more time but it does it in place.

edit: other than the triple reverse, I can't do it in place (i.e. without a third buffer equal to the difference) without putting in a bunch of rotations to get the ends of the longer buffer in the right place:

first, swap the ends of the longer one so you won't overwrite the trailing elements of the long one:

[X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7]
[download]

becomes

[X8 X9 X2 X3 X4 X5 X6 X7 X0 X1 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7]

then to a straight swap

[Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X8 X9 X2 X3 X4 X5 X6 X7]

then you're stuck rotating the trailing elements of the longer one back into place

[Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X9 X2 X3 X4 X5 X6 X7 X8]
[Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X2 X3 X4 X5 X6 X7 X8 X9]
[download]

which I think usually takes more time than the triple reverse (which really is only two passes through the whole thing).

Comment on Re: [OT] Swapping buffers in place. Select or Download Code

Replies are listed 'Best First'.

Re^2: [OT] Swapping buffers in place.
by BrowserUk (Patriarch) on Mar 01, 2015 at 06:42 UTC

I can do it with just one temp and n+m+(m-n) swaps (on paper):

 0 1 2 3 4 5 6 7 8 
[a b c d e f 1 2 3] temp
      [d]>>>>>>>>>>>[d]             temp = *(p1+p1len+1)     // want t
+o move [0]->[3] so put [3]->temp  (1)
[a]>>>[d]                        *(p1+p1len+1) = *(p1+0)     // [0]->[
+3]                                (2)
[e]<<<<<[e]                      *(p1+0) = *(p1+p1len+2)     // want t
+o move [1]->[4] so put [4]->[0]   (3)
  [b]>>>[b]                      *(p1+p1len+2) = *(p1+1)     // [1]->[
+4]                                (4)
  [f]<<<<<[f]                    *(p1+1) = *(p1+p1len+3)     // want t
+o move [2]->[5] so put [5]->[1]   (5)
    [c]>>>[c]                    *(p1+p1len+3) = *(p1+2)     // [2]->[
+5] leaving [2] free so            (6)
    [3]<<<<<<<<<[3]              *(p1+2) = *(p2+p2len-1)     // [2]<-[
+8] leaving [8] free so            (7)
  [f]>>>>>>>>>>>[f]              *(p2+p2len-1) = *(p1+1)     // [1]->[
+8] leaving [1] free so            (8)
  [2]<<<<<<<<<[2]                *(p1+1) = *(p2+p2len-2)     // [1]<-[
+7] leaving [7] free so            (9)
[e]>>>>>>>>>>>[e]                *(p2+p2len-2) = *(p1+0)     // [0]->[
+7] leaving [0] free so           (10)
[1]<<<<<<<<<[1]                  *(p1+0) = *(p2+p2len-3)     // [0]<-[
+6] which leaves [6] free         (11)
            [d]<<<<<[d]          *(p2+p2len-3) = temp;       // for th
+e value in temp                  (12)
[1 2 3 a b c d e f]                                            m=6, n=
+3, moves= 6+3+(6-3) = 12
[download]

But I'm damned if I can see any pattern to the increments & decrements or steps; to capture that for a generic M+N?

the triple reverse (which really is only two passes through the whole thing).

That's really quite brilliant, I'd never have thought of that :), and it will certainly be what O shall fall back to if I can't get this working.

But as the left buffers are going to be 2GB or 4GB or 8GB or 16GB or 32GB (depending on physical memory in the machine)

and the right buffer could be anything from 16 bytes up to the (leftBufferSize)-16 (ie. whatever is left in the dataset modulus the leftBufferSize)

you can see why I'd rather avoid (M+N)*2 if I can get M+N+(M-N). (And also why a 3 buffer is impractical.)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

[reply]
[d/l]


go ahead... be a heretic
	PerlMonks