更有效地压平和压缩阵列

在很多情况下,我们需要对数组执行两个或更多不同的操作,如flatten和compact.

some_array.flatten.compact

我担心的是它将遍历数组两次.有更有效的方法吗？

我实际上认为这是一个很好的问题.但首先,为什么大家都不太关心这个？这是表现flatten和flatten.compact比较:

这是我用来生成此图表的代码,以及包含内存的代码.

希望现在你明白为什么大多数人都不会担心:这只是你在flatten用a 组成a时添加的另一个常数因素compact,或许它至少在理论上是有价值的:我们怎样才能减少这个中间体的时间和空间结构体？再次,渐近不是超级有价值,但好奇地想一想.

据我所知,你不能通过以下方式做到这一点flatten:

在查看源代码之前,我希望flatten可以采用这样的方式:

[[3, [3, 3, 3]], [3, [3, 3, 3]], [3, [3, 3, 3]], nil].flatten {|e| e unless e.nil? }

虽然没有骰子.我们将此作为回报:

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, nil]

这很奇怪,因为它基本上将块作为无操作方式抛弃.但它对消息来源有意义.flattenRuby核心中使用的C方法没有参数化以获取块.

Ruby源代码中的过程对我来说有点奇怪(我不是C程序员)但它基本上做了深度优先搜索.它正在使用一个堆栈,它将每个新的嵌套数组添加到它遇到的进程中.(当没有剩下时它终止.)我没有正式计算,但它让我猜测复杂性与DFS相同.

所以源代码可能已被编写,如果传入一个块,允许额外的设置,这可以工作.但没有它,你就会受到(小)性能的影响!