使用 JavaScript 进行算法动画的技术

• 下载源代码 - 1 Kb

引言

本文的目的是介绍一些使用 JavaScript 进行算法动画制作的基本技术。其中第一种技术是作者在之前的一些 CodeProject 文章中用于 汉诺塔 和 快速排序 的。

在本文中，我们介绍第二种技术，并将其用于对选择排序和插入排序算法进行动画制作。代码可以从 这里 运行。

这两种技术都可以用于动画递归算法。特别是，我们将展示选择排序和欧几里得最大公约数 (GCD) 算法递归版本的动画。后者示例可以从 这里 运行。

算法动画

算法动画的目标是向观众（学习者）展示算法执行的实时跟踪，显示数据修改和各种中间结果。然而，有用的动画应该是以生动的视觉形式呈现这些信息，从而帮助观众理解算法的工作原理。

算法动画通常被计算机科学教育者用作教学辅助工具，主要用于数据结构和算法课程。

在 Web 的早期 (1995-2003)，Java Applet 是实现算法动画的一种流行选择。要运行 Applet，Web 浏览器通常会使用一个加载 Java 运行时的插件。随着对安全风险的担忧日益加剧，大多数 Web 用户已经对使用包括 Applet 在内的插件感到厌倦。另一方面，JavaScript 在沙箱环境中由浏览器直接运行，并且功能受限，以最大程度地降低安全风险。随着客户端 Web 技术（HTML5 Canvas、SVG、CSS3、DOM 等）的发展，JavaScript 已成为实现算法动画的可行选项。

算法动画技术

算法动画的一种可行方法是在要动画化的算法程序代码的某些适当位置插入由两个函数调用组成的“ActivateAnimation(); Delay(T);”的代码。调用 Delay(T) 的目的是在动画播放期间引入时长为 T 的延迟。然而，存在一个大问题。JavaScript 缺少“真正的”延迟或休眠机制。如果我们通过自旋循环来实现延迟，那么整个 JavaScript 代码将在一个线程上执行，这将导致程序停滞不前。

为了解决上述问题，我们提出了以下（并为每个都赋予了一个名称）算法动画技术。

技术 1（堆栈技术）： 准备一个堆栈。修改要动画化的算法的程序代码，添加额外的代码，将动画所需的各种参数值推入堆栈。运行修改后的算法直至完成。然后处理堆栈，并结合一些视觉元素使用 JavaScript 的 setInterval() 函数来显示算法的进度。

正如作者在相关文章中所讨论的，该技术已成功用于汉诺塔和快速排序。

技术 2（Tick 技术）： 将算法执行期间的时间视为“滴答”（为此，我们使用全局变量 Tick，该变量在算法达到某个预定义状态时递增），然后当 Tick 达到由另一个变量 TargetTick 维护的某个预定义值时中止执行。例如，如果我们想在函数 f 执行 5 次循环迭代时中止其执行，我们可以将 TargetTick 设置为 5，并以 Tick= 0 开始，并在每次迭代后递增 Tick。有趣的是，如果在此时，我们递增 TargetTick，将 Tick 重置为 0 并重新执行函数 f，那么该函数将执行超过之前的状态并完成 6 次迭代。这正是此处给出的插入排序和选择排序算法动画背后的思想。该过程是通用的，因此可以应用于其他算法。之前的模式“ActivateAnimation(); Delay(T);”现在可以编码为“if (UpdateTick()) { ActivateAnimation(); return; }”。请注意使用“return”来中止算法的执行。执行将在已在对 setInterval() 的调用中设置的时间长度之后恢复（从执行历史的开头）。

函数 UpdateTick() 递增 Tick，如果 Tick 等于 TargetTick，则返回 true。在我们为选择排序和插入排序算法编写的代码中，上一行被插入到最内层循环中，并编码为“if (UpdateTick()) { PrintArray(A, ...); return; }”。

注意：函数 ActivateAnimation() 简单地命名为 PrintArray()。函数 PrintArray() 将数组渲染为 HTML 列表，并对列表的某些特定项应用不同的样式。

因此，整体动画过程的模式如下。

1. 设置 TragetTick = 1。
2. 执行要动画化的过程，从开始 (Tick = 0) 到 Tick = TragetTick。
3. 递增 TargetTick。

步骤 2 和 3 需要重复执行。因此，它们被包含在一个使用 setInterval() 调用重复执行的 JavaScript 函数中。

