岁虚山

行由不得,反求诸己

0%

编程珠玑-向量旋转

场景描述

假设我们有这么一个问题:

我们有一个 n 维的向量(数组),现在我们需要将前面的 r 个元素移动到末尾,如下所示:

我们该如何操作呢?

方法一

如果对操作方法不加任何限制,我们可以将这个向量当作数组来进行操作

1、定义一个额外的数组,保存前 r 个数据;

2、将剩下的 n - r 个数据从第 r + 1 位向前平移 r 位;

3、将额外数组中的数据复制到 原数组的后 r 位中。

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 7
r = 3
samples = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
tmpsample = ['' for i in range(0,r)]

for i in range(0, r):
tmpsample[i] = samples[i]

for i in range(r, n):
samples[i - r] = samples[i]

for i in range(n - r, n):
samples[i] = tmpsample[i - (n - r)]

我们来分析一下上面方法的消耗:

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 7
r = 3
samples = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
tmpsample = ['' for i in range(0,r)] #开辟了一个大小为 r 的数组

for i in range(0, r): #r 次赋值操作
tmpsample[i] = samples[i]

for i in range(r, n): #n - r 次赋值操作
samples[i - r] = samples[i]

for i in range(n - r, n): #r 次赋值操作
samples[i] = tmpsample[i - (n - r)]

1、大小为 r 的额外空间

2、n + r 次赋值操作(忽略循环本身内部消耗)

看起来似乎很简单,但是我们要注意一点,采用这种方法的时候,我们额外开辟了一个大小为 r 的数组,在上面的例子中,r = 3 ,可能我们觉得这个开销并不算什么,但是当我们的数据达到一定数量时(比如 n = 100000000, r = 99999999),这个额外的空间开销以及时间消耗就十分巨大了。而我们可能并没有足够的内存空间以及时间来让我们使用。

方法二

看起来第一个方法足够简单清晰,但是性能似乎并不是那么好。那么,还有其他的方法吗?

让我们思考一下,对向量的旋转在操作的本质上就是对数据的平移,之所以消耗了大量的空间以及时间,就在于我们在将后面的数据平移到前面的数据时,需要临时保存前面的数据。

但是,我们同样可以发现,在我们平移最后的 r 位数据时,后面的这些空间似乎被浪费掉了。那么,我们能否将最后面的这 r 个空间利用起来呢?

让我们将整个数组想象成一个圆环,然后从最后面的一位向前平移 r 位,被替换的数字同样向前平移 r 位,直到到达数组中的前 r 位数据,这时,我们将这一位数据放到最后面的 r 位中:

-------------本文结束 感谢阅读-------------
打赏一包辣条