找到一个整数的位数最快的方法是什么?

huangapple go评论81阅读模式
英文:

Fastest way to find number of digits of an integer?

问题

我正在尝试构建一个验证给定输入的函数。输入是一个整数值。我的问题是,哪种方法应该是最有效和高效的?

count := 0

for number != 0 {
  number /= 10
  count += 1
}

return count

还是

len(strconv.Itoa(intValue))

谢谢!

英文:

I am trying to build a function which validates the given input. The input is an integer value. My question is, Which method should be the most effective and efficient

count := 0

for number != 0 {
  number /= 10
  count += 1
}

return count

or

len(strconv.Itoa(intValue))

Kind Regards

答案1

得分: 8

这是一个基准测试,修复了循环方法,使得输入为0时返回1:

func lenLoop(i int) int {
    if i == 0 {
        return 1
    }
    count := 0
    for i != 0 {
        i /= 10
        count++
    }
    return count
}

func lenItoa(i int) int {
    return len(strconv.Itoa(i))
}


const num = 834589

func BenchmarkLoop(b *testing.B) {
    for i := 0; i < b.N; i++ {
        lenLoop(num)
    }
}

func BenchmarkItoa(b *testing.B) {
    for i := 0; i < b.N; i++ {
        lenItoa(num)
    }
}

注意,这些方法只适用于正数。

在我的机器上的输出结果为:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-4771 CPU @ 3.50GHz
BenchmarkLoop
BenchmarkLoop-8    213208418    5.535 ns/op
BenchmarkItoa
BenchmarkItoa-8    33039769    33.74 ns/op

请注意,对于不同大小的输入数字,你可能会得到不同的结果;我选择了长度为6的数字作为典型情况,但你可以尝试其他选项。对于较短的数字,Itoa 中的额外机制使其比循环更慢(相对而言)。对于巨大的数字,它比循环慢4倍。

另外一个答案中提出的 log10 方法比修复后的循环方法慢2倍。

英文:

Here's a benchmark, with a fix for the loop method to return 1 for the input 0:

func lenLoop(i int) int {
	if i == 0 {
		return 1
	}
	count := 0
	for i != 0 {
		i /= 10
		count++
	}
	return count
}

func lenItoa(i int) int {
	return len(strconv.Itoa(i))
}


const num = 834589

func BenchmarkLoop(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		lenLoop(num)
	}
}

func BenchmarkItoa(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		lenItoa(num)
	}
}

[Note that these only work on positive numbers]

Output on my machine:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-4771 CPU @ 3.50GHz
BenchmarkLoop
BenchmarkLoop-8   	213208418	         5.535 ns/op
BenchmarkItoa
BenchmarkItoa-8   	33039769	        33.74 ns/op

Note that you could get different results for a different size of an input number; I picked length 6 as typical, but you could try other options. For shorter numbers, the extra machinery in Itoa makes it even slower (in relative terms) than the loop. For huge numbers it's "only" 4x slower than the loop.


The log10 method proposed in another answer is 2x slower than the loop (once fixed to handle corner cases correctly)

答案2

得分: 1

这里发生了很多事情。如果你正在验证输入,你可能不应该评估输入并将其保留在字符串(或[]byte)中;也就是说,简单地调用len(input)是最有效的方法,除非输入以某种二进制格式(或其他直接编码整数而不是其表示的格式)进行传入,但即使是这种情况,可能也有一种方法可以使用简单的算术方法(而不是使用对数或转换为浮点数)来缩小十进制长度。

如果给定的输入确实是一个int,有几种处理它的方式,目标是尽量少地进行操作,其中类型转换(除非是在int之间)非常浪费资源。

在这种情况下,简单的迭代计算数字的数量已经足够好(并且对于分支预测器友好);然而,在现代架构中,乘法比除法快得多;因此,与其除以给定的数字本身,比较一个(增长的)10的指数与该数字会更快。

