Go lang：从一组数字中搜索x位数字，为什么需要很长时间才能执行？

Question

我试图制作从一组数字中找到 x 位数字的小程序，例如：我想从1 - 1000000000 中找到第 89位数字。这是我的代码：https : //play.golang.org/p/93yh_urX16package mainimport (    "fmt"    "strconv")var bucket stringfunc main() {    findDigits( 89, 1000000000 )}func findDigits( digits int, length int) {    for i := 1; i <= length; i++ {        bucket += strconv.Itoa(i)    }    fmt.Println( "The", digits, "th digit from 1", "-", length, "is :", string ( [] rune ( bucket )[digits - 1] ) )}有谁知道，我犯了什么错误？我需要一些建议来改进此代码。

Answer 1

你的程序非常非常低效。user1431317 的程序效率很低。

简单地计算价值。它只需要几纳秒的 CPU 时间和一些内存分配，即使是大到 9,223,372,036,854,775,807 的数字索引（95.6 纳秒和我的计算机上的 2 次分配）。例如，

package main

import (

    "fmt"

    "math"

    "strconv"

)

// digit returns the ith digit from the sequence of

// concatenated non-negative integers.

// The sequence of digits is 01234567891011121314151617181920...

func digit(i int64) string {

    // There are 9 one digit positive integers, 90 two digit,

    // 900 three digit, and so on.

    if i <= 0 {

        return "0"

    }

    j := int64(1)

    w := 1

    for ; ; w++ {

        t := j + 9*int64(math.Pow10(w-1))*int64(w)

        if 0 > t || t > i {

            break

        }

        j = t

    }

    k := i - j

    n := k / int64(w)

    m := k % int64(w)

    d := strconv.FormatInt(int64(math.Pow10(w-1))+n, 10)[m]

    return string(d)

}

func main() {

    tests := []int64{

        0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

        10, 11, 12, 13,

        88, 89,

        188, 189, 190, 191, 192,

        math.MaxInt32, math.MaxInt64,

    }

    for _, n := range tests {

        fmt.Println(n, digit(n))

    }

}

输出：

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

10 1

11 0

12 1

13 1

88 4

89 9

188 9

189 9

190 1

191 0

192 0

2147483647 2

9223372036854775807 9