使用递归和 Promises 合并排序可视化

Question

我在 p5.js 中编写了一个合并排序可视化，它显示了合并排序的步骤。这作为顺序可视化效果很好，但我很想将其展示为真实的表示，您可以在其中看到数组的每个部分同时排序（多个部分同时可视化排序，以真正体现递归）。代码本身比较简单：

    // Split the array recursively
    let mid = Math.floor((right + left) / 2);

    if (right - left < 1) {
        return;
    }
    
    // My attempt to visualise this properly
    await Promise.all([mergeSortSlice(array, left, mid), mergeSortSlice(array, mid + 1, right)]);
    
    // THIS WORKS, but only for sequential sorting
    // await mergeSortSlice(array, left, mid);
    // await mergeSortSlice(array, mid + 1, right)

   // Putting sleep(200) here also works, but doesn't show the steps of the sort as they are happening, just the result of each stage of the sort.

    leftCounter = 0;
    rightCounter = 0;
    l = left;
    r = mid + 1;
    valuesStartIndex = l;
    let leftArray = array.slice(left, r);
    let rightArray = array.slice(r, right + 1);

    while (rightCounter < rightArray.length && leftCounter < leftArray.length) {
        if (leftArray[leftCounter] < rightArray[rightCounter]) {
            array.splice(l + rightCounter, 1);
            array.splice(valuesStartIndex, 0, leftArray[leftCounter]);
            l++;
            leftCounter++;
            valuesStartIndex++;
            await sleep(200);

        } else {
            array.splice(r, 1);
            array.splice(valuesStartIndex, 0, rightArray[rightCounter]);
            r++;
            rightCounter++;
            valuesStartIndex++;
            await sleep(200);
        }
    }

使用 Promise.all 的问题是数组的拆分部分混淆了，我相信是由于递归？这导致数组未正确排序。

我的超时函数：

async function sleep(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}

设置函数和绘制循环：

let values = [50, 10, 80, 56, 30, 25, 15]

function setup() {
    createCanvas(600, 190);
    frameRate(60);
    mergeSort(values)
}

function draw() {
    rectWidth = 10;
    background(23);
    stroke(0);
    fill(255);

    for (let i = 0; i < values.length; i++) {
        rect(i * rectWidth, height - values[i], rectWidth, values[i]);
    }
}

异步函数和递归的结合让我很难想出解决方案。任何 help/advice 将不胜感激。

Answer 1

您实际上非常接近找到可行的解决方案。您的问题是您在 mergeSortSlice 函数中创建了一堆全局变量：

  // These were all missing the let keyword
  // And were therefore either assigning or implicitly declaring
  // globally scoped variables.
  let leftCounter = 0;
  let rightCounter = 0;
  let l = left;
  let r = mid + 1;
  let valuesStartIndex = l;
  let leftArray = array.slice(left, r);
  let rightArray = array.slice(r, right + 1);

当一个函数调用的两个实例作为 Promise 的一部分运行时，每个实例都等待超时，它们的执行将交错进行（这是您想要的，因此您可以图形化地表示理论上的并行性） .但是，当这些函数更改全局变量时，这是一个典型的共享内存多线程错误。

这是对您的代码的改编，修复了错误，添加了突出显示，并且延迟策略略有不同：

