Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- fun main(args: Array<String>) {
- val hashSet = HashSet<Int>()
- val treeSet = TreeSet<Int>()
- var timeStart = 0L
- var timeEnd = 0L
- huffmanCoding("beep boop beer!")
- huffmanString("beep boop beer!", huffmanCoding("beep boop beer!"))
- fromHuffmanString( huffmanString("beep boop beer!", huffmanCoding("beep boop beer!")), huffmanCoding("beep boop beer!"))
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- hashSet.add(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("HASH ADD: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- hashSet.contains(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("HASH FIND: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 3_000..200_000_000)
- hashSet.contains(i)
- timeEnd = System.currentTimeMillis()
- println("HASH FIND RANGE: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- hashSet.remove(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("HASH DELETE: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- treeSet.add(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("TREE ADD: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- treeSet.contains(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("TREE FIND: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- treeSet.subSet(3_000, 200_000_000)
- timeEnd = System.currentTimeMillis()
- println("TREE FIND RANGE: ${(timeEnd - timeStart) / 1000f} sec.")
- timeStart = System.currentTimeMillis()
- for (i in 0..300_000_000) {
- treeSet.remove(i % 300_000)
- }
- timeEnd = System.currentTimeMillis()
- println("TREE DELETE: ${(timeEnd - timeStart) / 1000f} 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
- }
- 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