有没有更高效的方法来做这个算法？

据我所知，这种算法会在需要时正确搜索并变为真。在课堂上，我们谈论的是大O分析，所以这个任务是展示递归搜索如何比迭代搜索更快。重点是搜索一个数字，使得A [i] = i（找到一个与存储在索引处的数字相同的索引）。该算法与迭代算法相差仅约100纳秒，但有时迭代速度更快。我使用rand（）函数设置主要矢量。我运行这两种算法一百万次并记录时间。我问的问题是，这个算法是否尽可能高效，或者有更好的方法来做到这一点？有没有更高效的方法来做这个算法？

bool recursiveSearch(vector<int> &myList, int beginning, int end) 
{ 
    int mid = (beginning + end)/2; 

    if (myList[beginning] == beginning) //check if the vector at "beginning" is 
    {          //equal to the value of "beginning" 
     return true; 
    } 

    else if (beginning == end) //when this is true, the recursive loop ends. 
    {       //when passed into the method: end = size - 1 
     return false; 
    } 

    else 
    { 
     return (recursiveSearch(myList, beginning, mid) || recursiveSearch(myList, mid + 1, end)); 
    } 

}

编辑：在传递之前，该列表预有序和一个检测在主做是为了确保开头和结尾都存在

来源

2014-01-24 user2908474

对于大O分析，无论您检查元素的顺序如何：线性（迭代）还是跳跃（递归），在未排序数组中查找值的最佳方式为“O（n）”同样好。但是，实际运行时间可能会有很大差异。通常你不关心这些微小的差异（时间上，也就是说，速度可能快1.5倍，但如果差距是100ns，谁在乎？），然而（你总是可以购买更快的机器;-)）。 –

我担心时差的唯一原因是因为我的教授想证明这一点。这两种算法在我的机器上相差大约7微秒（在对我的向量的参考之后），实际上这并不重要，但它的任务说 – user2908474

@ user2908474你不能着手“证明” 。你运行实验，并报告你的发现。虽然两种算法都是O（N），但理论上，递归有更多的开销WRT迭代。另一方面，C和C++编译器非常擅长将递归代码优化为迭代代码。因此，在不同的优化级别上查看这两种方法产生的汇编代码可能是值得的。 – juanchopanza

一个可能的“改善”将不可复制每个递归中的向量通过传递一个引用：

bool recursiveSearch(const vector<int>& myList, int beginning, int end)

来源

2014-01-24 07:47:04 juanchopanza

此外，使用'operator []'而不是'at（）'会节省边界检查。 –

使用方括号并使用引用，它将算法加速了大约7微秒，在这个用法中足以证明这是一个更快的算法。谢谢！ – user2908474

@ user2908474这（它比迭代更快）让我感到惊讶。您的迭代方法能否也存在一些不必要的低效率？而且，这必须是矢量中元素数量的函数。同样值得用许多不同的随机种子进行测试以获得全部种群或结果。 – juanchopanza

一个明显的“改进”是在所有其余的内核上运行线程。只需将vector分配给number of cores - 1件，并使用条件变量在找到时发出主线程信号。

来源

2014-01-24 07:59:07

除非您知道有关数据排序的特殊内容，否则执行此类分区搜索绝对没有好处。

事实上，你的代码实际上是[尝试]做一个线性搜索，所以它实际上实现了一个简单的for循环，其代价是大量的堆栈和开销。

请注意，您的代码中存在一个奇怪的现象：如果第一个元素不匹配，您将致电recursiveSearch(myList, beginning /*=0*/, mid)。由于我们已经知道元素0不匹配，所以您将再次细分，但只能在重新测试元素之后再进行细分。

因此，考虑有没有匹配6种元素的载体，你要拨打：

recursiveSearch（myList中，0,6）; - > < recursiveSearch（myList，0，3）|| recursiveSearch（myList，4，6）; > - > < recursiveSearch（myList，0，1）|| recursiveSearch（2，3）> < recursiveSearch（myList，4，5）; || recursiveSearch（myList，5，6）; > - > < recursiveSearch（myList，0，0）|| recursiveSearch（myList，1，1）> < recursiveSearch（myList，2，2）|| recursiveSearch（myList中，3,3）> ...

最后，你没有在给定的指标，因为你达到这样的开始和结束都是这个值，这似乎是一种昂贵的方式，条件消除每个节点，并且最终结果不是分区搜索，它是一种简单的线性搜索，您只需使用大量堆栈深度即可实现。

所以，一个简单和快速的方式来做到这一点是：

for (size_t i = beginning; i < end; ++i) { 
    if (myList[i] != i) 
     continue; 
    return i; 
}

因为我们想在这里最优化，这是值得指出的是MSVC，GCC和Clang的所有假设if表示可能案例，所以我在这里优化退化的案例，我们有一个没有或没有晚期匹配的大型向量。如果我们运气好，我们会尽早找到结果，那么我们愿意为潜在的分支小姐付出代价，因为我们正要离开。我意识到，分支缓存将很快弄清楚了这一点对我们来说，但又 - 优化;-P

正如其他人所指出的那样，你也可以从不能按值传递的载体（强制复印件）

受益

const std::vector<int>& myList

来源

2014-01-24 08:07:50 kfsone

如果您需要在未排序数组中找到一个元素，例如A[i] == i，那么唯一的方法就是遍历每个元素，直到找到一个元素。

要做到这一点最简单的方法是，像这样：

bool find_index_matching_value(const std::vector<int>& v) 
{ 
    for (int i=0; i < v.size(); i++) { 
     if (v[i] == i) 
      return true; 
    } 
    return false; // no such element 
}

这是O(n)，而你不会是能够做到任何比这更好的算法。所以我们必须把注意力转向微观优化。一般来说，如果在现代机器上，你的递归解决方案比上面简单的解决方案更快，我会感到非常惊讶。尽管编译器可能（可能）能够移除额外的函数调用开销（有效地将递归解决方案转换为迭代解决方案），但按顺序（如上所述）依次运行数组允许优化使用缓存，而对于大数组，你的分区搜索不会。

来源

2014-01-24 08:09:58

有没有更高效的方法来做这个算法？

回答

相关问题