func lenLoop10(i int) int {
    if i >= 1e18 {
        return 19
    }
    x, count := 10, 1
    for x <= i {
        x *= 10
        count++
    }
    return count
}

注意:乘法可能会溢出,因此我们需要检查边界;在64位架构上,int的最大值大于1e18但小于1e19,因此需要进行初始检查。

这是在正整数int64范围内进行随机工作负载的基准测试。

goos: windows
goarch: amd64
pkg: st.ack/ilog10
cpu: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
BenchmarkLoop-8                 24724068                45.26 ns/op
BenchmarkItoa-8                 16520800                62.47 ns/op
BenchmarkLoop10-8               415604792                2.824 ns/op
BenchmarkLoopPrecalc-8          100000000               11.51 ns/op
BenchmarkSearch-8               62924082                18.11 ns/op
BenchmarkSearchManual-8         180194925                6.741 ns/op
PASS
ok      st.ack/ilog10   34.460s

注意1:我包括了对预先计算的10的指数进行范围遍历,但它比直接乘以10要慢。

注意2:我还包括了两个使用二分搜索对预先计算的10的指数进行搜索的版本:一个使用sort.Search,一个手写的。sort.Search很好,但在这里多个函数调用太重了。手写版本消除了函数调用,并且性能要好得多,但仍然比简单的loopLen10慢。

注意3:虽然预先计算值可以节省运行时时间,但访问内存实际上并不是免费的,尤其在进行这种轻量级操作时不能将其视为免费。分支预测器也不是可以忽视的力量。

playground链接:https://play.golang.org/p/Qpd0W8Gdad1

英文:

There are many things happening here. If you are validating inputs, you probably shout NOT evaluate the input and keep it in the string (or []byte) from; which is to say, a simple calling len(input) would be most efficient, unless the inputs coming in some binary formats (or other formats that encodes integers directly instead of its representation), but even if that's the case, there is probably a way to narrow down the length in decimal using simple arithmetic methods (without using log or converting to float number).

If the given input is indeed an int, there are several way to handle it, and the goal is to do as less as possible, in which type conversion (unless it's between ints) are very wasteful.

With this in mind, the simple way of iterating to count the digits is good enough (and bonus point for being branch predictor friendly); however, on modern architectures, multiplying a number is much faster than dividing a number; so it would be faster to comparing a (growing) 10's exponents to the number than dividing the given number itself.

func lenLoop10(i int) int {
	if i &gt;= 1e18 {
		return 19
	}
	x, count := 10, 1
	for x &lt;= i {
		x *= 10
		count++
	}
	return count
}

Note: multiply can overflow, so we need to check the bounds; on 64 bit architectures, int's max value is bigger than 1e18 but smaller than 1e19, hence the initial check.

Here's a benchmark testing on random workload within range of positive int64s.

goos: windows
goarch: amd64
pkg: st.ack/ilog10
cpu: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
BenchmarkLoop-8                 24724068                45.26 ns/op
BenchmarkItoa-8                 16520800                62.47 ns/op
BenchmarkLoop10-8               415604792                2.824 ns/op
BenchmarkLoopPrecalc-8          100000000               11.51 ns/op
BenchmarkSearch-8               62924082                18.11 ns/op
BenchmarkSearchManual-8         180194925                6.741 ns/op
PASS
ok      st.ack/ilog10   34.460s

Note 1: I do include a range over pre-calculated exponents of 10s, and it's slower than just multiplying it by the go.

Note 2: I also includes two versions of using binary search against the pre-calculated exponents of 10s: one using sort.Search and one hand written. sort.Search is good, but multiple function calls is too heavy here. The hand written version eliminates function calls and has a much better performance, but still slower than the simple loopLen10.

Note 3: While pre-calculating values can save time at runtime, accessing memories are actually not free, and can especially not considered free when doing this light operations. And branch predictor is not a force to ignore.

playground: https://play.golang.org/p/Qpd0W8Gdad1

huangapple
  • 本文由 发表于 2021年6月25日 04:55:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/68122675.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定