并行二进制搜索

6 回答

• 4

  是的，在经典的并行化意义上（多核），二分搜索和BST并没有好多少 .

  对于每个处理器，存在诸如在L1高速缓存上具有BST的多个副本的技术 . 只有一个处理器处于活动状态，但具有多个L1缓存的增益可能很大（L1为4个周期，L2为14个周期） .

  在实际问题中，您经常同时搜索多个键 .

  现在，还有另一种可以帮助的并行化：SIMD！查看英特尔/ UCSC / Oracle（SIGMOD 2010）团队的“现代CPU和GPU上的快速架构敏感树搜索” . 这很酷 . 顺便说一句，我的目前研究项目都是基于这篇论文 .

  回复于 2024-04-28T13:12:32+08:00
• 3

  您可以轻松使用并行性 .

  对于 k 小于 n 处理器，将阵列拆分为 n/k 组并为每个组分配处理器 .

  在该组上运行二进制搜索 .

  现在时间是 log(n/k) .

  还有一种船员方法是 logn/log(k+1) .

  回复于 2024-04-28T13:12:32+08:00
• 2

  我认为它肯定有资格进行并行化 . 至少，跨越两个线程 . 让一个线程执行深度优先搜索，另一个执行广度优先搜索 . 获胜者是执行速度最快的算法，可能与数据集到数据集不同 .

  回复于 2024-04-28T13:12:32+08:00
• 1

  我在并行编程方面没有太多经验，但我怀疑这是并行处理的一个很好的选择 . 算法的每一步都取决于执行一次比较，然后根据此比较继续向下设置“路径”（您要么找到了您的值，要么现在必须根据比较继续搜索一组“方向”） . 执行相同比较的两个独立线程不会让你在任何地方更快，并且单独的线程将需要依赖相同的比较来决定下一步做什么，所以他们不能真正做任何有用的，分开的工作自己 .

  至于你分裂数组的想法，我认为你只是在这种情况下否定二分搜索的好处 . 您的值（假设它在您的数组中）将位于数组的顶部或底部 . 二进制搜索中的第一个比较（在中点）将告诉你应该查看哪一半 . 如果你更进一步，考虑将N个元素的数组分成N个不同的二进制搜索（一个天真的并行尝试） -ize） . 当你不需要的时候，你正在进行N次比较 . 您正在失去二分搜索的功能，因为每次比较都会将搜索范围缩小到适当的子集 .

  希望有所帮助 . 欢迎评论 .

  回复于 2024-04-28T13:12:32+08:00
• 13

  并行实现可以加速二进制搜索，但改进并不是特别重要 . 最坏的情况是，二进制搜索所需的时间是 log_2(n) ，其中 n 是列表中元素的数量 . 一个简单的并行实现将主列表分成 k 子列表，由并行线程进行bin搜索 . 二进制搜索的最坏情况时间是 log_2(n/k) ，实现了搜索时间的理论减少 .

  Example: 1024 条目列表使用单个线程进行二元搜索所需的 10 个循环次数 . 使用 4 个线程，每个线程只需要 8 个周期来完成搜索 . 并且使用 8 个线程，每个线程需要 7 个周期 . 因此， 8 线程并行二进制搜索可能比单线程模型快 30% .

  但是，他的加速不应该与效率的提高相混淆：与单线程二进制搜索执行的 10 比较相比， 8 线程模型实际执行 8 * 7 = 56 比较以完成搜索 . 如果并行应用二进制搜索的速度的边际增益对于它们的应用是合适的或有利的，则由程序员自行决定 .

  回复于 2024-04-28T13:12:32+08:00
• 3

  我非常确定二进制搜索可以加速log（M）因子，其中M是处理器的数量 . 对于常数M，log（n / M）= log（n） - log（M）> log（n）/ log（M） . 我没有严格下界的证明，但如果M = n，则执行时间是O（1），这不能再好了 . 下面是算法草图 .

  Parallel_Binary_Search(sorted_arraylist)

  • 将sorted_arraylist划分为M个大小的块N / M .

  • 将一个比较步骤应用于每个块的中间元素 .

  • 如果比较器发出相等的信号，则返回地址并终止 .

  • 否则，识别两个相邻的块，其中比较器分别用信号通知（>）和（<） .

  • 从信号（>）之后的元素开始形成一个新的Chunk，并以信号（<）之前的元素结束 .

  • 如果它们是相同的元素，则返回失败并终止 .

  • 否则，Parallel_Binary_Search（Chunk）

  回复于 2024-04-28T13:12:32+08:00