map [byte] int и map [string] int имеют разное использование памяти

Question

Этот вопрос возник из маленькой простой проблемы из LeetCode .

Этот вопрос не связан с самой проблемой LeetCode. Но это связано с двумя подходами, которые имеют различие только в типе map, для решения этой проблемы LeetCode.

---

1. Первый подход с использованием 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
}

Как это онлайн судить по 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)

---

2. Второй подход с использованием 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
}

Как это онлайн судить по 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)

---

Несколько слов к онлайн-оценке: Я запускал эти две версии более 10 раз с интервалом в 1 час. И они достигают 22% против 100% при memory usage.

Что я ожидал:

Я думал, что первый, использующий map[byte]int, должен быть быстрее и экономить память.

Почему быстрее: Во второй версии мне приходится разыгрывать rune до string каждый раз. (Но проводник компилятора говорит мне, что это не большая разница.)

Почему следует экономить память: Потому что byte легче, чем string.

---

Итак, последний вопрос:

почему есть разница в memory usage?
И почему мои ожидания неверны?

Answer 1

Оцените ваш код, romanToIntStr и romanToIntByt.Разница между romanToIntStr и romanToIntByt незначительна.Ваш код romanToIntStr и romanToIntByt не эффективен.См. romanToIntArr.

---

Вывод:

$ 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)
    }
}