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
Comments
Imported From: https://issues.scala-lang.org/browse/SI-4658?orig=1 |
@soc said: 1 to Int.MaxValue sum 34,476000
sum(1, Int.MaxValue) 0,000000 One run takes ~ 35 seconds. |
@dcsobral said: def sum[B >: A](implicit num: Numeric[B]): B = (length.toLong * (head + last) / 2).toInt |
@soc said: One difference is there, though: "Overflow compatibility" (== returning the same wrong "results" like the original code). Not sure if that is required, though... |
@soc said (edited on Aug 26, 2011 10:02:12 AM UTC): 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 ... |
@soc said (edited on Aug 26, 2011 10:02:56 AM UTC): 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... |
@soc said (edited on Aug 26, 2011 10:03:08 AM UTC): override def sum[B](implicit num: Numeric[B]): Int = { val len = length; if (len > 0) (len.toLong * (head + last) / 2).toInt else 0 } |
Vincent Foley-Bourgon (gnuvince) said: 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. |
@soc said: 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. |
@soc said: This doesn't make Numeric better, but we have a lucky work-around in this situation. |
@paulp said: |
Range doesn't provide a sensible implementation, but uses this one from TraversableOnce:
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:
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: