20 June 2018

IMG-THUMBNAIL

讨论一下整数转字符串的几种方式,再讨论一下原理和性能。

整形转字符串经常会用到,本文讨论一下 Golang 提供的这几种方法。基于 go1.10.1

fmt.Sprintf

fmt 包应该是最常见的了,从刚开始学习 Golang 就接触到了,写 ‘hello, world’ 就得用它。它还支持格式化变量转为字符串。

func Sprintf(format string, a ...interface{}) string

Sprintf formats according to a format specifier and returns the resulting string.

fmt.Sprintf("%d", a)

%d代表十进制整数。

strconv.Itoa

func Itoa(i int) string

Itoa is shorthand for FormatInt(int64(i), 10).

strconv.Itoa(a)

strconv.FormatInt

func FormatInt(i int64, base int) string

FormatInt returns the string representation of i in the given base, for 2 <= base <= 36. The result uses the lower-case letters ‘a’ to ‘z’ for digit values >= 10.

参数i是要被转换的整数,base是进制,例如2进制,支持2到36进制。

strconv.Format(int64(a), 10)

Format 的实现

[0, 99)的两位整数

对于小的(小于等于100)十进制正整数有加速优化算法:

if fastSmalls && 0 <= i && i < nSmalls && base == 10 {
	return small(int(i))
}

加速的原理是提前算好100以内非负整数转换后的字符串。

const smallsString = "00010203040506070809" +
    "10111213141516171819" +
    "20212223242526272829" +
    "30313233343536373839" +
    "40414243444546474849" +
    "50515253545556575859" +
    "60616263646566676869" +
    "70717273747576777879" +
    "80818283848586878889" +
    "90919293949596979899"

可以看出来,转换后的结果是从1到99都有,而且每个结果只占两位。当然个人数的情况还得特殊处理,个位数结果只有一位。

func small(i int) string {
    off := 0
    if i < 10 {
        off = 1
    }
    return smallsString[i*2+off : i*2+2]
}

如果被转换的数字是个位数,那么偏移量变成了1,默认情况是0。

只支持2到36进制的转换。36进制是10个数字加26个小写字母,超过这个范围无法计算。

var a [64 + 1]byte 

整形最大64位,加一位是因为有个符号。转换计算时,要分10进制和非10进制的情况。

10进制转换

10进制里,两位两位转换,为什么这么干?两位数字时100以内非负整数转换可以用上面的特殊情况加速。很有意思。

us := uint(u)
for us >= 100 {
	is := us % 100 * 2
	us /= 100
	i -= 2
	a[i+1] = smallsString[is+1]
	a[i+0] = smallsString[is+0]
}

2、4、8、16、32进制的转换。

const digits = "0123456789abcdefghijklmnopqrstuvwxyz"

var shifts = [len(digits) + 1]uint{
    1 << 1: 1,
    1 << 2: 2,
    1 << 3: 3,
    1 << 4: 4,
    1 << 5: 5,
}

if s := shifts[base]; s > 0 {
	// base is power of 2: use shifts and masks instead of / and %
	b := uint64(base)
	m := uint(base) - 1 // == 1<<s - 1
	for u >= b {
		i--
		a[i] = digits[uint(u)&m]
		u >>= s
	}
	// u < base
	i--
	a[i] = digits[uint(u)]
} 

通过循环求余实现。进制的转换也是这种方式。

for u >= b {
    i--
    a[i] = uint(u)&m
    u >>= s
}

上面的代码实现了进制的转换。而digits[uint(u)&m]实现了转换后的结果再转成字符。

常规情况

b := uint64(base)
for u >= b {
	i--
	q := u / b
	a[i] = digits[uint(u-q*b)]
	u = q
}
// u < base
i--
a[i] = digits[uint(u)]

