Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
scabug opened this issue May 30, 2011 · 11 comments
Closed

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

scabug opened this issue May 30, 2011 · 11 comments
Assignees
Labels
Milestone

Comments

@scabug
Copy link

@scabug scabug commented May 30, 2011

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.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@soc said:
Just Benchmarked it:

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

One run takes ~ 35 seconds.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 30, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Jun 6, 2011

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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Sep 3, 2011

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Mar 27, 2012

@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

This comment has been minimized.

Copy link
Author

@scabug scabug commented May 3, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.