简短回答
通过模运算来实现循环数组。给定一个移动的距离,可以计算出相应的索引:
distance = distance % len
new_index = (index + distance + len) % len
长回答
使用模运算,就像读普通的模拟时钟一样。基本原则是将两个整数相加,除以一个整数,并保留余数。例如,13 = 3 (mod 10)
,因为 13
是 1*10 + 3
,而 3
是 0*10 + 3
。
但我们为什么要安排3
和13
呢?为了回答这个问题,我们需要考虑到欧几里得除法算法(EDA)。它表明对于两个整数a
和b
,存在唯一的整数q
和r
,使得
a = b*q + r
带有0 ≤ r < b
。这比你想象的更强大:它使我们能够"在模n下工作"。
也就是说,我们可以说a = b (mod n)
当且仅当存在唯一的整数q1
、r1
、q2
和r2
,满足
a = n * q1 + r1, 0 ≤ r1 < n
b = n * q2 + r2, 0 ≤ r2 < n
而且r1
等于r2
。我们称r1
和r2
为“余数”。
回到之前的例子,我们现在知道为什么13 = 3 (mod 10)
。EDA说13 = 1*10 + 3
,1
和3
是满足必要约束条件的唯一q
和r
;同理可得,3 = 0*10 + 3
。由于余数相等,我们说在“模10运算”中13
和3
相等。
幸运的是,JavaScript本身就实现了模运算符。不幸的是,我们需要注意一个怪异的地方,即模运算符保留其操作数的符号。这会导致一些结果,例如:-6 % 5 == -1
和-20 % 7 == -6
。虽然它们是完全有效的数学陈述(请自行验证原因),但对于数组索引来说并没有帮助。
引理1: a + n = a (mod n)
引理2: -1 = n-1 (mod n)
引理3: -a = n-a (mod n)
克服这个问题的方法是“欺骗”JavaScript使用正确的符号。假设我们有一个长度为len
且当前索引为index
的数组;我们想要将索引移动d
距离:
d = d % len
new_index = (index + d + len) % len
我们首先将d
放入范围{-len+1, -len+2, ..., -2, -1, -0}
中。接下来,我们添加一个额外的len
,以确保我们移动的距离在范围{1, 2, ..., len-1, len}
内,从而确保%
运算的结果具有正号。我们知道这行得通,因为(-a+b) + a = b (mod a)
。然后,我们将新索引设置为index + d + len (mod len)
。
更详细的实现:
class Carousel {
// assumes `arr` is non-empty
constructor (arr, index = 0) {
this.arr = arr
this.index = index % arr.length
}
// `distance` is an integer (...-2, -1, 0, 1, 2, ...)
move (distance) {
let len = this.arr.length
distance = distance % len
let new_index = (this.index + distance + len) % len
this.index = new_index
return this.arr[this.index]
}
}
// usage:
let c = new Carousel(['a','b','c','d','e'], 1) // position pointer set at 'b'
c.move(-1) // returns 'a' as (1 + -1 + 5) % 5 == 5 % 5 == 0
c.move(-1) // returns 'e' as (0 + -1 + 5) % 5 == 4 % 5 == 4
c.move(21) // returns 'a' as (4 + 21 + 5) % 5 == 30 % 5 == 0
currentIndex
为0且向左移动时,移动到哪里是处理变化最干净,最聪明的方式?当currentIndex
为长度-1时向右移动呢?” “你所说的“最干净和最聪明”是什么意思?change
在哪里使用?期望的结果是什么?” - guest271314