1 234 5 6 7 / 7 页下一页

[C] 通用可重复值的排序数组的二分法检索 [复制链接]

yulihua49

巨富豪门

论坛徽章:: 15

21楼 [报告]

发表于 2016-11-02 20:55 |只看该作者

本帖最后由 yulihua49 于 2016-11-02 21:00 编辑

mr_sev 发表于 2016-11-02 17:38
不是有个bsearch？你咋不把glibc重写一遍？

你根本没有仔细看。bsearch，支持可重复值吗？支持不等式查找吗？
类似这样的：
1，1，1，2，2，4，4，4，5，6，6，7，8，9，9，9，，，，，，
为key定上下界，避免线性查找。
脑子里能不能多考虑下实际需求。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yulihua49

巨富豪门

论坛徽章:: 15

22楼 [报告]

发表于 2016-11-02 21:05 |只看该作者

windoze 发表于 2016-11-01 22:04
std::binary_search不就行了，干吗要重新造轮子？

mr_sev 发表于 2016-11-02 17:38
不是有个bsearch？你咋不把glibc重写一遍？

你根本没有仔细看。bsearch，支持可重复值吗？支持不等式查找吗？
类似这样的：
1，1，1，2，2，4，4，4，5，6，6，7，8，9，9，9，，，，，，
为key定上下界，避免线性查找。
你不应该问这问题啊，老鸟了，这需求应该见过啊。能满足需求的就是multimap，太慢。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

windoze

版主

论坛徽章:: 44

23楼 [报告]

发表于 2016-11-02 22:28 |只看该作者

本帖最后由 windoze 于 2016-11-02 22:30 编辑

回复 22# yulihua49

STL里就有upper_bound和lower_bound，和你写的这两个函数的功能一模一样，速度还要快一点……
比如你要在一个排好序的数组里找小于等于n的最大的数字：

std::vector<int> seq{1，1，1，2，2，4，4，4，5，6，6，7，8，9，9，9};
int n=6;
auto i=std::upper_bound(seq.begin(), seq.end(), n);
// 现在i指向7
if(i==seq.begin()) {
// 没找到，整个seq都比n大
} else {
i--;
// 现在i就指向第二个6
}

复制代码

时间复杂度一样是O(log(N))，lower_bound类似，不过是反过来的。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

windoze

版主

论坛徽章:: 44

24楼 [报告]

发表于 2016-11-02 23:10 |只看该作者

本帖最后由 windoze 于 2016-11-02 23:20 编辑

刚才做了一个micro benchmark，代码如下：

#include <chrono>
#include <iostream>
#include <algorithm>
constexpr size_t len=100000;
int test_data[len];
size_t garbage;
void generate_test_data() {
for(size_t i=0; i<len; i++) {
test_data[i]=i;
}
}
int upperBound(void *key,void *data,int data_count,int (*compare)(void *key,void *data,int n))
{
int middle,start=0,end=data_count-1,val;
int result=-1;
if(!key||!data) return -1;
while(start <= end) {
middle = start + ((end-start) >> 1);
val=compare(key,data,middle);
if(val>0) {
if(!middle||compare(key,data,middle - 1) <= 0)
result=middle;
end=middle-1;
} else start=middle+1;
};
return result;
}
int cmp(void *key, void *data, int n) {
return ((int *)data)[n]-*((int *)key);
}
void test1() {
// Find the last element smaller than 80000 in test_data
int key=80000;
// Make sure this is not optimized;
garbage+=upperBound(&key,test_data,len,cmp)-1;
}
struct cmp_stl {
bool operator()(int a, int b) const { return a<b; }
};
void test2() {
// Find the last element smaller than 80000 in test_data
// Make sure this is not optimized;
garbage+=std::upper_bound(test_data, test_data+len, 80000, cmp_stl())-test_data-1;
}
void time_it(size_t repeat, void(*f)()) {
auto start=std::chrono::system_clock::now();
for(size_t i=0; i<repeat; i++) {
f();
}
auto end=std::chrono::system_clock::now();
std::cout << "Duration: " << (end-start).count() << std::endl;
}
int main() {
generate_test_data();
// Warm up
for(size_t i=0; i<100; i++) {
test1();
test2();
}
std::cout << "Test1 ";
time_it(100000, test1);
std::cout << "Test2 ";
time_it(100000, test2);
}

复制代码

用O3优化：
Test1 Duration: 3038
Test2 Duration: 2581
STL比你的代码快15%

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yulihua49

巨富豪门

论坛徽章:: 15

25楼 [报告]

发表于 2016-11-03 11:03 |只看该作者

本帖最后由 yulihua49 于 2016-11-03 11:22 编辑

