Chinese, Simplified subtitles

← 见备注

Get Embed Code
2 Languages

Showing Revision 2 created 05/18/2013 by Michael Xiao.

  1. 我们尝试一个稍难的算法,叫做列表排名。
  2. 在列表排名中,每个节点都有它在列表中
    的后继节点的索引,
  3. 我们知道输出中的第一个元素。
  4. 我们希望做的是把节点排序。
  5. 这有很多用途,在我们实验室,我们用它来解压
  6. 被B sub2压缩的数据。那么让我们来看个例子。
  7. 例如,这里我们有10个节点。
  8. 我们知道输出将开始于节点0
  9. 及其后继节点,即链中前进一位是节点5。
  10. 节点5的后继节点是节点2。
  11. 节点2的后继节点是节点7,等等。
  12. 所以这是我们的输入—数组5、6、7、9、2、3、0、1。
  13. 我们的输出是什么?
  14. 输出会是0、5、2、7、4、9、1、6、3、8。
  15. 所以这是我们的输入,这是输出。
  16. 现在,你注意到数组实际上是圆形的,
  17. 所以有必要实际指定起点,
  18. 在这个例子中,我们说节点0是起点。
  19. 当然,一个串行处理器可以用N步完成这个。
  20. 问题是,我们如何让它在并行硬件上进行,
  21. 用更少的步骤完成?