function merge_sort(p) {
  const Mode = {
    Shuffling: 0,
    Sorting: 1
  };
  const spacing = 5;

  let array = [...Array(40)].map((_, i) => i);
  let highlights = [];
  let itemWidth;
  let itemHeight;

  let currentMode = Mode.Shuffling;
  let iterator;

  let frameRate = 8;

  let redrawPromise;
  let signalRedraw;

  p.setup = function() {
    p.createCanvas(p.windowWidth, p.windowHeight);
    p.frameRate(frameRate * 5);

    itemWidth = (p.width - (spacing * (array.length + 1))) / array.length;
    itemHeight = p.height - spacing * 2;

    iterator = shuffle();
    initRedrawPromise();
  };

  function initRedrawPromise() {
    redrawPromise =
      new Promise(resolve => {
        signalRedraw = resolve;
      });
    redrawPromise.then(() => initRedrawPromise());
  }

  p.draw = function() {
    p.background('white');

    // draw
    for (let i = 0; i < array.length; i++) {
      if (highlights[i]) {
        p.fill(highlights[i]);
      } else {
        p.fill('blue');
      }

      let fractionalHeight = (array[i] + 1) / array.length;
      let pixelHeight = fractionalHeight * itemHeight;
      p.rect(
        (i + 1) * spacing + i * itemWidth,
        spacing + (itemHeight - pixelHeight),
        itemWidth,
        pixelHeight
      );
    }

    signalRedraw();

    if (currentMode === Mode.Shuffling) {
      // update
      let next = iterator.next();
      if (next.value) {
        // Done suffle, switch to sort
        currentMode = Mode.Sorting;
        p.frameRate(frameRate);
        sort().then(() => {
          // switch back to shuffling
          currentMode = Mode.Shuffling;
          p.frameRate(frameRate * 5);
          iterator = shuffle();
        });
      }
    }
  };

  p.keyPressed = function(e) {
    if (e.key === 'ArrowRight' || e.key === 'ArrowUp') {
      frameRate++;
      p.frameRate(frameRate);
    } else if (e.key === 'ArrowLeft' || e.key === 'ArrowDown') {
      frameRate = Math.max(0, frameRate - 1);
      p.frameRate(frameRate);
    }
  }

  // shuffle the array. yield false for each step where the array is not yet shuffled. yield true once the array is shuffled.
  function* shuffle() {
    // for each position in the array (except the last position),
    //   if the chosen item is not the current item, swap the two items.
    for (let i = 0; i < array.length - 1; i++) {
      highlight(i);
      yield false;

      let j = randomInt(i, array.length);
      if (j !== i) {
        highlight(i, j);
        yield false;

        swap(i, j);

        highlight(j, i);
        yield false;
      } else {
        highlight(i);
        yield false;
      }
    }

    yield true;
  }

  function sort() {
    highlights = [];
    return sortSlice(0, array.length - 1);
  }

  async function sortSlice(left, right) {
    if (right - left < 1) {
      return;
    }

    // Split the array recursively
    let mid = Math.floor((right + left) / 2);

    await Promise.all([sortSlice(left, mid), sortSlice(mid + 1, right)]);

    for (let ix = left; ix <= right; ix++) {
      highlights[ix] = undefined;
    }

    let leftCounter = 0;
    let rightCounter = 0;
    let l = left;
    let r = mid + 1;
    let valuesStartIndex = l;
    let leftArray = array.slice(left, r);
    let rightArray = array.slice(r, right + 1);

    while (rightCounter < rightArray.length && leftCounter < leftArray.length) {
      if (leftArray[leftCounter] < rightArray[rightCounter]) {
        array.splice(l + rightCounter, 1);
        array.splice(valuesStartIndex, 0, leftArray[leftCounter]);
        highlights[valuesStartIndex] = 'green';
        highlights[r] = 'red';
        l++;
        leftCounter++;
        valuesStartIndex++;
      } else {
        array.splice(r, 1);
        array.splice(valuesStartIndex, 0, rightArray[rightCounter]);
        highlights[valuesStartIndex] = 'green';
        r++;
        rightCounter++;
        valuesStartIndex++;
        highlights[l + rightCounter] = 'red';
      }

      // at each merge step wait for a redraw that shows this step
      await redrawPromise;
      highlights[valuesStartIndex - 1] = 'gray';
      for (let ix = valuesStartIndex; ix <= right; ix++) {
        highlights[ix] = undefined;
      }
    }
  }

  function swap(i, j) {
    const tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }

  function randomInt(lowerBound, upperBound) {
    return lowerBound + Math.floor(Math.random() * (upperBound - lowerBound));
  }

  function highlight(i, j) {
    highlights = [];
    if (i !== undefined) {
      highlights[i] = 'green';
    }
    if (j !== undefined) {
      highlights[j] = 'red';
    }
  }
}

sketch = new p5(merge_sort);

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.4.0/p5.js"></script>

使用递归和 Promises 合并排序可视化

Merge sort visualisation using recursion and Promises

javascript

sorting

recursion

promise

p5.js