Почему количество итераций неправильно с этим генератором доходности в JavaScript? - PullRequest
Новая
       15

Почему количество итераций неправильно с этим генератором доходности в JavaScript?

0 голосов
/ 30 октября 2018

Итак, вот фрагмент кода, с которым я пытаюсь работать. 

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 - это файл, в котором написана эта программа).

Примечание: я не хочу печатать массив после каждой итерации. Я хочу вернуть это. Если это поможет.

1 Ответ

0 голосов
/ 30 октября 2018

Ваша основная проблема в том, что вы звоните 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. Я смутно припоминаю, что внутренний цикл может быть короче, но, видимо, не таким образом.

Live Пример: 

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.

...