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/16/2013 by Michael Xiao.

  1. 关于实现的一些备注。

  2. 该特殊的散列公式的真正好处是
  3. 我们的查询时间再次不变,
  4. 这对于像GPU这样的机器的并行度来说非常棒,
  5. 因为我们保持所有的线程都忙碌。
  6. 完全不存在线程发散,结构算法实际上相当简单且快速。
  7. 当它在共享内存上处理少量要散列的项,这实际上是非常有效的散列表结构,
  8. 但结果证明实际上它在大数据集方面也工作地相当好,
  9. 此时散列表需要在主内存构建。
  10. 需要记住的很重要的事情是
  11. 把我的项写入散列表并踢出其它项的操作需要是原子操作—
  12. 在我们的实现中,我们使用原子交换
  13. 以确保2个矛盾的线程不可能踩在互相头上。
  14. 最后一条备注,有不止一种方法可以解决
    这个一般的检查一个元素是否在集合中的问题。
  15. 不使用散列表,我们可以选择相当蛮力的方式进行。
  16. 我们可以选择对集合中所有元素排序作为一个构建步骤,
  17. 然后,在查询步骤,我们可以对集合进行二分查找
  18. 以查看是否存在特定元素。
  19. 例如,这个集合中我们可能有5个键。
  20. 为了构建该特别的数据结构,我们根据键对这些进行排序,
  21. 为了进行查询,我们只要在该集合中进行二分查找。
  22. 例如,如果我们用一个线程查询k6的值,
  23. 我们查看k5,我的键比这大。
  24. 然后我向这边移动,以此类推,直到我到达k6。
  25. 我可能有另一个线程在查询k3。
  26. 它从中间k5开始,然后进行二分查找直到它找到k3。
  27. 现在在GPU上排序很快,即使散列表在这个特定计算上更快,
  28. 但它们没有快非常多,以致绝不认为排序是个好主意。
  29. 常常在GPU上,有时一个蛮力方法,
  30. 如排序和二分查找,可能是你的最好选择。