虽然我不是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))
result=middle;
end=middle-1;
} else start=middle+1;
};
return result;
}
优化到O2，论运行速度这个C版本就胜过STL版本了:victory:
本帖最后由 yulihua49 于 2016-11-05 16:50 编辑
爻易 发表于 2016-11-05 14:23
虽然我不是C粉，但C＋＋是不会比C更快的，除非你C用得不对。
C为了灵活性可能不知数据类型，但程序员如 ...
你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型和复杂比较器的。
我估计复杂类型可能也是stl优，因为它知道类型，可以有针对的优化。只不过优势没那么大。
如果这样，99%的需求它可以解决了。
本帖最后由 爻易 于 2016-11-05 17:05 编辑
yulihua49 发表于 2016-11-05 16:39
你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型 ...
灵活性与效率,由程序员把握
本帖最后由 爻易 于 2016-11-05 17:15 编辑
当要求在大数据量上运行，就需要牺牲灵活性来满足效率。
模板是编译器展开函数，C则是程序员自己来展开函数（宏也有一定展开功能）。
yulihua49 发表于 2016-11-05 16:39
你这个只能处理整型数组。要做成任意类型的，当用于整型时效率就不最高了。
如果有时间，我试试复杂类型 ...
复杂类型，C程序员就按整型那样再人肉展开一次。开发效率有点低，但运行效率仍会快于STL:emn16:
抱歉，前面贴代码时发现了点错误，重新整理了下:hug:
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;
}
爻易 发表于 2016-11-05 21:50
抱歉，前面贴代码时发现了点错误，重新整理了下
inline int CupperBound(int key,int *data,int da ...
你这个是找相等，不是大于。
yulihua49 发表于 2016-11-05 21:54
你这个是找相等，不是大于。
是大于啊，key=80000时返回值80001,跟你的函数返回值还有stl版本返回值一样的
我觉得如果算法的思路上没有变化的话, 那么无论是用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 于 2016-11-06 20:26 编辑
以下为测试情况:
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,速度会更快