通用可重复值的排序数组的二分法检索
本帖最后由 yulihua49 于 2016-10-27 14:40 编辑造了个轮子哈。因为没有这样的轮子。系统提供一个二分法，只能处理无重复值的，而且没提供不等式查找，
#include <Binary_search.h>
// =key
int lowerBound(void *key,void *data,int data_count,int (*compare)(void *key,void *data,int n))
{
int middle,start=0,end=data_count-1,val;
if(!key||!data) return -1;
while (start <= end) {
middle = start + ((end-start) >> 1);
val=compare(key,data,middle); //data - key
if (!val && (!middle||compare(key,data,middle - 1) < 0)) return middle;
if (val>=0) end = middle - 1;
else start = middle + 1;
}
return -1;//不存在
}
// >key
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;
}
本帖最后由 yulihua49 于 2016-10-27 14:47 编辑
yulihua49 发表于 2016-10-27 14:04
#include
// =key
int lowerBound(void *key,void *data,int data_count,int (*compare)(void *key,void ...
那个.h无关紧要，就是这两个函数的原型。
lowerBound查找指定KEY等值元素下标最小的一个。返回找到的下标号，0开始。找不到返回-1；
upperBound查找>KEY的下标最小的一个。返回找到的下标号，0开始。找不到返回-1
lowerBound和upperBound确定了重复元素的上下界。
由于是通用算法，函数并不知道key和data具体的数据类型（一般二者类型相同），只能以void表示之。
需要使用者提供比较函数compare，在这个函数里按照你自己的数据结构和需求进行比较。
data>key 返回正数，=返回0，<返回负数。
其他需求，如>=,<=,<,等等可以用这两个函数组合出来：
// <key的最后元素
int less_than(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
{
int ret;
if(0>(ret=lowerBound(key,data,data_siz,cmp)) &&
0>(ret=upperBound(key,data,data_siz,cmp))) {
ret=data_siz;
}
return --ret;
}
// <=key的最后元素
int less_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
{
int ret;
if(0>(ret=upperBound(key,data,data_siz,cmp)))
ret=data_siz;
return --ret;
}
// >=key的第一个元素
int great_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
{
int ret;
return (ret=lowerBound(key,data,data_siz,cmp))>=0?ret:
upperBound(key,data,data_siz,cmp);
}
这套函数也可以处理无重复数组，只是效率偏低，基本函数每个节点进行2次比较，派生函数多达4次。
所以还有一套针对无重复值排序数组的函数，每个节点只比较1次。
std::multimap用值做key，除了使用不连续内存并且内存要多用一些，可以满足需要吧 本帖最后由 yulihua49 于 2016-10-28 10:47 编辑
cokeboL 发表于 2016-10-27 21:57
std::multimap用值做key，除了使用不连续内存并且内存要多用一些，可以满足需要吧
1.有的应用是用的数组，把数据库的一些表经过order by调入内存，在内存进行快速检索。
2.二者的性能，你可以测一下（百万级数据）。我感觉要差很多。
3.有的应用是C，而不是C++。
当然multimap有很多好处，尤其是动态性。
2.解释下，multimap是红黑树，不是完全平衡的，检索路径较长。不等式的运算需要迭代（寻找相邻节点），在树里迭代要比数组下标迭代效率差很多，最多要爬两倍的深度。
如： if(!middle||compare(key,data,middle - 1) <= 0)；；；；就是个相当吃力的操作。
我在做一个项目时，就是优化一个运算，原来处理400万数据用11小时，纯计算，使用STL。
把STL（主要就是multimap）全部搞掉，用自己的轮子，在相同的系统上时间缩短到半小时。
回复 4# yulihua49
我在做一个项目时，就是优化一个运算，原来处理400万数据用11小时，纯计算，使用STL。
把STL（主要就是multimap）全部搞掉，用自己的轮子，在相同的系统上时间缩短到半小时。
看错了，还以为是缩短半小时 恩，极端情况stl是不适合的
话说，golang里的map只有一种，是hash实现的，好想golang能像c++一样分成map 和unordermap分别提供红黑树和hash实现的 本帖最后由 yulihua49 于 2016-10-31 10:42 编辑
cokeboL 发表于 2016-10-30 11:37
恩，极端情况stl是不适合的
话说，golang里的map只有一种，是hash实现的，好想golang能像c++一样分成map ...
如果从1秒优化到0.1秒，你可能不介意。但是从10小时到1小时，谁都不能忽视了。
hash就不能实现不等式查找了。
其他的，你可以自己实现啊。其实这个二分法与二叉树的实现是类似的。你可以研究下改成二叉树。语言不同不是问题。
还是给你个二叉树的吧，供参考：
T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len))
{
while(sp) {
//rc=sp-key
int rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec);
if(!rc) return sp;
if(rc<=0) sp=sp->Right;
else sp=sp->Left;
}
return NULL;
}
//返回>key的节点
T_Tree * BB_Tree_GT(T_Tree *sp,void *content_key,int len,
int (*Cmp_rec)(void *s1,void *s2,int len))
{
T_Tree *t=NULL;
while(sp) {
int rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec);
if(rc<=0) sp=sp->Right;
else {
t=sp;
sp=sp->Left;
}
}
return t;
}
这个等效于map。
不过我改了下，stl的lowerbound是>=。我认为=是最常用的，要保证他的高性能，所以作为基本函数，其他的可以派生。
本帖最后由 yulihua49 于 2016-11-01 12:31 编辑
cokeboL 发表于 2016-10-27 21:57
std::multimap用值做key，除了使用不连续内存并且内存要多用一些，可以满足需要吧
百万数据，平衡树要20层。红黑树最多40层。寻找相邻节点，最多要爬80层楼。相对于数组：array[++i],开销大多少？说10倍20倍不过分吧？说STL性能低的，我大概是第一个。
不等式的用途：利率问题。
已知某日（存款的结束日期），找到比他小的最后一个利率记录。要想找到他的整个生命期的利率变化情况，只需不断迭代（－－），直到存入日期时的利率。
回复 8# yulihua49
二分法的复杂度同样是O(lgN)，和树是一样的。
如果对于一坨固定的数据，当然有序数组比树要强，Cache亲和性这点就好很多了。其实++i和q = q->left or q = q->right，后者的指令也复杂不了太多
但是假如说：如果要支持数据的插入和删除，数组就太麻烦了，是不是还需要把构造有序数组这个时间给计算进来？
我觉得unorderd_multimap最快了，如果有不满足需求的地方，可以采用两种组织方式，各取所需
std::binary_search不就行了，干吗要重新造轮子？