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

cokeboL

语言不同，问题很明显的。。。golang语言层之上自己实现的数据结构，就比如红黑树吧，比c++慢的量级在10倍以上，想提速，只能golang内置c/c++汇编的实现，
所以除了c/c++这种，其他语言非内置的数据结构，实现不是大问题，但就是达不到想要的极致性能

另外，连续内存在增删的时候要memmove，也未必划算啊，否则 stl 也差不多够用了

说 stl 慢的人还是挺多的，毕竟通用的东西，特定场景不如专用的，大公司大项目有挺多禁止使用 stl 的

yulihua49

回复 9# lxyscls

其实++i和q = q->left or q = q->right
----------------------------------------------
不是说q->left 低效，而是找相邻节点，不是q->left 就行的，可能要爬楼，最多爬两倍深度，而且边爬边比较。
map的动态性是优势，这个我一开始就说了。
哈希虽然性能好，但是无序，就不能做不等式查询。
我这个帖子的一个意思是在内存数据库里做不等式查询。坛子里有一个说内存KV数据库的。我说一般的KV完不成不等式查找。这里告诉他一个不等式方案，数组的和树的都给了。

yulihua49

cokeboL 发表于 2016-11-02 09:47
语言不同，问题很明显的。。。golang语言层之上自己实现的数据结构，就比如红黑树吧，比c++慢的量级在10倍 ...

stl不仅是慢，而且编译慢，一个系统，大量使用STL，编译就变得巨慢，产生的代码量巨大。
我们使用泛型函数库，函数都编译好入库了，在应用时没有附加的编译开销。
编译速度优于STL，运行速度更是优于STL。

某大神主张编译时泛型处理，认为高效。实际未见得。我的运行时泛型处理，效率更高。

我们公司没有禁止STL。只不过出现性能问题时，再改出来。

lxyscls

yulihua49 发表于 2016-11-02 10:28
回复 9# lxyscls

其实++i和q = q->left or q = q->right

我的意思是：用两套数据结构索引同一套数据

需要不等式比较的时候，就用树；不需要的时候就用Hash

yulihua49

lxyscls 发表于 2016-11-02 10:38
我的意思是：用两套数据结构索引同一套数据

需要不等式比较的时候，就用树；不需要的时候就用Hash

这个可以。

cokeboL

就是因为c/c++编译太慢并且没法解决，pike和c爹才搞golang

http://www.oschina.net/translate ... oftware-engineering

sditmaner

std::multimap用值做key，除了使用不连续内存并且内存要多用一些，可以满足需要吧

yulihua49

sditmaner 发表于 2016-11-02 12:45
std::multimap用值做key，除了使用不连续内存并且内存要多用一些，可以满足需要吧

你跟3楼一模一样，看看其后的解释吧。

yulihua49

cokeboL 发表于 2016-11-02 10:51
就是因为c/c++编译太慢并且没法解决，pike和c爹才搞golang

http://www.oschina.net/translate/go-at-goo ...

这个收了慢慢学习。编译快了，前边11楼你也说了，运行慢。似乎一些算法的实现有效率问题。
解决这个问题的方法是，某种新语言，嵌入C构件。C只做简单的，高性能原子处理。复杂的策略问题由更高级的语言实现。

就是，C完成基本操作，高级语言完成策略。
之前我们是汇编完成操作，C完成策略。

mr_sev

不是有个bsearch？    你咋不把glibc重写一遍？