YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Chinese, Simplified subtitles

← 列表排名开始部分重做

Get Embed Code
2 Languages

Showing Revision 2 created 05/23/2013 by Lian7.

  1. 关于图的讨论,我作过以下表述;
    让我引述我自己。
  2. "如果我们有一个图表,只有一条线性链,
    最后一个节点会是节点N- 1。
  3. "线性链是很难并行的。
  4. 如果我们在这里进行BFS(宽度优先搜索),
    它将花费我们O(n)个步骤来到达图表的最后。"
  5. 让我以另一种方式说明这个问题。
  6. 我在一个线性链中有N个节点,
  7. 并且链中的每个节点知道下一个节点的 ID。
  8. 这只是一个简单的链接列表。
  9. 每个节点找到列表末尾的算法是什么?
  10. 当然我们可以在N步内解决这个问题。
  11. 假设每个节点都有下一个指针,
    我已经把那些标示为蓝色,
  12. 指针指向链中的下一个节点,
    而且最后一个节点的下个指针等于null。
  13. 现在我们根本不打算更改下一个指针,
    否则我们就会失去我们列表的结构。
  14. 所以我们要假定它们只读。
  15. 所以我们要为每个节点存储第二个我们可以更改的指针。
  16. 出于历史原因,我们会把这个指针叫做chum,
  17. 而且我们要将它指定为红色。
  18. 然后在算法的最后,我们想要每个节点的chum指针
    指向链中的最后一个节点。
  19. 所以,简单的算法是在每个节点的每次迭代
  20. 把chum设为下一个chum,直到我们到达一个节点,
    它的下一个是空。
  21. 所以我们首先将把所有的chum指针指向它们自己的节点。
  22. 这就是我们将如何初始化它们,同样地,
    在每次迭代,我们将chum设为下一个指针。
  23. 所以在第一次迭代,它会看起来像这样,
    现在我们要做另一次迭代。
  24. 所以对于任何特定的节点,我们寻找chum,然后下一个。
  25. 所以在第二次迭代,它要看起来像这样,以此类推。
  26. 所有在每次迭代,chum指针的长度就比前一次迭代多1。
  27. 问题是——重要的问题是,我们可以做得更好吗?
  28. 结果显示答案是肯定的,
  29. 这个由 Danny Hillis和Guy Steele在1986年描述的算法,
  30. 不是由他们发现,但他们很好地进行了描述,
  31. 它非常棒,它是我起初决定做并行计算的一个原因。
  32. 让我们分析我们刚才描述的算法的复杂性。
  33. 显然一个串行处理器可以在N步内、
    以O(n)的工作量做此计算。
  34. 并行处理器会怎么样?
  35. 我们知道这需要 N步。那么多少工作量?
  36. 你的选择有O(N)、O(N log N)、
    O(N N^1/2),或者 O(N^2)。