Rotate Pointer implementation operating in a single pass

[three...@gmail.com]

Hi:

I am reading the book 'The Go Programming Language'.  I wrote a slice implementation inspired by  http://www.geeksforgeeks.org/array-rotation/ (method3) of rotate operating in a single pass.   I like c++ graceful Pointer implementation http://www.cplusplus.com/reference/algorithm/rotate/ too.  I tried to code "rotate" using Pointer in Go but failed.   I know that there is no pointer arithmetic. Therefore, I cannot code

ptr++ 

I cannot code the followings either (try to get around of pointer arithmetic)

mid, last := &ptr[d], &ptr[n]

The compiler gave me an error: invalid operation: ptr[d] (type *[]int does not support indexing).   I could write 'reverse' in both slice and pointer array.   However, I just cannot get  "rotate" using Pointer in Go to work.  Has anybody try that and get it working?  Or is it just impossible due to the limitation imposed by Go? 

Thanks.

[Roberto Zanotto]

Because of memory safety reasons, there is no pointer arithmetic in Go and pointers and arrays/slices are not the same thing,

as you can guess from the error you are getting.

If you can, use indices or slices on an array to emulate pointers.

Actually you can do pointer arithmetic if you really want, but you have to go through package unsafe.

I suggest the following reads:

https://golang.org/pkg/unsafe/

http://blog.golang.org/go-slices-usage-and-internals

[Roberto Zanotto]

I just looked at the third method on geeksforgeeks, they do it with indices, not with pointers.

You should be able to translate that in Go.

If you have troubles, post your code here.

On Tuesday, March 29, 2016 at 4:35:44 AM UTC+2, three...@gmail.com wrote:

[three...@gmail.com]

Roberto, Thanks for your help.  

Yes.  "I wrote a slice implementation inspired by  http://www.geeksforgeeks.org/array-rotation/ (method3) of rotate operating in a single pass."  It works perfectly without problem.   I just like to to see if I can also implement "rotate"  using Pointer in Go in one pass like C++ does.    I will take a look at those links given.

Sonya

[Roberto Zanotto]

Oh, sorry, I didn't get that.

To do pointer arithmetic you basically have to do this:
https://play.golang.org/p/K7Do6aUnlq

It is explained better in pkg/unsafe documentation.

Of course avoid unsafe in production.

[Roberto Zanotto]

In alternative you can use slices as pointers:

https://play.golang.org/p/GTwb_CcK_p
That option is pretty much explained in the blog post about slices.

A limitation is that with slicing you can advance the "pointer" but you can't decrease it.

[Roberto Zanotto]

You made me curious about the thing, so I translated the C++ code in Go (the Go program uses indices, it's just the cleanest solution)

It's here if you want to spoil yourself the solution :)
https://play.golang.org/p/hktEoaaJxC

It's definitely the best algorithm among the ones you linked, very few lines of code, O(n) time, O(1) extra memory.

On Wednesday, March 30, 2016 at 12:12:18 AM UTC+2, three...@gmail.com wrote:

[Michael Jones]

Strongly suggest using Ken Thompson’s scheme. O(n) time, NO extra memory, simple. Brilliant!

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Michael Jones]

Busy here. Had to go look for my code for the “method of the hands” so here you are. If you care I can upload the test suite and benchmarks to my github account.

// swap partitions using the beautiful "method of the hands"
func SwapMH(a []int, count int) {
if a != nil && 0 < count && count < len(a) {
reverse(a[:count]) // reverse the left partition
reverse(a[count:]) // reverse the right partition
reverse(a)         // reverse the whole array
}
}

func reverse(a []int) {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
}

The name Swap means “swap the first N elements with the last length()-N elements” but calling it “rotate the list by N” is the same meaning.

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

[Matt Harden]

I don't think that could be considered "in a single pass" unfortunately. I think the first two reverses could be considered one pass, but the third reverse surely counts as a second pass.

If you define "one pass" as reading from each element exactly once, and writing to each element exactly once, then this one will fit the bill. It uses the fact from group theory that any permutation can be factored into one or more disjoint cycles, a cycle being essentially a single shift of a subset of the elements. So rotating [a b c d e f] by two = (a c e) (b d f), for example. This requires exactly one variable for temporary storage.

https://play.golang.org/p/hxiKJ3U-4x

[three...@gmail.com]

Thanks everybody.  Here are two one-pass solutions I come up with (I haven't read Reberto's spoil link yet).  Don't mess up your brain with pointer.  Think in terms of index.  Here is the first one