更具体地说，我们有这些函数，对于选择排序命名为 AnimateSelectionSort()，对于插入排序命名为 AnimateInsertionSort()，它们将在下面展示。

function AnimateSelectionSort()  
{  // This function is executed repeatedly via SetInterval()
   // Note: TargetTick is incremented with every call to this function 
   
   Tick=0;
   SelectionSort(A); 
   TargetTick++;   
}

function AnimateInsertionSort()
{ // This function is executed repeatedly via SetInterval()  
  // Note: TargetTick is incremented with every call to this function 
  
  B = A.slice(); // Start from an original copy of A   
  Tick=0; 
  InsertionSort(B); 
  TargetTick++;   
}

上述函数与算法无关，当然，除了引用正在动画化的实际算法的函数的那一行。每个上述函数都使用 setInterval() 函数激活。间隔时间决定了动画的速度，间隔越小，动画越快。每次函数激活时，它实际上都是从执行历史的开头执行的。因此，使用算法的原始（未修改的）输入更安全（而且实际上是合理的）。这就是为什么在 AnimateInsertionSort() 函数中，对 InsertionSort() 的调用使用了原始输入数组的副本。我们发现这对于我们的 SelectionSort() 函数不是必需的。SeectionSort() 函数的程序代码将在下一节中给出。InsertionSort() 的程序代码可以在文章下载的 HTML 文件中找到。

为递归算法使用 Tick 技术

读者可能会想 Tick 技术是否适用于递归算法。答案是肯定的。我们举两个例子。

作为第一个例子，考虑 SelectionSort_Rec() 函数，它是 SelectionSort() 函数的“递归”版本的重写（轻微修改）。下面的程序代码列表对比了这些函数。加粗的行是启用动画的代码。

function SelectionSort(A) 
{   
   for (var i = 0; i < A.length-1; i++) 
   {  var min_pos = i;
      var min = A[i];
      for(var j = i; j < A.length; j++)
      {   if (A[j] < min )
          {  min_pos= j; min =A[j]; }

          if (UpdateTick()) { PrintArray(A,i,j,min_pos); return; }
      }

      // swap A[i] with A[min_pos]
      var t = A[i]; A[i] = A[min_pos]; A[min_pos] = t;
   }

   // (i > A.length) last call to Printarray() to show array after final swap
   PrintArray(A,i+1,-1,-1); 
  EndAnimate(); 
}

function SelectionSort_Rec(A,i) 
{   
    if (i >= A.length-1)
    {  // (i > A.length) last call to Printarray() to show array after final swap
       PrintArray(A,i+1,-1,-1); 
       EndAnimate(); 
       return;
    }
 
    var min_pos=i ;
    var min = A[i];
    for(var j = i; j < A.length; j++)
    {  if (A[j] < min )
       {  min_pos= j; min =A[j]; }

       if (UpdateTick()) { PrintArray(A,i,j,min_pos); return; }
    }

    // swap A[i] with A[min_pos]
    var t = A[i]; A[i] = A[min_pos]; A[min_pos] = t; 

    SelectionSort_Rec(A,i+1); // Recursive call
}

function EndAnimate()
{  clearInterval(Timer1);  } 
 
function UpdateTick()
{  Tick++;
   return (Tick == TargetTick);
}

function PrintArray(A, prevleft, prevright)
{ // This function renders the array A as an HTML list 
  // Program code is omitted for brevity  
}

作为第二个例子，我们考虑欧几里得 GCD 算法的动画。动画只是显示递归树，每个递归调用进入或退出都对应树中的一个节点，如上图所示。树逐渐绘制，反映算法执行的进度。

GCD 动画的一些程序代码显示在下面的列表中。加粗的行是启用动画的代码。

function gcd(a,b)
{ // last param of Print() is either -1 to mean gcd() is entered
  // or positive (the gcd value) and also means gcd() is exited

   if (UpdateTick()) 
   { Print(a,b, -1); return; }  
  
   var c = a % b;
   
   if (c==0)
   {   if (UpdateTick())   
       { Print(a,b, b); return; }  

       return b; 
   }
   else 
   {  var k = gcd(b,c);

      if (UpdateTick())   
      { Print(a,b, k); return; }  

      return k;
    }
}

function Print(a,b,c) 
{  // Program code is omitted for brevity  
}

结论

该程序代码已在最新版本的流行浏览器中进行了测试。它在最新版本的 IE（版本 11）、Chrome（版本 30）和 Firefox（版本 24）中运行正常。