如何使用数组实现旋转木马？

Question

我有一个项目数组，代表一个虚拟的走马灯。

const carousel = ['a','b','c','d','e'];
let currentIndex = 0;

function move (amount) {
   const l = items.length;  // in case carousel size changes

   // need to update currentIndex

   return carousel[currentIndex];

}

当currentIndex == 0时向左移动，当currentIndex == length-1时向右移动，有什么简洁明了的处理方法吗？

我之前也思考过这个问题，但是没有想到任何非常聪明或简洁的方法。

- Alexander Mills

---

“当currentIndex为0且向左移动时，移动到哪里是处理变化最干净，最聪明的方式？当currentIndex为长度-1时向右移动呢？” “你所说的“最干净和最聪明”是什么意思？change在哪里使用？期望的结果是什么？” - guest271314

将数值相加并对列表长度取模。在包含8个项目的列表中，从5加4应返回1，因为9 % 8 = 1。 - Mr. Polywhirl

你可能想要考虑使用一个库？那将是最“聪明”的方式。至于“干净”，随着您的需求变化而改变——异步调用以更新内容？项目可以是带标题的图像、网页片段、带背景的文本？您的问题太广泛，无法简洁地回答。 - softwarenewbie7331

@softwarenewbie7331 在本质上询问如何处理一个circular array; 这个问题并不难回答。 - royhowie

@softwarenewbie7331如果变化超过1或-1，if/else语句将无法正常工作。@royhowie的答案是通用且最佳的解决方法。 - Alexander Mills

Answer 1

简短回答

通过模运算来实现循环数组。给定一个移动的距离，可以计算出相应的索引：

// put distance in the range {-len+1, -len+2, ..., -1, 0, 1, ..., len-2, len-1}
distance = distance % len
// add an extra len to ensure `distance+len` is non-negative
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距离：

// put `d` within the range {-len+1, -len+2, ..., -2, -1, -0}
d = d % len
// add an extra len to ensure `d+len` is non-negative
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

- royhowie

---

为什么要对距离进行取模？一个简单的 this.index = (whateverDistance + this.index) % this.arr.length 就足够了。 - Sukima

@Sukima在Carousel.move函数内进行了更详细的解释，但JS保留了%的符号，因此(0 + -13) % 5 == -3，但是-3不是有效的数组索引；添加len可以确保结果在范围内{0, 1, 2, ..., len-2, len-1}。 - royhowie

你的答案很好，因为它是通用的。我也将问题更改为更通用的形式。 - Alexander Mills

@AlexanderMills，这就是为什么我添加了distance = distance % len这一行的原因。 - royhowie

是的，虽然我仍在努力学习如何在纯JS中实现循环缓冲区的最佳设计。 - Sukima

Answer 2

我之前已经实现了一个 Array.prototype.rotate() 。在这个任务中它可能非常有用。以下是代码：

Array.prototype.rotate = function(n) {
var len = this.length;
return !(n % len) ? this.slice()
                  : this.map((e,i,a) => a[(i + (len + n % len)) % len]);
};
var a = [1,2,3,4,5,6,7,8,9],
    b = a.rotate(10);
console.log(JSON.stringify(b));
    b = a.rotate(-10);
console.log(JSON.stringify(b));

- Redu

Answer 3

currentIndex = currentIndex + change;
if (currentIndex >= l)  currentIndex = 0;
if (currentIndex < 0) currentIndex = l -  1;

这将修改索引，检查它是否有可能的值，并调整为轮播图的“side”之一。

- Arrisar

---

实用但有点无聊 :) - Alexander Mills

学会喜欢模（%）运算符。它在数组索引包装方面表现出色。 - Sukima

看到上面使用的模组，很喜欢！希望将来有机会尝试一下。Alex说得没错，虽然有点无聊，但确实有效。 :^) - Arrisar

好的，当你将旋转木马旋转超过1个位置时，它就无法工作了 :) - Alexander Mills