Issue #15925 has been updated by janosch-x (Janosch M=FCller). jeremyevans0 (Jeremy Evans) wrote: > Your recommended implementation greatly improves performance. = I fear this benchmark result "over-idealizes" the performance improvements = because `SortedSet#to_a` is memoized [here](https://github.com/ruby/ruby/bl= ob/afd68cd87114fb49158462f1594cacfd2b765e9b/lib/set.rb#L781-L784) on the fi= rst run, and only cleared when set contents are changed. Real world performance improvements should end up between 2x (at most) for = a fresh or modified set (by virtue of avoiding the extra iteration mentione= d in the report), and the results of this benchmark. ---------------------------------------- Misc #15925: Speed up SortedSet#min, #max, #sum etc.? https://bugs.ruby-lang.org/issues/15925#change-78670 * Author: janosch-x (Janosch M=FCller) * Status: Assigned * Priority: Normal * Assignee: knu (Akinori MUSHA) ---------------------------------------- this issue is somewhat similar to https://bugs.ruby-lang.org/issues/15807 current situation, using the example of `SortedSet#min` (without `rbtree`): - `SortedSet#min` calls `Enumerable#min` - `Enumerable#min` calls `SortedSet#each` - `SortedSet#each` calls `SortedSet#to_a` - `#to_a` returns an `Array` which is guaranteed to be sorted - `Enumerable#min` wastefully goes through this whole `Array` anyway so complexity can be reduced from O(n) to O(1) for `#min`/`#max`/`#minmax`. other methods may be sped up by delegating to faster implementations on `Ar= ray`. for instance, `SortedSet.new(1..1000).to_a.sum` is an order of magnitude fa= ster than `SortedSet.new(1..1000).sum`. suggestion: ``` class SortedSet < Set # [ ... ] # non-rbtree case # [ ... ] def min to_a.first end def max to_a.last end def minmax [min, max] end def sum to_a.sum end # maybe more? end ``` ---Files-------------------------------- sorted-set-min-max-sum.patch (1.85 KB) -- = https://bugs.ruby-lang.org/ Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=3Dunsubscribe> <http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>