Scala Programming Language
  1. Scala Programming Language
  2. SI-4658

Range's sum method has O(n) complexity, but should have O(1)

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.8.0, Scala 2.8.1, Scala 2.9.0, Scala 2.9.1
    • Fix Version/s: Scala 2.10.0
    • Component/s: Misc Library
    • Labels:
    • Environment:

      Scala version 2.10.0.r25021-b20110525020223 (OpenJDK 64-Bit Server VM, Java 1.6.0_22)

      Description

      Range doesn't provide a sensible implementation, but uses this one from TraversableOnce:

       def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus) 

      This is probably the worst case algorithm.

      It is possible to provide an algorithm taking constant time for at least step size 1 and probably every other step size, too.

      I just written a quick-and-dirty implementation covering step size 1:

        final def sum: Int = {
          var _end = if (isInclusive) end else end-1
          if (step == 1)
            if(start >= 0)
              -gauss(start-1) + gauss(_end)
            else
              -gauss(-start) + gauss(_end)
          else
            sum()
        }
      
        @inline private def gauss(end: Int) = (end+1)*end/2
      

      NumericRange has the same problem. The same algorithm applies, but with Numeric[T] instead of Int as a type.

        Issue Links

          Activity

          Hide
          Simon Ochsenreither added a comment - - edited

          Latest version:

          override def sum[B](implicit num: Numeric[B]): Int = { val len = length; if (len > 0) (len.toLong * (head + last) / 2).toInt else 0 }
          
          Show
          Simon Ochsenreither added a comment - - edited Latest version: override def sum[B](implicit num: Numeric[B]): Int = { val len = length; if (len > 0) (len.toLong * (head + last) / 2).toInt else 0 }
          Hide
          Vincent Foley-Bourgon added a comment -

          I am not very good with mathematics, so somebody is going to have to make sure I haven't made an obvious (or non-obvious) mistake in my reasoning here.

          Consider the finite sequence of integers s[0], s[1], s[2], ..., s[n-1] where s[i] = s[0] + ip for all i in [0, n-1] with p being the step value.

          The sum of this sequence is:

          SUM = s[0] + s[1]       + s[2]        + ... + s[n-1]
              = s[0] + (s[0] + p) + (s[0] + 2p) + ... + (s[0] + (n-1)p)
          

          If we double SUM, we get:

          2SUM =   s[0]            + (s[0] + p)      + (s[0] + 2p)     + ... + (s[0] + (n-1)p)
                 + (s[0] + (n-1)p) + (s[0] + (n-2)p) + (s[0] + (n-3)p) + ... + s[0] 
               ---------------------------------------------------------------------------------
               = (2s[0] + (n-1)p) + (2s[0] + (n-1)p) + (2s[0] + (n-1)p) + ... + (2s[0] + (n-1)p)
               = n(2s[0] + (n-1)p)
          

          And therefore, we have:

          SUM = 2SUM/2 = (n(2s[0] + (n-1)p)) / 2
          

          So I went ahead and implemented the code:

          import scala.util.Random
          
          object Sum {
            def sum(range: Range): Long = {
              if (range.isEmpty)
                0
              else {
                val n = range.length
                (n * (2*range.first + (n-1)*range.step)) / 2
              }
            }
          
            def test(n:Int): Option[(String, Int, Int, Int)] = {
              val r = new Random(System.currentTimeMillis)
          
              for (_ <- 0 until n) {
                val start = r.nextInt(2000) - 1000
                val end = r.nextInt(4000) - 1000
                val step = (r.nextInt(10) + 1) * (if (end < start) -1 else 1)
                val rangee = new Range(start, end, step)
                val rangei = new Range.Inclusive(start, end, step)
          
                if (Sum.sum(rangee) != rangee.foldLeft(0L)(_+_))
                  return Some(("Exclusive", start, end, step))
          
                if (Sum.sum(rangei) != rangei.foldLeft(0L)(_+_))
                  return Some(("Inclusive", start, end, step))
              }
              None
            }
          }
          

          The test code seems to work properly. I have not done extensive testing with ScalaCheck however, so there may be problems that I have not sniffed out.

          I hope this helps a little.

          Vincent.

          Show
          Vincent Foley-Bourgon added a comment - I am not very good with mathematics, so somebody is going to have to make sure I haven't made an obvious (or non-obvious) mistake in my reasoning here. Consider the finite sequence of integers s [0] , s [1] , s [2] , ..., s [n-1] where s [i] = s [0] + ip for all i in [0, n-1] with p being the step value. The sum of this sequence is: SUM = s[0] + s[1] + s[2] + ... + s[n-1] = s[0] + (s[0] + p) + (s[0] + 2p) + ... + (s[0] + (n-1)p) If we double SUM, we get: 2SUM = s[0] + (s[0] + p) + (s[0] + 2p) + ... + (s[0] + (n-1)p) + (s[0] + (n-1)p) + (s[0] + (n-2)p) + (s[0] + (n-3)p) + ... + s[0] --------------------------------------------------------------------------------- = (2s[0] + (n-1)p) + (2s[0] + (n-1)p) + (2s[0] + (n-1)p) + ... + (2s[0] + (n-1)p) = n(2s[0] + (n-1)p) And therefore, we have: SUM = 2SUM/2 = (n(2s[0] + (n-1)p)) / 2 So I went ahead and implemented the code: import scala.util.Random object Sum { def sum(range: Range): Long = { if (range.isEmpty) 0 else { val n = range.length (n * (2*range.first + (n-1)*range.step)) / 2 } } def test(n:Int): Option[(String, Int, Int, Int)] = { val r = new Random(System.currentTimeMillis) for (_ <- 0 until n) { val start = r.nextInt(2000) - 1000 val end = r.nextInt(4000) - 1000 val step = (r.nextInt(10) + 1) * (if (end < start) -1 else 1) val rangee = new Range(start, end, step) val rangei = new Range.Inclusive(start, end, step) if (Sum.sum(rangee) != rangee.foldLeft(0L)(_+_)) return Some(("Exclusive", start, end, step)) if (Sum.sum(rangei) != rangei.foldLeft(0L)(_+_)) return Some(("Inclusive", start, end, step)) } None } } The test code seems to work properly. I have not done extensive testing with ScalaCheck however, so there may be problems that I have not sniffed out. I hope this helps a little. Vincent.
          Hide
          Simon Ochsenreither added a comment -

          https://github.com/scala/scala/pull/83

          Makes Range#sum an O(1) operation instead of an O one.

          Partially fixes SI-4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation. </rant>

          Show
          Simon Ochsenreither added a comment - https://github.com/scala/scala/pull/83 Makes Range#sum an O(1) operation instead of an O one. Partially fixes SI-4658 . NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation. </rant>
          Hide
          Simon Ochsenreither added a comment -

          It finally struck me that it is possible to just use the implicit parameter from the constructor instead of the one from the method with `this.num` and use the `Integral` methods as intended.

          This doesn't make Numeric better, but we have a lucky work-around in this situation.

          https://github.com/scala/scala/pull/335

          Show
          Simon Ochsenreither added a comment - It finally struck me that it is possible to just use the implicit parameter from the constructor instead of the one from the method with `this.num` and use the `Integral` methods as intended. This doesn't make Numeric better, but we have a lucky work-around in this situation. https://github.com/scala/scala/pull/335
          Hide
          Paul Phillips added a comment -

          This was incorporated in e593d8b9ed ; I admit I'm mostly relying on you all when it comes to the corner cases, so feel free to double check.

          Show
          Paul Phillips added a comment - This was incorporated in e593d8b9ed ; I admit I'm mostly relying on you all when it comes to the corner cases, so feel free to double check.

            People

            • Assignee:
              Simon Ochsenreither
              Reporter:
              Simon Ochsenreither
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development