为什么在 javascript 中这个 yield generator 的迭代次数是错误的？

Question

这是我正在尝试使用的代码片段。

function* genBubble(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      yield arr; // returning arr after every iteration
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1); // removed swap for brevity
      }
    }
  }
}
const tempArray = [3, 5, 8, 4, 1, 9, -2];
const genForLoop = genBubble(tempArray);

do {
  console.log(genForLoop.next());
} while (!genForLoop.next().done);

这是一个简单的冒泡排序实现。如您所知，冒泡排序有 n * (n - 1) / 2 次迭代，因此在这种情况下，数组的长度为 7，我们有 7 * (7 - 1) / 2 次迭代，等于 21.

但是当我运行这段代码时，我只得到 11 次迭代。输出如下图。

{ value: [ 3, 5, 8, 4, 1, 9, -2 ], done: false }
{ value: [ 3, 5, 8, 4, 1, 9, -2 ], done: false }
{ value: [ 3, 5, 4, 1, 8, 9, -2 ], done: false }
{ value: [ 3, 5, 4, 1, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 5, 1, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 1, 5, 8, -2, 9 ], done: false }
{ value: [ 3, 4, 1, 5, -2, 8, 9 ], done: false }
{ value: [ 3, 1, 4, 5, -2, 8, 9 ], done: false }
{ value: [ 1, 3, 4, -2, 5, 8, 9 ], done: false }
{ value: [ 1, 3, -2, 4, 5, 8, 9 ], done: false }
{ value: [ 1, -2, 3, 4, 5, 8, 9 ], done: false }

我正在使用node test.js来运行这个程序（test.js是写这个程序的文件）。

注意：我不想在每次迭代后打印数组。我要return它。如果有帮助的话。

Answer 1

您的主要问题是您调用了两次 next，但忽略了所有其他调用的 value。相反，将其称为一次并记住结果：

let result;
while (!(result = genForLoop.next()).done) {
  console.log(result.value.join(","));
}

...或者更简单地说，使用 for-of（这意味着您不必具有 genForLoop 标识符）：

for (const value of genBubble(tempArray)) {
  console.log(value.join(","));
}

但是（我已经很多年没有进行冒泡排序了）我相信你的内循环终止需要 j < arr.length - 1，而不仅仅是 j < arr.length - i - 1。我隐约记得内循环可以更短，但显然不是那样。

实例：

function swap(arr, i1, i2) {
  const t = arr[i1];
  arr[i1] = arr[i2];
  arr[i2] = t;
}
function* genBubble(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      yield arr; // returning arr after every iteration
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1); // removed swap for brevity
      }
    }
  }
}
const tempArray = [3, 5, 8, 4, 1, 9, -2];

for (const value of genBubble(tempArray)) {
  console.log(value.join(","));
}

.as-console-wrapper {
  max-height: 100% !important;
}

你的外循环条件应该是< arr.length，而不是< arr.length - 1。

为什么在 javascript 中这个 yield generator 的迭代次数是错误的？

Why are the number of iterations wrong with this yield generator in javascript?

javascript

iteration

generator

yield-keyword

bubble-sort