8000 Makes Range#sum an O(1) operation instead of an O(n) one. · scala/scala@db7bd31 · GitHub
[go: up one dir, main page]
Skip to content

Commit db7bd31

Browse files
socsoc
committed
Makes Range#sum an O(1) operation instead of an O(n) one.
Partially fixes SI-4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation.
1 parent 947797e commit db7bd31

File tree

3 files changed

+128
-0
lines changed

3 files changed

+128
-0
lines changed

‎src/library/scala/collection/immutable/Range.scala

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,13 @@ extends collection.AbstractSeq[Int]
211211

212212
final def contains(x: Int) = isWithinBoundaries(x) && ((x - start) % step == 0)
213213

214+
final override def sum[B >: Int](implicit num: Numeric[B]): Int = {
215+
val len = length
216+
if (len == 0) 0
217+
else if (len == 1) head
218+
else (len.toLong * (head + last) / 2).toInt
219+
}
220+
214221
override def toIterable = this
215222

216223
override def toSeq = this

‎test/files/run/t4658.check

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
Ranges:
2+
1073741824
3+
1073741824
4+
0
5+
0
6+
55
7+
25
8+
1
9+
-45
10+
-55
11+
0
12+
-24
13+
-30
14+
0
15+
-40
16+
-55
17+
-10
18+
-24
19+
-30
20+
-10
21+
IntRanges:
22+
Disabled #1
23+
Disabled #2
24+
0
25+
0
26+
55
27+
25
28+
1
29+
-45
30+
-55
31+
0
32+
-24
33+
-30
34+
0
35+
-40
36+
-55
37+
-10
38+
-24
39+
-30
40+
-10
41+
LongRanges:
42+
Disabled #1
43+
Disabled #2
44+
0
45+
0
46+
55
47+
25
48+
1
49+
-45
50+
-55
51+
0
52+
-24
53+
-30
54+
0
55+
-40
56+
-55
57+
-10
58+
-24
59+
-30
60+
-10
61+
BigIntRanges:
62+
Disabled #1
63+
Disabled #2
64+
0
65+
0
66+
55
67+
25
68+
1
69+
-45
70+
-55
71+
0
72+
-24
73+
-30
74+
0
75+
-40
76+
-55
77+
-10
78+
-24
79+
-30
80+
-10

‎test/files/run/t4658.scala

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
import scala.collection.immutable.NumericRange
2+
//#4658
3+
object Test {
4+
5+
case class R(start: Int, end: Int, step: Int = 1, inclusive: Boolean = true)
6+
7+
val rangeData = Array(
8+
R(1, Int.MaxValue), R(-Int.MaxValue, -1), R(0, 0), R(0,0, inclusive = false), R(1,10),
9+
R(1,10,2), R(1,10,11), R(-10, -5), R(-10, 0), R(-10, 10), R(-10, -5, 2), R(-10, 0, 2), R(-10, 10, 2),
10+
R(-10, -5, inclusive = false), R(-10, 0, inclusive = false), R(-10, 10, inclusive = false),
11+
R(-10, -5, 2, inclusive = false), R(-10, 0, 2, inclusive = false), R(-10, 10, 2, inclusive = false)
12+
)
13+
14+
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)
15+
16+
def numericIntRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(r.start, r.end, r.step) else NumericRange(r.start, r.end, r.step))
17+
18+
def numericLongRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(r.start.toLong, r.end, r.step) else NumericRange(r.start.toLong, r.end, r.step))
19+
20+
def numericBigIntRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(BigInt(r.start), BigInt(r.end), BigInt(r.step)) else NumericRange(BigInt(r.start), BigInt(r.end), BigInt(r.step)))
21+
22+
def main(args: Array[String]) {
23+
// We drop the first two tests for all ranges which don't have a decent sum implementation,
24+
// because it is just too slow.
25+
println("Ranges:")
26+
ranges.foreach{range => println(range.sum)}
27+
println("IntRanges:")
28+
println("Disabled #1")
29+
println("Disabled #2")
30+
numericIntRanges.drop(2).foreach{range => println(range.sum)}
31+
println("LongRanges:")
32+
println("Disabled #1")
33+
println("Disabled #2")
34+
numericLongRanges.drop(2).foreach{range => println(range.sum)}
35+
println("BigIntRanges:")
36+
println("Disabled #1")
37+
println("Disabled #2")
38+
numericBigIntRanges.drop(2).foreach{range => println(range.sum)}
39+
}
40+
41+
}

0 commit comments

Comments
 (0)
0