依然是循环求余来实现。这段代码更像是给人看的。和上面2的倍数的进制转换的区别在于,上面的代码把除法/换成了右移(>>s位,把求余%换成了逻辑与&操作。

Sprintf 的实现

switch f := arg.(type) {
    case bool:
        p.fmtBool(f, verb)
    case float32:
        p.fmtFloat(float64(f), 32, verb)
    case float64:
        p.fmtFloat(f, 64, verb)
    case complex64:
        p.fmtComplex(complex128(f), 64, verb)
    case complex128:
        p.fmtComplex(f, 128, verb)
    case int:
        p.fmtInteger(uint64(f), signed, verb)
    ...
}

判断类型,如果是整数int类型,不需要反射,直接计算。支持的都是基础类型,其它类型只能通过反射实现。

Sprintf支持的进制只有10%d、16x、8o、2b这四种,其它的会包fmt: unknown base; can’t happen异常。

switch base {
case 10:
	for u >= 10 {
		i--
		next := u / 10
		buf[i] = byte('0' + u - next*10)
		u = next
	}
case 16:
	for u >= 16 {
		i--
		buf[i] = digits[u&0xF]
		u >>= 4
	}
case 8:
	for u >= 8 {
		i--
		buf[i] = byte('0' + u&7)
		u >>= 3
	}
case 2:
	for u >= 2 {
		i--
		buf[i] = byte('0' + u&1)
		u >>= 1
	}
default:
	panic("fmt: unknown base; can't happen")
}

2、8、16进制和之前FormatInt差不多,而10进制的性能差一些,每次只能处理一位数字,而不像FormatInt一次处理两位。

性能对比

var smallInt = 35
var bigInt = 999999999999999

func BenchmarkItoa(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := strconv.Itoa(smallInt)
        _ = val
    }
}

func BenchmarkItoaFormatInt(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := strconv.FormatInt(int64(smallInt), 10)
        _ = val
    }
}

func BenchmarkItoaSprintf(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := fmt.Sprintf("%d", smallInt)
        _ = val
    }
}

func BenchmarkItoaBase2Sprintf(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := fmt.Sprintf("%b", smallInt)
        _ = val
    }
}

func BenchmarkItoaBase2FormatInt(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := strconv.FormatInt(int64(smallInt), 2)
        _ = val
    }
}

func BenchmarkItoaBig(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := strconv.Itoa(bigInt)
        _ = val
    }
}

func BenchmarkItoaFormatIntBig(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := strconv.FormatInt(int64(bigInt), 10)
        _ = val
    }
}

func BenchmarkItoaSprintfBig(b *testing.B) {
    for i := 0; i < b.N; i++ {
        val := fmt.Sprintf("%d", bigInt)
        _ = val
    }
}

压测有三组对比,小于100的情况,大数字的情况,还有二进制的情况。

BenchmarkItoa-8                 	300000000	         4.58 ns/op	       0 B/op	       0 allocs/op
BenchmarkItoaFormatInt-8        	500000000	         3.07 ns/op	       0 B/op	       0 allocs/op
BenchmarkItoaBase2Sprintf-8     	20000000	        86.4 ns/op	      16 B/op	       2 allocs/op
BenchmarkItoaBase2FormatInt-8   	50000000	        30.2 ns/op	       8 B/op	       1 allocs/op
BenchmarkItoaSprintf-8          	20000000	        83.5 ns/op	      16 B/op	       2 allocs/op
BenchmarkItoaBig-8              	30000000	        44.6 ns/op	      16 B/op	       1 allocs/op
BenchmarkItoaFormatIntBig-8     	30000000	        43.9 ns/op	      16 B/op	       1 allocs/op
BenchmarkItoaSprintfBig-8       	20000000	       108 ns/op	      24 B/op	       2 allocs/op
  • Sprintf在所有情况中都是最差的,还是别用这个包了。
  • 小于100的情况会有加速,不光是性能上的加速,因为结果是提前算好的,也不需要申请内存。
  • FormatInt10进制性能最好,其它的情况差一个数量级。
  • Itoa虽然只是封装了FormatInt,对于性能还是有一些影响的。

本文涉及的代码可以从这里下载。


参考文献
  1. 11.4 类型判断:type-switch - Go 入门指南

原文链接:Golang 中整数转字符串,转载请注明来源!

EOF

支付宝打赏 微信打赏

您的打赏是对我最大的鼓励!



相关推荐

blog comments powered by Disqus。如果你看不到评论框,加我微信或者自己想办法。