斯坦福算法课的编程题还是挺有挑战的，比如Programming Assignment 4，求SCC，问题的数据集接近80M，除了算法，数据结构和数据类型的选择也要特别细致，否则就跑不出结果。
一个带有编号的证书
完成算法课的编程题和测试题后，斯坦福的Tim Rough Garden会颁发一个带有编号的证书给你，还挺有意思，愉快的奋斗体验。
Programming Assignment 4
先分享Programming Assignment 4的编程，让大家对这门课程有一些有深度的感性认识。因为斯坦福已经将课程由免费课程改为收费课程，所以对是否要花钱完成这个课程大家会有一些犹豫，有一定有深度的感性认识应该能帮助大家形成自己的判断。
题目：
Programming Assignment 4
Download the following text file (right click and select "Save As..."): SCC.txt The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Every row indicates an edge, the vertex label in first column is the tail and the vertex label in second column is the head (recall the graph is directed, and the edges are directed from the first column vertex to the second column vertex). So for example, the 11th row looks liks : "2 47646". This just means that the vertex with label 2 has an outgoing edge to the vertex with label 47646 Your task is to code up the algorithm from the video lectures for computing strongly connected components (SCCs), and to run this algorithm on the given graph.
Enter the sizes of the 5 largest SCCs in the given graph using the fields below, in decreasing order of sizes. So if your algorithm computes the sizes of the five largest SCCs to be 500, 400, 300, 200 and 100, enter 500 in the first field, 400 in the second, 300 in the third, and so on. If your algorithm finds less than 5 SCCs, then enter 0 for the remaining fields. Thus, if your algorithm computes only 3 SCCs whose sizes are 400, 300, and 100, then you enter 400, 300, and 100 in the first, second, and third fields, respectively, and 0 in the remaining 2 fields.
WARNING: This is the most challenging programming assignment of the course. Because of the size of the graph you may have to manage memory carefully. The best way to do this depends on your programming language and environment, and we strongly suggest that you exchange tips for doing this on the discussion forums.
部分数据集图示：
尝试着用Scala按Java设计模式来coding ：
package Algorithms.Ch08_Topo.Version06
object Ch08_TopoMain {
def main(args: Array[String]): Unit = {
//read in
val graph = Client().readVertexPairsV2(
"D:\\SComputer\\study\\myScala\\src\\main\\scala\\Algorithms\\Ch08_Topo\\SCC.txt",
" ")(875714)
//calculate SCC
val scclist: Array[Array[Int]]= MyRun().runSCC(new StrongCCDFSStack(), graph)
//sample top-10
println("top-10: " + scclist.map(_.length).sorted.toList.takeRight(10))
//write result into file
Client().outputText( scclist, "D:\\SComputer\\study\\myScala\\src\\main\\scala\\Algorithms\\Ch08_Topo\\Version06\\result.txt"
)
}
}
package Algorithms.Ch08_Topo.Version06
import java.io.{File, FileWriter}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.io.Source
class Client {
def outputText(scclist: Array[Array[Int]],fileAddress: String): Unit = {
val fileWriter = new FileWriter( fileAddress )
for (scc <- 1 to scclist.length) {
fileWriter.write(s"${scc} ${scclist(scc-1).mkString(" ")}\n")
}
fileWriter.close()
}
// G(V,E), and V={1,2,3,4,...n}
def readVertexPairsV2(fileAddress : String, splitRegex: String)( verticesNumber: Int ):Array[Array[Int]] ={
val localFile = Source.fromFile(fileAddress)
val graph = ArrayBuffer[ArrayBuffer[Int]]()
// initiate graph. graph(vertex)(0) is vertex itself, which should be dealt with carefully.
for(v<- 1 to verticesNumber){graph += ArrayBuffer[Int](v)}
//ETL
for (line <- localFile.getLines()) {
val pair = line.split(splitRegex).map(_.toInt) // pair=(Vertex1, Vertex2); graphIndex = vertex -1
graph(pair(0) - 1) += pair(1)
//print(pair(0)+", ")
}
// close file
localFile.close() //; println(graph)
// return result
graph.toArray.map(_.toArray)
}
def readAdjacentListV2(fileAddress : String, splitRegex: String): Array[Array[Int]] ={
val localFile = Source.fromFile(fileAddress)
val bufferList = ListBuffer[Array[Int]]()
for (line <- localFile.getLines()) {
val list: ListBuffer[Int] = ListBuffer[Int]()
list ++= line.split(splitRegex).map(_.toInt).toList.tail
bufferList.prepend(list.toArray)
}
localFile.close()
bufferList.reverse.toArray
}
}
object Client {
def apply(): Client = new Client()
}
package Algorithms.Ch08_Topo.Version06
class MyRun {
def runTopoOrder(instTopoOrder:TopoOrder, graph: Array[Array[Int]]): Array[Int] ={
instTopoOrder.orderings(graph)
}
def runSCC(inst:StrongCC, graph: Array[Array[Int]] ):Array[Array[Int]]={
// SCC calculate
inst.SCC(graph)
}
}
object MyRun {
def apply(): MyRun = new MyRun()
}
package Algorithms.Ch08_Topo.Version06
trait StrongCC {
def SCC(graph :Array[Array[Int]]): Array[Array[Int]]
}
package Algorithms.Ch08_Topo.Version06
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
abstract class AbstractStrongCC extends StrongCC {
protected var graph= Array[Array[Int]]() //global variable considering G maybe in big size, and better to be dealt in place,
protected var flagArray= ArrayBuffer[Int]() //global variable
override def SCC(graphIn: Array[Array[Int]]): Array[Array[Int]] = {
graph = graphIn
//1. Let Grev denote the input graph G with the direction of every edge reversed.
val graphRevise: Array[Array[Int]] = GraphRevise(graph)
//2. Call DFS from every vertex of Grev, processed in arbitrary order,
// to compute a position f(v) for each vertex v.
val reviseTopoOrdsArray: Array[Int] = new TopoOrderDFSStack().orderings(graphRevise)
//3. Call DFS from every vertex of G, processed from highest to lowest position(position f(v) of G, but not Grev),
// to compute the identity of each vertex’s strongly connected component.
//3.1 initiate outer loop to iterate whole graph
val seqArray: ArrayBuffer[Int] = new Array[Int](graph.length).to[ArrayBuffer]
for(v <- 1 to graph.length){seqArray(reviseTopoOrdsArray(v-1)-1) = v} ;//println(seqArray.toList)
//
flagArray = new Array[Int](graph.length).to[ArrayBuffer]
var SCCnumber = 1 ; var ver = 1
for(v <- seqArray){
println(ver); ver+=1
if(flagArray(v-1)== 0){
updateFlagArray(SCCnumber,v) // update flagArray in place, flagging reachable vertex as SCCnumber
SCCnumber += 1
}
}
// return result
TransferFlagArray2List(SCCnumber-1) // transferFlagArray to list in place
}
protected def GraphRevise(graph: Array[Array[Int]]): Array[Array[Int]] = {
val graphRevise = ArrayBuffer[ArrayBuffer[Int]]()
// initiate graph. graphRevise index = vertex-1
// graphRevise(vertex)(0) is vertex itself, which should be dealt with carefully.
for(vertex <- 1 to graph.length){graphRevise += ArrayBuffer[Int](vertex)}
//ETL
for (vertex <- 1 to graph.length) {
// graph(vertex)(0) is vertex itself, which should be dealt with carefully.
for(edgePoint <- graph(vertex-1).toList.tail){
graphRevise(edgePoint-1) += vertex
}
}
// return result
graphRevise.toArray.map(_.toArray)
}
protected def TransferFlagArray2List(SCCnumber:Int): Array[Array[Int]] = {
val sccList = ArrayBuffer[ListBuffer[Int]]()
for(_ <- 1 to SCCnumber){sccList +=ListBuffer[Int]()}
// add vertices to each scc list
for(i<- flagArray.indices){
sccList(flagArray(i)-1) += i+1 // vertex=i+1; flagArray(i)=SCCgroupID. flagArray(i)-1 = list index
}
//for(l<- sccList.indices) println(s"${l+1}: ${sccList(l).length}")
//return result
sccList.toArray.map(_.toArray)
}
def updateFlagArray(SCCnumber: Int, v: Int)
}
package Algorithms.Ch08_Topo.Version06
import scala.collection.mutable.ListBuffer
class StrongCCDFSStack extends AbstractStrongCC {
def updateFlagArray(SCCnumber: Int, vertex: Int) = {
// unexplored:0, explored:SCCnumber
//1 DFS by stack
// graph index=vertex-1
val stack = ListBuffer[Int](vertex)
while(stack.nonEmpty){
val nextVertex = stack.remove(0)
// iterate the neighbor vertex; graph index=vertex-1
if(flagArray(nextVertex-1)== 0){
flagArray(nextVertex-1)= SCCnumber
for(v<- graph(nextVertex-1)){
if(flagArray(v-1)== 0) stack.prepend(v)
}
}
}
}
}
package Algorithms.Ch08_Topo.Version06
/**
* @note Topological Orderings
* Let G =(V,E) be a directed graph. A topological ordering of G is an assignment f(v)
* of every vertex v 2 V to a different number such that:
* for every (v, w) 2 E, f(v) <f(w).
* @author: Alfred.Qiang.Chen
* @Date: 2020/2/27
*/
trait TopoOrder {
// return Topological Orderings for each vertex(vertex = ArrayIndex+1)
def orderings(graphInput :Array[Array[Int]]):Array[Int]
}
package Algorithms.Ch08_Topo.Version06
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
class TopoOrderDFSStack extends AbstractTopoOrder {
override def orderings(graph: Array[Array[Int]]): Array[Int] = {
val exploreArray = ArrayBuffer[Int]() // flags for explored status. vertex = ArrayIndex+1
val curLabelArray = ArrayBuffer[Int]() // vertex’s position in ordering. vertex = ArrayIndex+1
var globalCurLable = graph.length //; println(graph.toList.map(_.toList)) ; println(graph.length)
// 1 initiate exploreArray. all vertices as unexplored(-1). explored(1)
exploreArray ++= graph.map(_=> -1)
// 2 initiate curLabel
curLabelArray ++= graph.map(_=> -1)
// 3 piggy back on DFS(by stack) to make orderings. graphIndex=vertex-1
for(vindex <- graph.indices){
if(exploreArray(vindex)== -1){
val stack = ListBuffer[Int](vindex+1) // vertex = graphIndex + 1
val curLabelStack = ListBuffer[Int]()
while(stack.nonEmpty){
val nextVertex = stack.remove(0)
// iterate the neighbor vertex
if(exploreArray(nextVertex-1)== -1){
exploreArray(nextVertex-1)= 1 // flag vertex as explored
curLabelStack.prepend(nextVertex) // vertex = graphIndex + 1
for(v<- graph(nextVertex-1)){
if((exploreArray(v-1)== -1)) stack.prepend(v)
}
}
}
for(v<- curLabelStack) {
curLabelArray(v-1)= globalCurLable // curLabelArray Index = vertex - 1
//print(s"(${v}" + s" ${globalCurLable}), ")
globalCurLable -= 1
}
//println(curLabelStack)
}
}
//4 return curLabelArray
curLabelArray.toArray
}
}
部分结果：
斯坦福算法课的编程题的数据集通常很大，整个计算过程通常非常耗时，借用线程和并发编程是很自然的想法。
如上图，使用线程并行处理可以明显缩短整个运行时间。但并发编程本身的学习曲线很长，也不是这门算法课的主要内容。
授人以”鱼“是个权宜的选择
以Programming Assignment 3为例：
Programming Assignment 3
1可能的分 (分级)
Download the following text file (right click and select "Save As..."): kargerMinCut.txt
The file contains the adjacency list representation of a simple undirected graph.
There are 200 vertices labeled 1 to 200.
The first column in the file represents the vertex label, and the particular row
(other entries except the first column) tells all the vertices that the vertex is adjacent to.
So for example, the 6th row looks like :
"6 155 56 52 120 ......".
This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with)
the vertices with labels 155,56,52,120,......,etc
Your task is to code up and run the randomized contraction algorithm
for the min cut problem and use it on the above graph to compute the min cut.
(HINT: Note that you'll have to figure out an implementation of edge contractions.
Initially, you might want to do this naively, creating a new graph from the old every time
there's an edge contraction. But you should also think about more efficient implementations.)
(WARNING: As per the video lectures, please make sure to run the algorithm many times
with different random seeds, and remember the smallest cut that you ever find.)
Write your numeric answer in the space provided. So e.g., if your answer is 5,
just type 5 in the space provided.
线程池和AtomicInteger使用的一个实例：
def runMinCut(factory: FactoryMinCut, graph: Array[Array[Int]] , loops:Int , numberOfThreads:Int): Unit = {
val T0_TIME = System.currentTimeMillis()
val GRAPH_LENGTH = graph.length
var result = (0, Array(0, 0))
val minumCutsAtomic = new AtomicInteger(GRAPH_LENGTH + 1)
val countAtomic = new AtomicInteger(0)
val executor = new ThreadPoolExecutor(
numberOfThreads,
numberOfThreads,
0L,
TimeUnit.MILLISECONDS,
new ArrayBlockingQueue[Runnable](100),
new ThreadPoolExecutor.CallerRunsPolicy
)
// submit to a threads pool
for (i <- 0 until loops) {
executor.submit(new Runnable {
override def run(): Unit = {
result = new MinCutKarger(graph).minCut()
//CAS - compare and swap
var done = false
var mt = minumCutsAtomic.get()
do {
if (mt > result._1) {
done = minumCutsAtomic.compareAndSet(mt, result._1)
if (!done) mt = minumCutsAtomic.get()
} else {
done = true
}
} while (!done)
//loop count
val count = countAtomic.incrementAndGet()
//timeArray += System.currentTimeMillis() - T1_TIME
println(s"At ${count} loop, cuts =${result._1}, " +
s"the last two vertices: ${result._2.toList.head}, ${result._2.toList(1)}")
}
})
}
executor.shutdown()
executor.awaitTermination(100, TimeUnit.SECONDS)
println(s"\nThe minimum cuts = ${minumCutsAtomic.get()} " +
s"\nTaking ${System.currentTimeMillis()-T0_TIME} milliseconds. \n" )
用new ThreadPoolExecutor启用一个线程池
val executor = new ThreadPoolExecutor(
numberOfThreads,
numberOfThreads,
0L,
TimeUnit.MILLISECONDS,
new ArrayBlockingQueue[Runnable](100),
new ThreadPoolExecutor.CallerRunsPolicy
)
跨线程的计数，可以直接使用：
val countAtomic = new AtomicInteger(0)
...
val count = countAtomic.incrementAndGet()
跨线程更新最小值，会繁琐一些，考虑到race condition的情况并不是很激烈，所以选择了乐观锁的思路，基于compareAndSet写了自旋锁的代码，抛砖引玉。
val minumCutsAtomic = new AtomicInteger(GRAPH_LENGTH + 1)
...
//CAS - compare and swap
var done = false
var mt = minumCutsAtomic.get()
do {
if (mt > result._1) {
done = minumCutsAtomic.compareAndSet(mt, result._1)
if (!done) mt = minumCutsAtomic.get()
} else {
done = true
}
} while (!done)
授人以鱼不如授人以渔
读AtomicInteger源码，会发现它实际上是调用了Java Native方法，这个方法又进一步调用了底层系统的汇编命令。以Intel 64-ia-32-architectures为例, 它调用了cmpxchg指令：
cmpxchg指令是基于硬件的，如文中所述“The processor never produces a locked read without also producing a locked write." ，避免了基于软件的lock方法的overhead，执行效率非常高，非常适合当前的场景。在1000 loops下，整个运行时间明显缩短了。
题外话
对并发编程感兴趣的小伙伴，强烈推荐开发Java concurrency库的架构师Brian Goetz写的Java concurrency in practice
