A pitfall of the Ruby Range class 2009-11-05


I tweeted about this, but figured it deserve a more lasting treatment.

If you've ever used Range#min or Range#max you may have inadvertently slowed your code significantly.

Both of those ought to be O(1) - constant time. After all, a Range in Ruby consist of two values, and though you can't be assured whether or not the first one or the last one is the smallest/biggest one, the obvious implementation is this:


    def min
      first  last ? first : last
    end

.. and the equivalent one for Range#max. Except that's not what happens, as you can easily convince yourself by doing:


    $ irb
    irb(main):001:0> (1..10000000).max
    => 10000000
    irb(main):002:0>

... and see how slow it is. Eww. The explanation is that min/max are only provided in generic versions that iterate over the full Range (so that the same implementation also works on other collections).

If your app, like mine, frequently needs the smallest or greatest value in a Range, it may be time to monkey patch:


    class Range
      def min
        first  last ? first : last
      end
          
      def max
        first >= last ? first : last
      end
    end
    

For the app that made me notice this problem, adding the above monkey patch caused a 30% speedup. Of course, if most of your ranges are small, or you don't use Range#min or Range#max anywhere, you may not notice any difference at all.


blog comments powered by Disqus