- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
在阅读 http://en.cppreference.com/w/cpp/algorithm/binary_search 时我注意到它将转发迭代器作为参数。现在我很困惑,因为我认为它宁愿是一个随机访问迭代器,所以二进制搜索实际上是二进制的。
为了满足我的好奇心,我写了一个小程序:
#include <iostream>
#include <vector>
#include <forward_list>
#include <list>
#include <deque>
#include <algorithm>
#include <chrono>
#include <random>
int main()
{
std::uniform_int_distribution<int> uintdistr(-4000000, 4000000);
std::mt19937 twister(std::chrono::high_resolution_clock::to_time_t(std::chrono::high_resolution_clock::now()));
size_t arr[] = { 200000, 400000, 800000, 1600000, 3200000, 6400000, 12800000 };
for(auto size : arr)
{
std::list<int> my_list;
for(size_t i = 0; i < size; i++)
my_list.push_front(uintdistr(twister));
std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
my_list.sort(); //fixed
start = std::chrono::high_resolution_clock::now();
std::binary_search(my_list.begin(), my_list.end(), 1252525);
end = std::chrono::high_resolution_clock::now();
long long unsigned elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
std::cout << "Test finished in " << elapsed_time << "\n";
}
}
用 gcc 4.7.0 编译并运行
g++ -std=c++11 test.cpp
在我的机器上提供以下结果:
Test finished in 0
Test finished in 15625
Test finished in 15625
Test finished in 46875
Test finished in 93750
Test finished in 171875
Test finished in 312500
所以看起来它实际上并没有在前向列表上进行二进制搜索。现在我的问题是:
为什么会有这样一个令人困惑的名字?
为什么允许这样的代码?
为什么引用文献说它是“第一个和最后一个之间距离的对数”?
标准对此有何规定?
编辑:现在代码在搜索之前对列表进行排序 - 愚蠢的错误,现在结果是:
Test finished in 46875
Test finished in 109375
Test finished in 265625
Test finished in 546875
Test finished in 1156250
Test finished in 2625000
Test finished in 6375000
当然仍然不是对数;)
最佳答案
原始 SGI STL 实现的文档,该标准源自该文档,states that
The number of comparisons is logarithmic: at most log(last - first) + 2. If
ForwardIterator
is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.
也就是说,比较次数总是对数,而由于缺乏随机可访问性而影响的进步次数可以是线性的。在实践中,stl::advance
可能使用,如果迭代器是随机访问,则复杂度是恒定的,否则是线性的。
如果比较非常昂贵,则具有线性数量的迭代器改进但具有对数比较数的二进制搜索是有意义的。例如,如果您有一个复杂对象的排序链表,需要磁盘或网络访问才能进行比较,那么使用二分搜索可能比使用线性搜索要好得多。
关于c++ - 为什么 std::binary_search 的参数是前向迭代器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13502128/
前一段时间写过一篇文章《 实战,一个高扩展、可视化低代码前端,详实、完整 》,得到了很多朋友的关注。 其中的逻辑编排部分过于简略,不少朋友希望能写一些关于逻辑编排的内容,本文就详细讲述一下逻辑
我正在尝试以下 Java 片段: int[] testArray={10,20,30,40}; int i= 0; testArray[i++]= testArray[i++]+1; System.o
我想知道我是否可以通过某种方式在 C++ 中进行前/后函数调用。我有一个包含很多函数的包装器类,在每次调用包装器函数后,我应该调用另一个始终相同的函数。 所以我不想像这样对每个函数调用 postFun
我有一个像这样的头文件: #pragma once #include "gamestate.h" #include "ExitListener.h" class InitialGameState :
学习左值和右值。定义是任何可以是“地址”的东西都是左值,否则就是右值。 我检查了运算符的优先级,前缀和后缀增量都比“地址”运算符具有更高的优先级。 对于下面的两个例子,谁能解释一下为什么第一个“&++
在我的学习过程中,我遇到了前后迭代器,我想知道是否有办法让它们就地创建容器元素。从文档来看,容器似乎需要实现 push_back 函数才能与 back_iterator 一起使用。但是有没有一种方法可
我有两个关于 Java 中运算符优先级的类似问题。 第一个: int X = 10; System.out.println(X++ * ++X * X++); //it prints 1440 根据
请放轻松,不要对我开枪,因为我还是新手。 当我运行这段代码时,我完全糊涂了,终生无法弄清楚为什么: int y = 9; cout << "++y = " << ++y << "\n--y = " <
两种表达方式有区别吗: (*x)++ 和 ++(*x) 我可以看到这两个语句都替换了 *x 中 (*x+1) 的内容。但是它们之间有什么区别吗? 最佳答案 (*x)++ 计算为*x的值;作为副作用,*
我有一个如下所示的数据集: Date CONSUMER DISCR CONSUMER STAPLES ENERGY FINANCIALS HEALTH CARE
我希望检查名称字段中输入的前两个字符是否为字母 - 除此之外没有什么区别(空格、'、- 等都是公平的游戏)。这是我到目前为止所拥有的,但它不起作用。想法?谢谢! if (document.form01
我制作了一个简单的脚本,为像素和所有附近的像素着色为相同的颜色 Click foto
我需要编写一个循环,以下列格式输出从昨天算起的最近 30 天: 2014-02-02 2014-02-03 2014-02-04 ... 2014-03-04 我想我需要像这样使用循环: for ($
我正在做一些练习,但我对这个感到困惑: public static int f (int x, int y) { int b=y--; while (b>0) { if (x%2!=0
我需要一个 4 个字符的正则表达式。前 3 个字符必须是数字,最后 1 个字符必须是字母或数字。 我形成了这个,但它不起作用 ^([0-9]{3}+(([a-zA-Z]*)|([0-9]*)))?$
我需要编写一个循环,以下列格式输出从昨天算起的最近 30 天: 2014-02-02 2014-02-03 2014-02-04 ... 2014-03-04 我想我需要像这样使用循环: for ($
我有下面的程序,我试图找到前 1000 个素数的总和。在代码中,解决方案1和2有什么区别?为什么我不应该将 count 变量放在 if 条件之外?如果我把变量放在 if 之外,我显然没有得到我需要的答
这个问题在这里已经有了答案: Replace First N Occurrences in the String (7 个答案) 关闭 4 年前。 我有一个如下的字符串 const str = '_
我正在尝试测量以纳秒为单位的平均访问延迟,但在第一次迭代后我收到“段错误(核心转储)”。我错过了什么吗?我是否滥用了指针。这是导致错误的函数: #include #include #include
我有一个 SQL 问题 (MySQL)。我如何从下表创建一个新表(表名称:“well_master_prod_inj”)。 我需要按井名和日期聚合数据。我希望每个井名只有一行数据以及显示以下数据的列:
我是一名优秀的程序员,十分优秀!