免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 10335 | 回复: 65

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

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2016-10-27 14:04 |显示全部楼层
本帖最后由 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;
}


论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2016-10-27 14:05 |显示全部楼层
本帖最后由 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,<返回负数。

其他需求,如>=,<=,<,等等可以用这两个函数组合出来:
  1. // <key的最后元素
  2. int less_than(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
  3. {
  4. int ret;
  5.         if(0>(ret=lowerBound(key,data,data_siz,cmp)) &&
  6.            0>(ret=upperBound(key,data,data_siz,cmp))) {
  7.                 ret=data_siz;
  8.         }
  9.         return --ret;
  10. }

  11. // <=key的最后元素
  12. int less_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
  13. {
  14. int ret;
  15.         if(0>(ret=upperBound(key,data,data_siz,cmp)))
  16.                 ret=data_siz;
  17.         return --ret;
  18. }

  19. // >=key的第一个元素
  20. int great_eq(void *key,void *data,int data_siz,int cmp(void *key,void *data,int n))
  21. {
  22. int ret;
  23.         return (ret=lowerBound(key,data,data_siz,cmp))>=0?ret:
  24.                 upperBound(key,data,data_siz,cmp);
  25. }
复制代码

这套函数也可以处理无重复数组,只是效率偏低,基本函数每个节点进行2次比较,派生函数多达4次。
所以还有一套针对无重复值排序数组的函数,每个节点只比较1次。


论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2016-10-27 21:57 |显示全部楼层
std::multimap用值做key,除了使用不连续内存并且内存要多用一些,可以满足需要吧

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2016-10-28 10:24 |显示全部楼层
本帖最后由 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)全部搞掉,用自己的轮子,在相同的系统上时间缩短到半小时。

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2016-10-28 15:39 |显示全部楼层
回复 4# yulihua49

我在做一个项目时,就是优化一个运算,原来处理400万数据用11小时,纯计算,使用STL。
把STL(主要就是multimap)全部搞掉,用自己的轮子,在相同的系统上时间缩短到半小时。

看错了,还以为是缩短半小时

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2016-10-30 11:37 |显示全部楼层
恩,极端情况stl是不适合的

话说,golang里的map只有一种,是hash实现的,好想golang能像c++一样分成map 和unordermap分别提供红黑树和hash实现的

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2016-10-31 10:22 |显示全部楼层
本帖最后由 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就不能实现不等式查找了。
其他的,你可以自己实现啊。其实这个二分法与二叉树的实现是类似的。你可以研究下改成二叉树。语言不同不是问题。
还是给你个二叉树的吧,供参考:


  1. T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
  2.                 int (*Cmp_rec)(void *s1,void *s2,int len))
  3. {
  4.         while(sp) {
  5. //rc=sp-key
  6.                 int rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec);
  7.                 if(!rc) return sp;
  8.                 if(rc<=0) sp=sp->Right;
  9.                 else sp=sp->Left;
  10.         }
  11.         return NULL;
  12. }

  13. //返回>key的节点
  14. T_Tree * BB_Tree_GT(T_Tree *sp,void *content_key,int len,
  15.                 int (*Cmp_rec)(void *s1,void *s2,int len))
  16. {
  17. T_Tree *t=NULL;

  18.         while(sp) {
  19.                 int rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec);
  20.                 if(rc<=0) sp=sp->Right;
  21.                 else {
  22.                         t=sp;
  23.                         sp=sp->Left;
  24.                 }
  25.         }
  26.         return t;
  27. }
复制代码


这个等效于map。
不过我改了下,stl的lowerbound是>=。我认为=是最常用的,要保证他的高性能,所以作为基本函数,其他的可以派生。


论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2016-11-01 12:24 |显示全部楼层
本帖最后由 yulihua49 于 2016-11-01 12:31 编辑
cokeboL 发表于 2016-10-27 21:57
std::multimap用值做key,除了使用不连续内存并且内存要多用一些,可以满足需要吧

百万数据,平衡树要20层。红黑树最多40层。寻找相邻节点,最多要爬80层楼。相对于数组:array[++i],开销大多少?说10倍20倍不过分吧?说STL性能低的,我大概是第一个。
不等式的用途:利率问题。
已知某日(存款的结束日期),找到比他小的最后一个利率记录。要想找到他的整个生命期的利率变化情况,只需不断迭代(--),直到存入日期时的利率。

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2016-11-01 14:11 |显示全部楼层
回复 8# yulihua49

二分法的复杂度同样是O(lgN),和树是一样的。
如果对于一坨固定的数据,当然有序数组比树要强,Cache亲和性这点就好很多了。其实++i和q = q->left or q = q->right,后者的指令也复杂不了太多

但是假如说:如果要支持数据的插入和删除,数组就太麻烦了,是不是还需要把构造有序数组这个时间给计算进来?

我觉得unorderd_multimap最快了,如果有不满足需求的地方,可以采用两种组织方式,各取所需

论坛徽章:
44
15-16赛季CBA联赛之浙江
日期:2021-10-11 02:03:59程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2016-11-01 22:04 |显示全部楼层
std::binary_search不就行了,干吗要重新造轮子?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP