通用可重复值的排序数组的二分法检索

爻易

虽然我不是C粉，但C＋＋是不会比C更快的，除非你C用得不对。

C为了灵活性可能不知数据类型，但程序员如果知道的话，比如这里知道要处理的是整型，就可以明确定义类型，也可用宏及typedef之类方法增加一定的灵活性。

还有此例中传参比较关键字用的是指针（int ＊key），这也降低了比较效率，完全可以用int key；另外也不需要包装比较函数。

不需要多大的修改，就这几点改变:

int CupperBound(int key,int *data,int data_count)
{
int middle,start=0,end=data_count-1,val;
int result=-1;
        if(!data) return -1;
        while(start <= end) {
                middle = start + ((end-start) >> 1);
                if(*data>key)  {
                        if(!middle||(key>=data[middle - 1]))
                                result=middle;
                        end=middle-1;
                } else start=middle+1;
        };
        return result;
}

优化到O2，论运行速度这个C版本就胜过STL版本了

yulihua49

爻易 发表于 2016-11-05 14:23
虽然我不是C粉，但C＋＋是不会比C更快的，除非你C用得不对。

C为了灵活性可能不知数据类型，但程序员如 ...

你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型和复杂比较器的。
我估计复杂类型可能也是stl优，因为它知道类型，可以有针对的优化。只不过优势没那么大。
如果这样，99%的需求它可以解决了。

爻易

yulihua49 发表于 2016-11-05 16:39
你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型 ...

灵活性与效率,由程序员把握

爻易

当要求在大数据量上运行，就需要牺牲灵活性来满足效率。
模板是编译器展开函数，C则是程序员自己来展开函数（宏也有一定展开功能）。

爻易

yulihua49 发表于 2016-11-05 16:39
你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型 ...

复杂类型，C程序员就按整型那样再人肉展开一次。开发效率有点低，但运行效率仍会快于STL

爻易

抱歉，前面贴代码时发现了点错误，重新整理了下

inline int CupperBound(int key,int *data,int data_count)
  {
  int *start=data,*end=data+(data_count-1),*middle;

  if(*end <= key) return data_count;
  while(start < end)
    {
    middle = start + ((end-start) >> 1);
    if(*middle > key) end = middle;
    else start = ++middle;
    }
  return start-data;
  }

yulihua49

爻易 发表于 2016-11-05 21:50
抱歉，前面贴代码时发现了点错误，重新整理了下

inline int CupperBound(int key,int *data,int da ...

你这个是找相等，不是大于。

爻易

yulihua49 发表于 2016-11-05 21:54
你这个是找相等，不是大于。

是大于啊，key=80000时返回值80001,跟你的函数返回值还有stl版本返回值一样的

wlmqgzm

我觉得如果算法的思路上没有变化的话, 那么无论是用C++ std库, 还是自己重新写一遍, 基本上性能都差不多.

关键还是在核心算法的思路上要有突破, 才值得重写std库的代码, 这两天在测试 自己重写的std::unordered_hash库, 主要的变化有几点:
1)去掉了标准算法容器等效于 vector<list<T>>, 改进后的算法 容器等效于boost::circular_buffer<T>, 由于有更好的cache依存性, 在多数情况下性能会更好
2)算法中容器默认为2的倍数, 每次都按照2的倍数扩展或者减少, 这样去掉了消耗资源多的除法运算, 用&代替, hash值的匹配更快速
3)rehash的改进: 将rehash中copy T过程, 对于旧容器进行依次pop, 及时释放内存, Copy一个释放一个, 而不是一次性释放, 减少了rehash过程中的内存占用.
4)删除中添加检测并 自动rehash, 及时减少内存占用.
5)hash值的缓存, 将每个Key的hash缓存下来,多占用4个字节, 但是rehash的时候就不用重新计算了, 提高了insert性能.

总体上内存占用率下降20%以上, 综合性能提高70%以上.

wlmqgzm

以下为测试情况:

guo@guo-desktop:/mnt/guo/newcpp/hash_map/bin/Release$ ./hash_map
TEST_COUNT=10000000, std::unordered_map<std::string, std::shared_ptr<std::string> >   map1;  // 依次为insert , find , delete的花费时间,

6.076009s wall, 5.880000s user + 0.180000s system = 6.060000s CPU (99.7%)

3.253689s wall, 3.250000s user + 0.000000s system = 3.250000s CPU (99.9%)

4.088779s wall, 4.080000s user + 0.000000s system = 4.080000s CPU (99.8%)

Log: Time=2016-11-06T19:17:10.074099, Line=75, File="/mnt/guo/newcpp/hash_map/main.cpp", Func="test_myhash", Msg="Circular_hash_map    map2"

3.652572s wall, 3.610000s user + 0.050000s system = 3.660000s CPU (100.2%)

2.086055s wall, 2.080000s user + 0.000000s system = 2.080000s CPU (99.7%)

3.389029s wall, 3.360000s user + 0.030000s system = 3.390000s CPU (100.0%)   // 主要是delete中  多次rehash回收了内存, 如果去掉rehash,速度会更快