Chinese, Simplified subtitles

← cs344_unit4_20_q_基数排序

Get Embed Code
2 Languages

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

  1. 所以到目前为止,我们已经看到一些真正有趣的算法,
  2. 但 GPU 性能的领导者和我们到目前为止
    讨论过的那些内容没有关系。
  3. 相反,通常在 GPU 上运行最高执行排序
  4. 我们使用不同的排序算法,称为基数排序。
  5. 现在,所有以前的排序算法都是比较排序,
  6. 意思是我们在一个项目上的唯一操作是拿它和另一个比较。
  7. 基数排序依赖于使用位置表示法的一种数字表达形式。
  8. 在这种情况下,位是更重要的,
    当我们在字中进一步向左移动,
  9. 使用整数来解释最容易。
  10. 因此,基数排序的算法如下所示,
  11. 以整数的最低有效位开始,将输入拆分成 2 个集合,
  12. 那些在这个特定位位置上是0的和那些是1的集合。
  13. 否则,保持原来的顺序。
  14. 然后继续到下一个的最低有效位,
    然后重复直到我们处理完所有位。
  15. 所以像往常一样,我们要做一个示例,那样将更加清楚,
  16. 我们要使用无符号整数。
  17. 所以我们要进行排序是这一栏左边的数字,
  18. 而这里是这些数字的二进制表示形式。
  19. 所以我们要从这里的最低有效位开始。
  20. 所以,我们要执行此操作的方法,
    是取走最低有效位为0的所有元素。
  21. 而我们将以另外的方式保持它们的顺序,
    但我们要把它们放在顶部。
  22. 然后我们会取出其余所有的元素,
  23. 那些最低有效位是1的元素,
  24. 然后我们要再次让他们保持顺序,
    并将它们追加到我们刚刚创建的列表。
  25. 所以这个所创建的是一个所有最低有效位为0的列表,
  26. 然后所有的最低有效位是1的列表。
  27. 现在我们将移动到下一个最低有效位,
  28. 所以,这个中间位,然后我们要做同样的事情。
  29. 我们要取出所有为0的数字,并把它们放在顶部,
  30. 然后我们会取出所有为1的数字,放到下面。
  31. 在这里的虚线只是显示我们观察的数据移动。
  32. 绿线是那些中间位是 0的数据,
  33. 而蓝线是中间位为1的数据。
  34. 现在我们来看下一个最高有效位——
  35. 在这个例子,最高有效位 — 我们将再做同样的操作。
  36. 在最高有效位是零的向上移动到顶部,是1的移动到底部。
  37. 除此之外,我们继续保持顺序。
  38. 现在我们有一个有序序列。很酷吧?
  39. 现在,此代码在 GPU上运行流畅,有 2 个很大原因。
  40. 第一是其工作的复杂性。最佳的比较基础排序是O (n log n)。
  41. 另一方面,这种算法是O(kn),
  42. 意思是运行时在2个不同的事物中是线性关系。
  43. 首先,在表示形式中,位数是线性的。
  44. 所以在它的表示形式上,这个特定的整数有3位,
  45. 而且我们花了3个阶段才能完成输入的排序。
  46. 第二,要排序的项数是线性的。
  47. 所以在这里的表示形式中,我们有 8 个项目。
  48. 因此,工作量和 8 成正比。
  49. 一般情况下,针对任何合理的程序,k 是恒定的,比如说一个 32 位字或一个 64 位字。
  50. 而且一般来讲也是如此,这种工作的复杂性
  51. 主要是和我们需要排序的项目数成正比。
  52. 所以这就是到目前为止我们已经讨论过的任何排序的超级工作复杂性。
  53. 所以那就这个看起来很好的一个原因。
  54. 第二个是底层操作,也就是我们需要对每一步输入进行的这种分割,
  55. 那些是实际上非常有效的操作。
  56. 而事实上,他们是你早已熟悉的的高效操作。
  57. 让我们仔细看看我们在做什么。
  58. 我们仅要看看基数排序算法的第一阶段,
  59. 其中我们只考虑最低有效位的值,
  60. 而且我们只是要看看最低有效位是0的输出。
  61. 到现在我们实际在这里做什么?
  62. 我们今天已经学会一种做这个运算算法。
  63. 所以取出此输入并以此创建输出的算法的名称是什么?