向量旋转

向量旋转

题目均来自《编程珠玑》。

将一个n元一维向量向左旋转(循环移位)i个位置。例如,当n=8时且i=3时,向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。能否仅用数十个额外直接的存储空间,在正比于n的时间内完成向量的旋转?

旋转操作对应于交换相邻的不同大小的内存块:每当拖动文件中的一块文件到其他地方时,就要求程序交换两块内存中的内容。

两个简单直接的方法

方法一:首先将 x 的前 i 个元素复制到一个临时数组中,然后将余下的 n-i 个元素向左移动 i 个位置,最好将最初的 i 个元素从临时数组中复制到 x 中余下的位置。这种办法使用 i 个额外的位置产生了过大的存储空间的消耗。

方法二:定义一个函数将 i 向左旋转一个位置(其时间正比于 n),然后调用该函数 i 次。该方法产生了过多的运行时间消耗。

下面介绍三种更好的方法。

跳跃交换实现

这个算法的思路就是:向量旋转后,vec[i]存储的将是vec[2i]的值,vec[2i]存储的是vec[3i]的值,如此类推。

要注意的就是,如果 n % i != 0,那么,要移动的部分超出 n%i 的长部分位于 i - n%i 的后面,本来应该在前的,所以又需要对这一部分进行旋转。

实现


func VectorRotateByMagic(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    length := len(vec)
    for i := 0; i < n; i++ {
        v, j := vec[i], i+n
        for ; j < length; j += n {
            vec[j-n] = vec[j]
        }
        vec[j-n] = v
    }

    mod := length % n
    if mod != 0 {
        VectorRotateByMagic(vec[length-n:], n-mod)
    }
}

func checkParam(vec []byte, n int) (bool, int) {
    length := len(vec)
    if length < 2 {
        return false, n
    }

    if n < 0 {
        n = -1 * n
        n = n % length
        n = length - n
    } else {

        n = n % length
    }

    if n == 0 {
        return false, n
    }

    return true, n
}

用求逆实现

下面这张图足以说明这个算法的思路来了:
vector-rotate-by-reverse

实现


func VectorRotateWithReverse(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    util.Reverse(vec[0:n])
    util.Reverse(vec[n:])
    util.Reverse(vec)
}

// util.Reverse
func Reverse(arr []byte) {
    var b byte
    for l, r := 0, len(arr)-1; l < r; l, r = l+1, r-1 {
        b = arr[l]
        arr[l] = arr[r]
        arr[r] = b
    }
}

用交换向量实现

原理:旋转向量x其实就是交换向量ab的两段,得到向量ba。
这里的a代表x中的前i个元素。假设a比b短,将b分为bL和bR,使得bR具有与a相同的长度。
交换a和bR,也就将a bL bR转换为bR bL a。序列a此时已处于其最终位置,因此现在的同样问题就集中到交换b的两部分。
由于新问题与原来的问题具有相同的形式,可以递归地解决。

实现


func VectorRotate(vec []byte, n int) {
    need, n := checkParam(vec, n)
    if !need {
        return
    }

    rotate(vec, n)
}

func rotate(vec []byte, l int) {
    length := len(vec)
    if length < 2 {
        return
    }

    r := length - l

    if l <= r {
        swapChunk(vec, 0, vec, length-l, l)
        rotate(vec[0:length-l], l)
    } else {
        swapChunk(vec, 0, vec, length-r, r)
        rotate(vec[r:], l-r)
    }
}

func swapChunk(src []byte, srcIndex int, dst []byte, dstIndex int, length int) {
    for i := 0; i < length; i, srcIndex, dstIndex = i+1, srcIndex+1, dstIndex+1 {
        t := src[srcIndex]
        src[srcIndex] = dst[dstIndex]
        dst[dstIndex] = t
    }
}

func checkParam(vec []byte, n int) (bool, int) {
    length := len(vec)
    if length < 2 {
        return false, n
    }

    if n < 0 {
        n = -1 * n
        n = n % length
        n = length - n
    } else {

        n = n % length
    }

    if n == 0 {
        return false, n
    }

    return true, n
}

问题扩展

向量旋转函数将向量ab变为ba。如何将向量abc变为cba?(这对交换非相邻内存块的问题进行建模)

这个问题其实可以先把 bc看作一个整体,那么问题就变为向量旋转的问题,旋转后变为bca,再对bc部分进行旋转,仍然是个向量旋转问题,旋转后即可得到最终结果cba。

如果用求逆的思路,仍然跟上面的类似。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据