-
Notifications
You must be signed in to change notification settings - Fork 4
/
ParallelParenthesesBalancing.scala
executable file
·97 lines (82 loc) · 2.65 KB
/
ParallelParenthesesBalancing.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package reductions
import scala.annotation._
import org.scalameter._
import common._
object ParallelParenthesesBalancingRunner {
@volatile var seqResult = false
@volatile var parResult = false
val standardConfig = config(
Key.exec.minWarmupRuns -> 40,
Key.exec.maxWarmupRuns -> 80,
Key.exec.benchRuns -> 120,
Key.verbose -> true
) withWarmer(new Warmer.Default)
def main(args: Array[String]): Unit = {
val length = 100000000
val chars = new Array[Char](length)
val threshold = 10000
val seqtime = standardConfig measure {
seqResult = ParallelParenthesesBalancing.balance(chars)
}
println(s"sequential result = $seqResult")
println(s"sequential balancing time: $seqtime ms")
val fjtime = standardConfig measure {
parResult = ParallelParenthesesBalancing.parBalance(chars, threshold)
}
println(s"parallel result = $parResult")
println(s"parallel balancing time: $fjtime ms")
println(s"speedup: ${seqtime / fjtime}")
}
}
object ParallelParenthesesBalancing {
/** Returns `true` iff the parentheses in the input `chars` are balanced.
*/
def balance(chars: Array[Char]): Boolean = {
def code(ch: Char): Int = ch match {
case '(' => 1
case ')' => -1
case _ => 0
}
@tailrec
def loop(chLs: List[Char], acc: Int = 0): Int = chLs match {
case head::tail if acc >= 0 => loop(tail, acc + code(head))
case _ => acc
}
loop(chars.toList) == 0
}
/** Returns `true` iff the parentheses in the input `chars` are balanced.
*/
def parBalance(chars: Array[Char], threshold: Int): Boolean = {
def traverse(idx: Int, until: Int, arg1: Int, arg2: Int): (Int, Int) = {
if (idx < until) {
chars(idx) match {
case '(' => traverse(idx + 1, until, arg1 + 1, arg2)
case ')' =>
if (arg1 > 0) traverse(idx + 1, until, arg1 - 1, arg2)
else traverse(idx + 1, until, arg1, arg2 + 1)
case _ => traverse(idx + 1, until, arg1, arg2)
}
} else (arg1, arg2)
}
def reduce(from: Int, until: Int): (Int, Int) = {
val size = until - from
if (size > threshold) {
val halfSize = size / 2
val ((a1, a2), (b1, b2)) = parallel(reduce(from, from + halfSize), reduce(from + halfSize, until))
if (a1 > b2) {
// )))((())(( => )))(((
(a1 - b2 + b1) -> a2
} else {
// )))(()))(( => ))))((
b1 -> (b2 - a1 + a2)
}
}
else {
traverse(from, until, 0, 0)
}
}
reduce(0, chars.length) == (0, 0)
}
// For those who want more:
// Prove that your reduction operator is associative!
}