/**
Please references
http://www.cplusplus.com/reference/algorithm/rotate/
Time complexity: O(n)
*/
func rotateIndexAdv(s []int, d int) {
       n := len(s)
       //mid points to the beginning of the right side of swapping, first, next are moving pointer(index) to where the next targets of both sides
       first, next, mid := 0, d, d
       for first != next {
              s[first], s[next] = s[next], s[first]
              first++; next++
              if next == n {
                     next = mid //back to the beginning of mide
              } else if first == mid {
                     mid = next //moving mid point to another set
              }
       }
}

The one I came up with before my first post is the following:

/**
Please Reference.
       http://www.geeksforgeeks.org/array-rotation/
       http://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast, the second post
Time complexity: O(n)
Auxillary space O(1)
 */
func rotateArrayAdv(s []int, d int) {
       n := len(s)
       var j, k int
       for i := 0; i < gcd(n, d); i++ {
              temp := s[i]
              j = i
              for {
                     k = j + d
                     //It treats thw whole series as circular, a,b,c,d,e,f,g (a,b,c)
                     if k >= n {
                            k -= n
                     }
                     if k == i {
                            break
                     }
                     s[j] = s[k]
                     j = k
              }
              s[j] = temp
       }
}

The first one is nice & compact but not easy to understand. simulating using an example like rotate({1,2,3,4,5,6,7}, 3) would help.  The second one is an amazing one.  If the gcd = 1, the program would touch every index of the slice but never repeat.(It will finish a cycle)  That is based upon modular arithmetic.  

[Roberto Zanotto]

The first one is similar to my code, as it comes from the same C++ code.

As you said, it's a bit tricky to understand.

The second is nice, but calculating the gcd for rotating an array is unnecessary.

I would go with the solution Michael proposed, it's linear time, simple and easy to understand.

You might want to do something like

count = (count%len(a) + len(a)) % len(a)

so that the algorithm works also when the rotation counter is negative or bigger than the length of the array.

[Michael Jones]

I understand now that this was a “how to code cleverly” question. One pass is quite clever. 

However, two passes (MH) is simpler and requires half the time.

I hope they don’t teach slow tricks in school!

Compiled Normally

BenchmarkRotateEZ10-8            10000000       188 ns/op

BenchmarkRotateEZ100-8              10000     101978 ns/op

BenchmarkRotateEZ1000-8                30   48516706 ns/op

{skipped BenchmarkRotateEZ1000}

BenchmarkRotateFM10-8            10000000       152 ns/op

BenchmarkRotateFM100-8             200000     10355 ns/op

BenchmarkRotateFM1000-8              2000     862210 ns/op

BenchmarkRotateFM10000-8               20   79812929 ns/op

BenchmarkRotateMH10-8            10000000       151 ns/op

BenchmarkRotateMH100-8             200000     10083 ns/op

BenchmarkRotateMH1000-8              2000     805174 ns/op

BenchmarkRotateMH10000-8               20   77660177 ns/op

BenchmarkRotateIndexAdv10-8      10000000       135 ns/op

BenchmarkRotateIndexAdv100-8       100000     21417 ns/op

BenchmarkRotateIndexAdv1000-8        1000   1918245 ns/op

BenchmarkRotateIndexAdv10000-8         10 181083936 ns/op

BenchmarkRotateArrayAdv10-8       3000000       559 ns/op

BenchmarkRotateArrayAdv100-8        50000     26239 ns/op

BenchmarkRotateArrayAdv1000-8        1000   1455696 ns/op

BenchmarkRotateArrayAdv10000-8         10 143630423 ns/op

BenchmarkRotateRZ10-8            10000000       137 ns/op

BenchmarkRotateRZ100-8             100000     20531 ns/op

BenchmarkRotateRZ1000-8              1000   1717377 ns/op

BenchmarkRotateRZ10000-8               10 169011382 ns/op

Compiled with bounds checking disabled:

BenchmarkRotateMH10-8            10000000       134 ns/op

BenchmarkRotateMH100-8             200000       8442 ns/op

BenchmarkRotateMH1000-8              2000     643056 ns/op

BenchmarkRotateMH10000-8               20   63050965 ns/op

For these types of array indexing computations, the redundant bounds checks are expensive.

BenchmarkRotateMH10-8             134 ns/op 

BenchmarkRotateMH100-8           8442 ns/op ==> -16.27%

BenchmarkRotateMH1000-8            643056 ns/op ==> -20.13%

BenchmarkRotateMH10000-8         63050965 ns/op ==> -18.81%

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

[Roberto Zanotto]

The "one pass" thing is misleading:

