map [byte] int和map [string] int具有不同的内存使用量

Question

This question came from a little simple problem from LeetCode.

This question is not so related with the LeetCode problemm itself. But it's related with two approaches, which only has difference at the type of map, to solve this LeetCode problem.

---

1. The first approach using map[byte]int:

func romanToInt(s string) int {
    m := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    result := 0
    length := len(s)
    last_element := length - 1
    for i := 0; i < last_element; i++ {
        current := m[s[i]]
        next := m[s[i+1]]
        if current < next {
            result -= current
        } else {
            result += current
        }
    }
    result += m[s[last_element]]
    return result
}

How it online judged by LeetCode:

✔ Accepted
  ✔ 3999/3999 cases passed (16 ms)
  ✔ Your runtime beats 100 % of golang submissions
  ✔ Your memory usage beats 22 % of golang submissions (3 MB)

---

1. The Second approach using map[string]int:

func romanToInt(s string) int {
    m := map[string]int{
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }
    result := 0
    length := len(s)
    last_element := length - 1
    for i := 0; i < last_element; i++ {
        current := m[string(s[i])]
        next := m[string(s[i+1])]
        if current < next {
            result -= current
        } else {
            result += current
        }
    }
    result += m[string(s[last_element])]
    return result
}

How it online judged by LeetCode:

✔ Accepted
  ✔ 3999/3999 cases passed (16 ms)
  ✔ Your runtime beats 100 % of golang submissions
  ✔ Your memory usage beats 100 % of golang submissions (3 MB)

---

Some word to the online evaluation: I had run this two versions more than 10 times in time interval 1 hour. And they achieve 22 % vs 100 % at memory usage.

What I expected:

I thought this first one using map[byte]int should be faster and memory-saver.

Why faster: In the second version, I have to cast the rune to string every time. (But the compiler explorer tells me that is not a big difference.)

Why should be memory-saver: Because byte is more lighter than string.

---

So final question:

why there is a difference at the memory usage?
And why is my expectation wrong?

Answer 1

Benchmark your code, romanToIntStr and romanToIntByt. The difference between romanToIntStr and romanToIntByt is not significant. Your code, romanToIntStr and romanToIntByt, is not efficient. See romanToIntArr.

---

Output:

$ go test roman2int_test.go -bench=. -benchmem

BenchmarkRomanToIntStr-8    2725520   440 ns/op     0 B/op   0 allocs/op
BenchmarkRomanToIntByt-8    2377992   499 ns/op     0 B/op   0 allocs/op

BenchmarkRomanToIntArr-8   25643797    42.3 ns/op   0 B/op   0 allocs/op

roman2int_test.go:

package main

import "testing"

func romanToIntStr(s string) int {
    m := map[string]int{
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }
    result := 0
    length := len(s)
    last_element := length - 1
    for i := 0; i < last_element; i++ {
        current := m[string(s[i])]
        next := m[string(s[i+1])]
        if current < next {
            result -= current
        } else {
            result += current
        }
    }
    result += m[string(s[last_element])]
    return result
}

func romanToIntByt(s string) int {
    m := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    result := 0
    length := len(s)
    last_element := length - 1
    for i := 0; i < last_element; i++ {
        current := m[s[i]]
        next := m[s[i+1]]
        if current < next {
            result -= current
        } else {
            result += current
        }
    }
    result += m[s[last_element]]
    return result
}

func romanToIntArr(s string) int {
    m := [256]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
    result := 0
    last := len(s) - 1
    for i := 0; i < last; i++ {
        current := m[(s[i])]
        next := m[(s[i+1])]
        if current < next {
            result -= current
        } else {
            result += current
        }
    }
    result += m[(s[last])]
    return result
}

var bench1942 = "MCMXLII"

func BenchmarkRomanToIntStr(b *testing.B) {
    for N := 0; N < b.N; N++ {
        romanToIntStr(bench1942)
    }
}

func BenchmarkRomanToIntByt(b *testing.B) {
    for N := 0; N < b.N; N++ {
        romanToIntByt(bench1942)
    }
}

func BenchmarkRomanToIntArr(b *testing.B) {
    for N := 0; N < b.N; N++ {
        romanToIntArr(bench1942)
    }
}