windoze 发表于 2016-11-02 23:10
刚才做了一个micro benchmark，代码如下：

./stl_test
Binary Duration: 40821
MAP Duration: 60072
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 26527
MAP Duration: 67755
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 34094
MAP Duration: 68970
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 45728
MAP Duration: 45947
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 38153
MAP Duration: 65282
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 37609
MAP Duration: 63948
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 36992
MAP Duration: 66479

复制代码

在我这里编译一下。很奇怪，运行时间不稳定，但总的来说，Binary比较快。时间单位是微秒。

./stl_test
Binary Duration: 34061
MAP Duration: 73334
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 33392
MAP Duration: 73889
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 40846
MAP Duration: 68421

复制代码

知道原因了，系统有别的任务在运行。

#include <datejul.h>
#include <iostream>
#include <algorithm>
#define len 100000
int test_data[len];
size_t garbage;
void generate_test_data() {
for(size_t i=0; i<len; i++) {
test_data[i]=i;
}
}
int upperBound(void *key,void *data,int data_count,int (*compare)(void *key,void *data,int n))
{
int middle,start=0,end=data_count-1,val;
int result=-1;
if(!key||!data) return -1;
while(start <= end) {
middle = start + ((end-start) >> 1);
val=compare(key,data,middle);
if(val>0) {
if(!middle||compare(key,data,middle - 1) <= 0)
result=middle;
end=middle-1;
} else start=middle+1;
};
return result;
}
int cmp(void *key, void *data, int n) {
return ((int *)data)[n]-*((int *)key);
}
void test1() {
// Find the last element smaller than 80000 in test_data
int key=80000;
// Make sure this is not optimized;
garbage+=upperBound(&key,test_data,len,cmp)-1;
}
struct cmp_stl {
bool operator()(int a, int b) const { return a<b; }
};
void test2() {
// Find the last element smaller than 80000 in test_data
// Make sure this is not optimized;
garbage+=std::upper_bound(test_data, test_data+len, 80000, cmp_stl())-test_data-1;
}
void time_it(size_t repeat, void(*f)()) {
// auto start=std::chrono::system_clock::now();
INT64 now=now_usec();
for(size_t i=0; i<repeat; i++) {
f();
}
// auto end=std::chrono::system_clock::now();
std::cout << "Duration: " << INTERVAL(now) << std::endl;
}
int main() {
generate_test_data();
// Warm up
for(size_t i=0; i<100; i++) {
test1();
test2();
}
std::cout << "Binary ";
time_it(100000, test1);
std::cout << "MAP ";
time_it(100000, test2);
}

复制代码

程序改了一点点，有的地方编译不过去。

那个好像不是stl里的map，就是数组的，所以没有爬楼开销。

man upper_bound
没有 upper_bound 的手册页条目

居然有这个函数，学习了。在哪里能找到这组函数的说明？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yulihua49

巨富豪门

论坛徽章:: 15

26楼 [报告]

发表于 2016-11-03 11:33 |只看该作者

本帖最后由 yulihua49 于 2016-11-03 11:37 编辑

yulihua49 发表于 2016-11-03 11:03
在我这里编译一下。很奇怪，运行时间不稳定，但总的来说，Binary比较快。时间单位是微秒。
知道原因了， ...

又改了下，带重复值的：
./stl_test
Binary Duration: 44759,N=80009
MAP Duration: 54602,N=80009
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 30905,N=80009
MAP Duration: 59491,N=80009
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 34123,N=80009
MAP Duration: 58152,N=80009
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 38281,N=80009
MAP Duration: 50799,N=80009
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 37987,N=80009
MAP Duration: 60669,N=80009

<p>void generate_test_data() {
for(size_t i=0; i<len; i++) {
test_data[i]=i/10;
}
}

复制代码

key改为8000.

尽管双方都是数组，还是我的快。

原来我不知有数组算法，只知有multimap的算法。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

爻易

家境小康

论坛徽章:: 6

27楼 [报告]

发表于 2016-11-03 11:50 |只看该作者

创新轮子也是从重复造轮子起步的，坚持博采众长地自主开发，就能不断进步，比肩大师甚至超越，一切皆有可能

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

windoze

版主

论坛徽章:: 44

28楼 [报告]

发表于 2016-11-03 12:55 |只看该作者

本帖最后由 windoze 于 2016-11-03 12:57 编辑

回复 26# yulihua49

你肯定没开优化对吧，开O2的时候STL就已经比你的代码快了。另外你说编译不过的那两行代码是C++11的，用-std=c++11就能编译过了。
std::upper_bound的代码和你写的差不多，不是map，都是数组，但是不用函数指针可以让代码inline的更激进一点。
文档你可以在 http://en.cppreference.com/w/ 上看，C和C++的都有。