the one pass algorithm does n swaps, the two passes algorithm still does n swaps, as reversing an array takes n/2 swaps.

Also, reversing is probably more cache friendly.

The algorithm based on reverse is just plain better.

[Michael Jones]

Credit to Ken Thompson. Apparently that’s how he did it in ‘ed'

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

[Matt Harden]

So I'm not arguing which is faster; I don't doubt that reversing is more performant on modern CPUs. I also agree that a "cleverer" (read: more complex in terms of human understanding) algorithm that's demonstrably slower and doesn't reduce some other resource use like memory or locking is a worse algorithm. Nevertheless, I must take issue with one thing Roberto said. The "one pass" algorithm that uses cyclic permutations does not perform n swaps. If you consider a swap to be 2 reads followed by 2 writes, as in reversing an array, then the one pass algorithm also requires n/2 swaps, just like reversing an array just one time. It's exactly one read and one write of each element of the array, which is obviously the minimum possible.

[Roberto Zanotto]

I guess you are right. I was talking about the algorithm taken from C++ doing n swaps. I didn't take the time to analyze the one with the gcd.

[three...@gmail.com]

I need some clarification.   The book has already given the rotate method using three reverse.  The exercise require us to come up with one-pass solution.   Therefore, it is alternative thinking exercise.   There is also another simple and understandable method. I call it rotateCopyRestore which use temporary storage.  I don't consider it as one-pass solution either.

I agrees with Matt's correction on swap time complexity analysis.  However,  I presented two one-pass methods.  I don't know which one people consider as cyclic permutations. However, rotateArrayAdv does not involve any swap, It just keep moving value from d * (i+1) % n to d * i % n.

I am learning the impact of algorithm methods on performance.   Michael, can you explain further regarding to "For these types of array indexing computations, the redundant bounds checks are expensive." 

On Wednesday, March 30, 2016 at 8:21:57 PM UTC-7, Roberto Zanotto wrote:

I guess you are right. I was talking about the algorithm taken from C++ doing n swaps. I didn't take the time to analyze the one with the gcd.

On Thursday, March 31, 2016 at 5:13:37 AM UTC+2, Matt Harden wrote:

So I'm not arguing which is faster; I don't doubt that reversing is more performant on modern CPUs. I also agree that a "cleverer" (read: more complex in terms of human understanding) algorithm that's demonstrably slower and doesn't reduce some other resource use like memory or locking is a worse algorithm. Nevertheless, I must take issue with one thing Roberto said. The "one pass" algorithm that uses cyclic 

BenchmarkRotateEZ10-8             10000000        188 ns/op

BenchmarkRotateEZ100-8               10000     101978 ns/op

BenchmarkRotateEZ1000-8                 30   48516706 ns/op

{skipped BenchmarkRotateEZ1000}

BenchmarkRotateFM10-8             10000000        152 ns/op

BenchmarkRotateFM100-8              200000      10355 ns/op

BenchmarkRotateFM1000-8               2000     862210 ns/op

BenchmarkRotateFM10000-8                20   79812929 ns/op

BenchmarkRotateMH10-8             10000000        151 ns/op

BenchmarkRotateMH100-8              200000      10083 ns/op

BenchmarkRotateMH1000-8               2000     805174 ns/op

BenchmarkRotateMH10000-8                20   77660177 ns/oppermutations does not perform n swaps. If you consider a swap to be 2 reads followed by 2 writes, as in reversing an array, then the one pass algorithm also requires n/2 swaps, just like reversing an array just one time. It's exactly one read and one write of each element of the array, which is obviously the minimum possible.

On Wed, Mar 30, 2016 at 7:08 PM Michael Jones <m...@wearality.com> wrote:

Credit to Ken Thompson. Apparently that’s how he did it in ‘ed'

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

On Mar 30, 2016, at 6:20 PM, Roberto Zanotto <roby...@gmail.com> wrote:

The "one pass" thing is misleading:

the one pass algorithm does n swaps, the two passes algorithm still does n swaps, as reversing an array takes n/2 swaps.

Also, reversing is probably more cache friendly.

The algorithm based on reverse is just plain better.

On Thursday, March 31, 2016 at 2:38:26 AM UTC+2, Michael Jones wrote:

I understand now that this was a “how to code cleverly” question. One pass is quite clever. 

However, two passes (MH) is simpler and requires half the time.

I hope they don’t teach slow tricks in school!

Compiled Normally

...

[Roberto Zanotto]

The two "one pass" methods you presented are the one from C++ and the other with gcd (or cyclic permutations).

I was noting that the C++ method, despite being single pass, actually does the same number of swaps of the method based on reverse.

...