SHARE
TWEET

Untitled

a guest Nov 16th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package dijkstra
  2.  
  3. import kotlinx.atomicfu.atomic
  4. import java.lang.Math.abs
  5. import java.util.*
  6. import java.util.Collections.swap
  7. import java.util.concurrent.Phaser
  8. import java.util.concurrent.locks.ReentrantLock
  9. import kotlin.Comparator
  10. import kotlin.collections.ArrayList
  11. import kotlin.collections.RandomAccess
  12. import kotlin.concurrent.thread
  13.  
  14. private val NODE_DISTANCE_COMPARATOR = Comparator<Node> { o1, o2 -> Integer.compare(o1!!.distance, o2!!.distance) }
  15.  
  16. // Returns `Integer.MAX_VALUE` if a path has not been found.
  17.  
  18. class MyQueue(workers: Int, comparator: Comparator<Node> ){
  19.     val workers : Int
  20.     var queueSzie = atomic(0)
  21.     val sizeLock : ReentrantLock
  22.     val arr  = IntArray(workers)
  23.     var myList : List<Int>
  24.     val sizeGroups = atomic(0)
  25.  
  26.     val qu : ArrayList<PriorityQueue<Node>> = ArrayList()
  27.     val loksStatus : ArrayList<ReentrantLock> = ArrayList()
  28.     init{
  29.         this.workers = workers
  30.         for(i in 0..workers -1){
  31.             arr[i] = i
  32.         }
  33.         myList = arr.toList()
  34.         sizeLock = ReentrantLock()
  35.         for (i in 1..this.workers) {
  36.             qu.add(PriorityQueue(1, comparator))
  37.             loksStatus.add(ReentrantLock())
  38.         }
  39.     }
  40.  
  41.     fun pop(): Node? {
  42.         var i = 0
  43.         var j = 0
  44.         var deletedSomethink : Boolean = false
  45.         var ans : Node = Node()
  46.         var myShuffleList = myList.shuffled(Random())
  47.         while (!isEmpty()){
  48. //            i++;
  49. //            if(i == workers)
  50. //                i = 0
  51. //
  52. //            if(loksStatus[myShuffleList[i]].tryLock()){
  53. //                try{
  54. //                    if(qu[myShuffleList[i]].size > 0){
  55. //                        ans = qu[myShuffleList[i]].remove()
  56. //                        deletedSomethink = true
  57. //                        queueSzie.decrementAndGet()
  58. //                    }
  59. //                } finally {
  60. //                    loksStatus[myShuffleList[i]].unlock()
  61. //                }
  62. //            }
  63.  
  64.  
  65. //            if(deletedSomethink){
  66. //                return ans
  67. //            }
  68.             i = abs(Random().nextInt()) % workers
  69.             if(sizeGroups.value == 1) {
  70.                 if (loksStatus[i].tryLock()) {
  71.                     try {
  72.                         if (qu[i].size > 0) {
  73.                             ans = qu[i].remove()
  74.                             deletedSomethink = true
  75.                             if (qu[i].size == 0)
  76.                                 sizeGroups.decrementAndGet()
  77.                             queueSzie.decrementAndGet()
  78.                         }
  79.                     } finally {
  80.                         loksStatus[i].unlock()
  81.                     }
  82.                 }
  83.                 if (deletedSomethink)
  84.                     return ans
  85.                 continue
  86.             }
  87.             j = abs(Random().nextInt()) % workers
  88.  
  89.             if(i == j)
  90.                 continue
  91.             if (loksStatus[i].tryLock()) {
  92.                 try {
  93.                     if(loksStatus[j].tryLock()) {
  94.                         try {
  95.                             if (qu[i].size > 0 && qu[j].size > 0) {
  96.                                 if(qu[i].peek().distance > qu[j].peek().distance){
  97.                                     ans = qu[j].remove()
  98.                                     if(qu[j].size == 0)
  99.                                         sizeGroups.decrementAndGet()
  100.                                 } else{
  101.                                     ans = qu[i].remove()
  102.                                     if(qu[i].size == 0)
  103.                                         sizeGroups.decrementAndGet()
  104.                                 }
  105.                                 deletedSomethink = true
  106.                                 queueSzie.decrementAndGet()
  107.  
  108.                             }
  109.                         } finally {
  110.                             loksStatus[j].unlock();
  111.                         }
  112.                     }
  113.                 } finally {
  114.                     loksStatus[i].unlock()
  115.                 }
  116.             }
  117.             if(deletedSomethink) {
  118.                 return ans
  119.             }
  120.         }
  121.         return null
  122.     }
  123.  
  124.     fun add(x : Node){
  125.         var myShuffleList  = myList.shuffled(Random())
  126.         var i = 0
  127.         var flag = true
  128.         while (flag){
  129. //            i++
  130. //            if(i == workers)
  131. //                i = 0;
  132. //            if (loksStatus[myShuffleList[i]].tryLock()) {
  133. //                try {
  134. //                    if(qu[myShuffleList[i]].size == 0){
  135. //                        sizeGroups.incrementAndGet()
  136. //                    }
  137. //                    queueSzie.incrementAndGet()
  138. //                    qu[myShuffleList[i]].add(x)
  139. //                    flag = false
  140. //                } finally {
  141. //                    loksStatus[myShuffleList[i]].unlock()
  142. //
  143. //                }
  144. //            }
  145.             i = abs(Random().nextInt()) % workers
  146.             if (loksStatus[i].tryLock()) {
  147.                 try {
  148.                     if(qu[i].size == 0){
  149.                         sizeGroups.incrementAndGet()
  150.                     }
  151.                     queueSzie.incrementAndGet()
  152.                     qu[i].add(x)
  153.                     flag = false
  154.                 } finally {
  155.                     loksStatus[i].unlock()
  156.  
  157.                 }
  158.             }
  159.         }
  160.     }
  161.  
  162.     fun isEmpty() : Boolean {
  163.         var result : Boolean
  164.         result = true
  165.         if(queueSzie.value > 0) {
  166.             result = false
  167.         }
  168.         return result
  169.     }
  170. }
  171.  
  172. fun shortestPathParallel(start: Node) {
  173.     val workers = Runtime.getRuntime().availableProcessors()
  174.     //val workers = 1
  175.  
  176.  
  177.  
  178.     // The distance to the start node is `0`
  179.     start.distance = 0
  180.     // Create a priority (by distance) queue and add the start node into it
  181.     //val q = PriorityQueue(workers, NODE_DISTANCE_COMPARATOR) // TODO replace me with a multi-queue based PQ!
  182.     val q = MyQueue(workers, NODE_DISTANCE_COMPARATOR)
  183.     q.add(start)
  184.     // Run worker threads and wait until the total work is done
  185.     val onFinish = Phaser(workers + 1) // `arrive()` should be invoked at the end by each worker
  186.     repeat(workers) {
  187.         thread {
  188.             while (!q.isEmpty()) {
  189.                 val cur: Node? = q.pop()
  190.                 if (cur == null) {
  191.                     continue
  192.                 }
  193.                 for (e in cur.outgoingEdges) {
  194.                     while (true) {
  195.                         val olde = e.to.distance
  196.                         val oldcur = cur.distance
  197.                         if(olde > oldcur + e.weight) {
  198.                                 if (e.to.casDistance(olde, oldcur + e.weight)) {
  199.                                     q.add(e.to)
  200.                                     break
  201.                                 }
  202.                             continue
  203.                         }
  204.                         break
  205.                     }
  206.                 }
  207.             }
  208.                 // TODO Write the required algorithm here,
  209.                 // TODO break from this loop when there is no more node to process.
  210.                 // TODO Be careful, "empty queue" != "all nodes are processed".
  211.             onFinish.arrive()
  212.         }
  213.     }
  214.     onFinish.arriveAndAwaitAdvance()
  215. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top