Ruby Ruby 标准库中缺少 rbtree, 严重影响开箱即用,谁能帮忙给核心开发者提议加入 rbtree。

lilijreey · July 28, 2020 · Last by luikore replied at August 03, 2020 · 2622 hits

rbtree 之前 1.9 的时候就有人开发了 patch,到了 2.6 直接被否决了。但是 rbtree 很常用,标准库没有还是很蛋疼的。尤其是设计算法的时候。哪位大佬可以帮忙给核心开发团队提提意见

用 gem 不好吗?进标准库就说明需要 core team 维护,然而 core team 没那么多时间,现在还一直把一部分标准库迁移到 gem 呢。

打编程比赛,没法使用 gem

还有 rbtree 这种做 ROR 一般用不到,但是做其他领域就很常用了。对比一下其他语言基本都有 rbtree 或者类似的容器。 ruby 也应该有。

Java 的 HashMap(8 以后)的链表树化是通过 红黑树实现

Java 的 TreeMap 是通过红黑树实现

Nginx 是用红黑树管理 timer 等

Linux 进程调度用红黑树管理进程控制块

等等……
[ https://zhuanlan.zhihu.com/p/76554186 ]

5 Floor has deleted

事实上,当我们需要一棵特别大的平衡树的时候,我们就用数据库,例如 redis 的 zset

显然也能做管理 timer 等用途……

我觉得平衡树的应用场景被好多基础软件做了,以至于在 Ruby 中并没有什么发挥的空间了

7 Floor has deleted

5 楼这回复 难怪 Rails 在国内越来越衰

我觉得这种类似的提议挺好的。看看人家 Python 的标准库,Ruby 要加油。

Reply to qichunren

python 标准库有红黑树?

rbtree 的 patch 当时一个设计是用来优化 SortedSet 的 hash 实现,但是现在 Ruby 的 hash 在 4 年前就改由 Open Addressing 的方法来实现了([Feature #12142])。这就类似于 Java Spark 里面的 OpenHashMap 了,性能远优于闭散列的实现,自然相关的东西就否决了。

如果是实际的算法用途,我记得很早以前 GSoC 有个 Ruby 的算法相关 gem 的实现。但这东西能不能进标准库,我表示怀疑。不过目前线下的算法比赛,不管是 ACM/ICPC 还是 OI 应该都是不能用 Ruby 的吧。如果是 Codeforces 或者 Leetcode,虽然不能用 gem,但 gem 也就是 require 的 ruby 文件,提前展开一下做成模板就是了。

12 Floor has deleted

需求用到红黑树的,目前只发现交易所的 order book 和 matching。 另外,我所知的很少有语言标准库自带红黑树。

Reply to dsh0416

主要是大部分都是 c 扩展写的。

Reply to Rei

python 也没有,但是其他语言基本都有,再说了现在 ruby 的性能基本已经全面超过 python, 有点志气别老和 python 比。

Ruby 标准库缺的数据结构多了去了,例如 list,double array,burst tree,radix tree,merkle-patricia tree,HAMT,HAT-tree …… 为何厚此薄彼?

我明白红黑树是入门数据结构书讲的,但就一定比别的数据结构有用咩?

Reply to lilijreey

python 是 9 楼提的。

进标准库要有取舍,目前来看引入统一的异步调度机制对 Ruby 更重要(在做了)。

Reply to luikore

其实都加上也不是不可以,为了吸引下一代程序员,就要从打比赛抓起。。

幫你翻譯中文,人家的意思是比賽不能裝 gem 然後這個 gem 做 Rails 開發時比較少在用 而不是比賽時不能用 gem 但可以用 ROR

Reply to ericguo

有道理…… 那我也支持

就差实现性能超过数组 sort 然后 bsearch 了

You need to Sign in before reply, if you don't have an account, please Sign up first.