[ruby-core:93218] [Ruby trunk Misc#15925] Speed up SortedSet#min, #max, #sum etc.?

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:[e-mail]?subject=3Dunsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>