Project

General

Profile

Misc #15925

Speed up SortedSet#min, #max, #sum etc.?

Added by janosch-x (Janosch Müller) over 1 year ago. Updated over 1 year ago.

Status:
Assigned
Priority:
Normal
[ruby-core:93158]

Description

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 Array.

for instance, SortedSet.new(1..1000).to_a.sum is an order of magnitude faster 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) sorted-set-min-max-sum.patch jeremyevans0 (Jeremy Evans), 06/17/2019 09:25 PM

Also available in: Atom PDF