concurrency - 并发二值斩波算法

标签 concurrency binary-search

有没有办法(或者理论上可能)同时实现二分搜索算法?我猜答案很可能是否定的,原因有两个:

  • 尽管进行了大量的谷歌搜索,但我还没有在任何地方找到并发实现
  • 二进制砍伐的每个迭代周期都取决于前一个迭代的值,因此即使每次迭代都是一个单独的线程,它也必须阻塞,直到前一个迭代完成,从而使其顺序化。

但是,我想在这方面进行一些澄清(如果可能的话,有任何链接或示例吗?)

最佳答案

乍一看,二分查找似乎完全是非并行的。但请注意,只有三种可能的结果:

  • 您击中了该元素
  • 搜索到的元素位于您点击的元素之前
  • 该元素位于后面

因此我们启动三个并行进程:

  • 点击元素
  • 假设该元素在前面,则在此处搜索
  • 假设该元素在后面,则在那里搜索

一旦我们知道第一个元素的结果,我们就可以杀死那些不会找到该元素的元素。但与此同时,在正确位置搜索的过程使搜索速度提高了一倍,即当前的加速比可能是 3 中的 2。

当然,如果您有 3 个以上的核心可供使用,则可以推广此方法。重要的一点是,这种思维方式是在硬件内部完成的。例如,查找超前进位加法器。

关于concurrency - 并发二值斩波算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4812036/

相关文章:

java - 基于另一个线程结果的数据库回滚

c++ - 在 STL 中使用返回索引进行二进制搜索?

algorithm - 给定多个圆和一个点,如何找到哪个圆包含该点

sql-server - 即使没有显式事务,SQL Server 是否也获取锁?

c++ - 使用迭代和递归的二进制搜索算法

algorithm - 使用分而治之是否会提高在数组中查找最大值和最小值的时间复杂度

algorithm - 分段区间搜索

linux - 从多个进程追加到单个文件的 "Thread safety"?

java - Spring Boot 在 Controller 内执行并行方法

并行部分任务的 Java 并发模式