Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var mapChar = HashMap<Char, Int>()
- fun main(args: Array<String>) {
- val hashSet = HashSet<Int>()
- val treeSet = TreeSet<Int>()
- var timeStart = 0L
- var timeEnd = 0L
- val str = readLine()!!
- val map = huffmanCoding(str)
- val huffStr = huffmanString(str, map)
- val orig = fromHuffmanString(huffStr, map)
- mapChar.toList().sortedBy { it.second }.forEach{
- println("${it.first} - ${it.second}")
- }
- println("-----------------------------------------------------------------------------------")
- map.toList().sortedBy { it.second.length }.forEach{
- println("${it.first} = ${it.second}")
- }
- println("-----------------------------------------------------------------------------------")
- println(huffStr)
- println("-----------------------------------------------------------------------------------")
- println(orig)
- println()
- println()
- println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++")
- val count = readLine()!!.toInt()
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- hashSet.add(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("HASH ADD ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- hashSet.contains(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("HASH FIND ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- for (i in (count / 1000)..(count /10))
- hashSet.contains(i)
- timeEnd = System.currentTimeMillis()
- println("HASH FIND RANGE (${count / 1000})..(${count /10}) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- hashSet.remove(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("HASH DELETE ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- println("-----------------------------------------------------------------------------------")
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- treeSet.add(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("TREE ADD ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- treeSet.contains(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("TREE FIND ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- treeSet.subSet((count / 1000), (count / 10))
- timeEnd = System.currentTimeMillis()
- println("TREE FIND RANGE (${count / 1000})..(${count /10}) : ${(timeEnd - timeStart) / 1f} milli sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..count) {
- treeSet.remove(Random().nextInt(count))
- }
- timeEnd = System.currentTimeMillis()
- println("TREE DELETE ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
- }
- fun huffmanCoding(phrase: String): HashMap<Char, String> {
- val chars = phrase.toCharArray()
- val chapMap = HashMap<Char, Int>()
- chars.forEach {
- val char = chapMap[it]
- if (char == null)
- chapMap[it] = 1
- else
- chapMap[it] = chapMap[it]!! + 1
- }
- mapChar = chapMap
- val queue = PriorityQueue<HuffmanNode>(Comparator { o1, o2 -> o1.cost.compareTo(o2.cost) })
- chapMap.forEach { queue.add(HuffmanNode(it.value, it.key, isChar = true)) }
- while (queue.size > 1){
- val first = queue.poll()
- val second = queue.poll()
- val isFirstLeft = first.cost < second.cost
- val node = HuffmanNode(first.cost + second.cost)
- if (isFirstLeft){
- node.left = first
- node.right = second
- } else {
- node.left = second
- node.right = first
- }
- queue.add(node)
- }
- val map = HashMap<Char, String>()
- val root = queue.poll()
- root.getCodes(map)
- return map
- }
- fun huffmanString(str: String, map: HashMap<Char, String>): String {
- var huffStr = ""
- val chars = str.toCharArray()
- chars.forEach {
- huffStr += map[it]
- }
- return huffStr
- }
- fun fromHuffmanString(str: String, map: HashMap<Char, String>): String {
- var s = str
- val reversMap = HashMap<String, Char>()
- map.forEach { reversMap[it.value] = it.key }
- var outStr = ""
- var shift = 1
- while (s.isNotEmpty()){
- if (reversMap[s.substring(0, shift)] == null){
- shift++
- } else {
- outStr += reversMap[s.substring(0, shift)]
- s = s.substring(shift)
- shift = 1
- }
- }
- return outStr
- }
- data class HuffmanNode(var cost: Int, var char: Char? = null, val isChar: Boolean = false, var left: HuffmanNode? = null, var right: HuffmanNode? = null){
- fun getCodes(map: HashMap<Char, String>, str: String = "") {
- if (isChar)
- map[char!!] = str
- else {
- this.left?.getCodes(map, str + "0")
- this.right?.getCodes(map, str + "1")
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement