Advertisement
AlexTyl

Untitled

Oct 18th, 2019
587
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 4.28 KB | None | 0 0
  1. fun main(args: Array<String>) {
  2.     val hashSet = HashSet<Int>()
  3.     val treeSet = TreeSet<Int>()
  4.  
  5.     var timeStart = 0L
  6.     var timeEnd = 0L
  7.  
  8.     huffmanCoding("beep boop beer!")
  9.     huffmanString("beep boop beer!", huffmanCoding("beep boop beer!"))
  10.     fromHuffmanString( huffmanString("beep boop beer!", huffmanCoding("beep boop beer!")), huffmanCoding("beep boop beer!"))
  11.  
  12.     timeStart = System.currentTimeMillis()
  13.     for (i in 0..300_000_000) {
  14.         hashSet.add(i % 300_000)
  15.     }
  16.     timeEnd = System.currentTimeMillis()
  17.     println("HASH ADD: ${(timeEnd - timeStart) / 1000f} sec.")
  18.  
  19.     timeStart = System.currentTimeMillis()
  20.     for (i in 0..300_000_000) {
  21.         hashSet.contains(i % 300_000)
  22.     }
  23.     timeEnd = System.currentTimeMillis()
  24.     println("HASH FIND: ${(timeEnd - timeStart) / 1000f} sec.")
  25.  
  26.     timeStart = System.currentTimeMillis()
  27.     for (i in 3_000..200_000_000)
  28.         hashSet.contains(i)
  29.     timeEnd = System.currentTimeMillis()
  30.     println("HASH FIND RANGE: ${(timeEnd - timeStart) / 1000f} sec.")
  31.  
  32.     timeStart = System.currentTimeMillis()
  33.     for (i in 0..300_000_000) {
  34.         hashSet.remove(i % 300_000)
  35.     }
  36.     timeEnd = System.currentTimeMillis()
  37.     println("HASH DELETE: ${(timeEnd - timeStart) / 1000f} sec.")
  38.  
  39.  
  40.     timeStart = System.currentTimeMillis()
  41.     for (i in 0..300_000_000) {
  42.         treeSet.add(i % 300_000)
  43.     }
  44.     timeEnd = System.currentTimeMillis()
  45.     println("TREE ADD: ${(timeEnd - timeStart) / 1000f} sec.")
  46.  
  47.     timeStart = System.currentTimeMillis()
  48.     for (i in 0..300_000_000) {
  49.         treeSet.contains(i % 300_000)
  50.     }
  51.     timeEnd = System.currentTimeMillis()
  52.     println("TREE FIND: ${(timeEnd - timeStart) / 1000f} sec.")
  53.  
  54.     timeStart = System.currentTimeMillis()
  55.     treeSet.subSet(3_000, 200_000_000)
  56.     timeEnd = System.currentTimeMillis()
  57.     println("TREE FIND RANGE: ${(timeEnd - timeStart) / 1000f} sec.")
  58.  
  59.     timeStart = System.currentTimeMillis()
  60.     for (i in 0..300_000_000) {
  61.         treeSet.remove(i % 300_000)
  62.     }
  63.     timeEnd = System.currentTimeMillis()
  64.     println("TREE DELETE: ${(timeEnd - timeStart) / 1000f} sec.")
  65.  
  66. }
  67.  
  68. fun huffmanCoding(phrase: String): HashMap<Char, String> {
  69.  
  70.     val chars = phrase.toCharArray()
  71.     val chapMap = HashMap<Char, Int>()
  72.  
  73.     chars.forEach {
  74.         val char = chapMap[it]
  75.         if (char == null)
  76.             chapMap[it] = 1
  77.         else
  78.             chapMap[it] = chapMap[it]!! + 1
  79.     }
  80.  
  81.     val queue = PriorityQueue<HuffmanNode>(Comparator { o1, o2 -> o1.cost.compareTo(o2.cost) })
  82.     chapMap.forEach { queue.add(HuffmanNode(it.value, it.key, isChar = true)) }
  83.  
  84.     while (queue.size > 1){
  85.         val first = queue.poll()
  86.         val second = queue.poll()
  87.  
  88.         val isFirstLeft = first.cost < second.cost
  89.  
  90.         val node = HuffmanNode(first.cost + second.cost)
  91.  
  92.         if (isFirstLeft){
  93.             node.left = first
  94.             node.right = second
  95.         } else {
  96.             node.left = second
  97.             node.right = first
  98.         }
  99.  
  100.         queue.add(node)
  101.     }
  102.  
  103.     val map = HashMap<Char, String>()
  104.     val root = queue.poll()
  105.  
  106.     root.getCodes(map)
  107.  
  108.     return map
  109.  
  110. }
  111.  
  112. fun huffmanString(str: String, map: HashMap<Char, String>): String {
  113.  
  114.     var huffStr = ""
  115.     val chars = str.toCharArray()
  116.  
  117.     chars.forEach {
  118.         huffStr += map[it]
  119.     }
  120.  
  121.     return huffStr
  122. }
  123.  
  124. fun fromHuffmanString(str: String, map: HashMap<Char, String>): String {
  125.  
  126.     var s = str
  127.     val reversMap = HashMap<String, Char>()
  128.     map.forEach { reversMap[it.value] = it.key }
  129.  
  130.     var outStr = ""
  131.     var shift = 1
  132.  
  133.     while (s.isNotEmpty()){
  134.         if (reversMap[s.substring(0, shift)] == null){
  135.             shift++
  136.         } else {
  137.             outStr += reversMap[s.substring(0, shift)]
  138.             s = s.substring(shift)
  139.             shift = 1
  140.         }
  141.     }
  142.  
  143.     return outStr
  144. }
  145.  
  146. data class HuffmanNode(var cost: Int, var char: Char? = null, val isChar: Boolean = false, var left: HuffmanNode? = null, var right: HuffmanNode? = null){
  147.     fun getCodes(map: HashMap<Char, String>, str: String = "") {
  148.         if (isChar)
  149.             map[char!!] = str
  150.         else {
  151.             this.left?.getCodes(map, str + "0")
  152.             this.right?.getCodes(map, str + "1")
  153.         }
  154.     }
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement