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

scabug · 2011-05-30T14:59:31Z

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.

The text was updated successfully, but these errors were encountered:

scabug · 2011-05-30T14:59:31Z

Imported From: https://issues.scala-lang.org/browse/SI-4658?orig=1
Reporter: @soc
Affected Versions: 2.8.0, 2.8.1, 2.9.0, 2.9.1

scabug · 2011-05-30T16:03:39Z

@soc said:
Just Benchmarked it:

1 to Int.MaxValue sum   34,476000
sum(1, Int.MaxValue)     0,000000

One run takes ~ 35 seconds.

scabug · 2011-05-30T18:02:57Z

@dcsobral said:
I wonder why such complex implementation? Why isn't the trivial implementation below enough?

def sum[B >: A](implicit num: Numeric[B]): B = (length.toLong * (head + last) / 2).toInt

scabug · 2011-05-30T18:41:29Z

@soc said:
I imagined that abstracting over the step size would be more approachable from my code, but it really is just some proof-of-concept and your code looks much nicer indeed.

One difference is there, though: "Overflow compatibility" (== returning the same wrong "results" like the original code). Not sure if that is required, though...

scabug · 2011-05-30T19:33:29Z

@soc said (edited on Aug 26, 2011 10:02:12 AM UTC):
Just checked. It seems without toLong the results are the same, but I guess with toLong the results have a better chance at being correct. Just wondering how the implementation in NumericRange would look like ...

I found one problem:

It throws an exception for things like 1 to -1, the original did not. No idea what's more correct.

java.util.NoSuchElementException: next on empty iterator
	at scala.collection.Iterator$$anon$3.next(Iterator.scala:28)
	at scala.collection.Iterator$$anon$3.next(Iterator.scala:26)
	at scala.collection.IndexedSeqLike$Elements.next(IndexedSeqLike.scala:63)
	at scala.collection.IterableLike$class.head(IterableLike.scala:90)
	at scala.collection.immutable.Range.head(Range.scala:43)
	at .sum2(<console>:20)
	at .<init>(<console>:22)
	at .<clinit>(<console>)
	at .<init>(<console>:11)
	at .<clinit>(<console>)
	at $export(<console>)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:616)
	at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:593)
	at scala.tools.nsc.interpreter.IMain$Request$$anonfun$10.apply(IMain.scala:831)
	at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
	at scala.tools.nsc.io.package$$anon$2.run(package.scala:31)
	at java.lang.Thread.run(Thread.java:679)

No idea where there is an Iterator involved ...

scabug · 2011-05-30T20:17:17Z

@soc said (edited on Aug 26, 2011 10:02:56 AM UTC):
Tests:

run/t4658.scala

import scala.collection.immutable.NumericRange
//#4658
object Test {

  case class R(start: Int, end: Int, step: Int = 1, inclusive: Boolean = true)

  val rangeData = Array(
    R(1, Int.MaxValue), R(0, Int.MaxValue), R(0, 0), R(0,0, inclusive = false), R(1,10), R(1,10,2), R(1,10,11),
    R(-Int.MaxValue, -1), R(-10, -5), R(-10, 0), R(-10, 10), R(-10, -5, 2), R(-10, 0, 2), R(-10, 10, 2),
    R(-10, -5, inclusive = false), R(-10, 0, inclusive = false), R(-10, 10, inclusive = false),
    R(-10, -5, 2, inclusive = false), R(-10, 0, 2, inclusive = false), R(-10, 10, 2, inclusive = false)
  )

  def ranges = rangeData.map(r =>  if (r.inclusive) r.start to r.end by r.step else r.start until r.end by r.step)

  def numericIntRanges = rangeData.map(r => if (r.inclusive) NumericRange(r.start, r.end, r.step) else NumericRange.inclusive(r.start, r.end, r.step))

  def numericLongRanges = rangeData.map(r => if (r.inclusive) NumericRange(r.start.toLong, r.end, r.step) else NumericRange.inclusive(r.start.toLong, r.end, r.step))

  def numericBigIntRanges = rangeData.map(r => if (r.inclusive) NumericRange(BigInt(r.start), BigInt(r.end), BigInt(r.step)) else NumericRange.inclusive(BigInt(r.start), BigInt(r.end), BigInt(r.step)))

  def main(args: Array[String]) {
    ranges.foreach{range => println(range.sum)}
    println()
    numericIntRanges.foreach{range => println(range.sum)}
    println()
    numericLongRanges.foreach{range => println(range.sum)}
    println()
    numericBigIntRanges.foreach{range => println(range.sum)}
  }

}

Took too much time to run it to generate the check file, though...

scabug · 2011-05-30T21:28:59Z

@soc said (edited on Aug 26, 2011 10:03:08 AM UTC):
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 }

scabug · 2011-06-06T18:11:25Z

Vincent Foley-Bourgon (gnuvince) said:
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.

scabug · 2011-09-03T19:53:04Z

@soc said:
scala/scala#83

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

Partially fixes #4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation.

scabug · 2012-03-27T18:19:36Z

@soc said:
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.

scala/scala#335

scabug · 2012-05-03T21:08:38Z

@paulp said:
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.

scabug closed this as completed May 3, 2012

scabug added the performance label Apr 7, 2017

scabug added this to the 2.10.0 milestone Apr 7, 2017

scabug assigned soc Apr 7, 2017

scabug mentioned this issue Apr 7, 2017

Parallel sum produces different result from sequential sum #4958

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

scabug commented May 30, 2011 •

edited by retronym

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented Jun 6, 2011

scabug commented Sep 3, 2011

scabug commented Mar 27, 2012

scabug commented May 3, 2012

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

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

Comments

scabug commented May 30, 2011 • edited by retronym

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented May 30, 2011

scabug commented Jun 6, 2011

scabug commented Sep 3, 2011

scabug commented Mar 27, 2012

scabug commented May 3, 2012

scabug commented May 30, 2011 •

edited by retronym