Go中数字（字符串类型）的高效反向索引

Question

TLDR（和简化）：给定一个字符串 s，其中 s 是任何正整数，反转顺序并将每个数字乘以它的新索引 (+1) 求和。

例如，从“98765”返回的值将是：(1x5) + (2x6) + (3x7) + (4x8) + (5*9)= 115.

我当前的工作解决方案可以在这里找到：Go playground。我想知道是否有更好的方法来做到这一点，无论是可读性还是效率。例如，我决定使用 count 变量，而不是使用 i 和 len，因为它看起来更清晰。我也不太熟悉 int/string 转换，但我假设需要使用 strconv。

func reverseStringSum(s string) int {
    total := 0
    count := 1
    for i := len(s) - 1; i >= 0; i-- {
        char := string([]rune(s)[i])
        num, _ := strconv.Atoi(char)
        total += count * num
        count++
    }
    return total
}

Answer 1

这是解决完整问题的有效方法：sum("987-65") = 115。完整的问题记录在您的工作解决方案 link 中：https://go.dev/play/p/DJ1ZYYDFnfq.

package main

import "fmt"

func reverseSum(s string) int {
    sum := 0
    for i, j := len(s)-1, 0; i >= 0; i-- {
        d := int(s[i]) - '0'
        if 0 <= d && d <= 9 {
            j++
            sum += j * d
        }
    }
    return sum
}

func main() {
    s := "987-65"
    sum := reverseSum(s)
    fmt.Println(sum)
}

https://go.dev/play/p/bx7wfmtXaie

由于我们在谈论高效的 Go 代码，因此我们需要一些 Go 基准测试。

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

BenchmarkSumTBJ-8     4001182   295.8 ns/op     52 B/op   6 allocs/op
BenchmarkSumA2Q-8   225781720     5.284 ns/op    0 B/op   0 allocs/op

您的解决方案 (TBJ) 很慢。

reversesum_test.go:

package main

import (
    "strconv"
    "strings"
    "testing"
)

func reverseSumTBJ(s string) int {
    total := 0
    count := 1
    for i := len(s) - 1; i >= 0; i-- {
        char := string([]rune(s)[i])
        num, _ := strconv.Atoi(char)
        total += count * num
        count++
    }
    return total
}

func BenchmarkSumTBJ(b *testing.B) {
    for n := 0; n < b.N; n++ {
        rawString := "987-65"
        stringSlice := strings.Split(rawString, "-")
        numberString := stringSlice[0] + stringSlice[1]
        reverseSumTBJ(numberString)
    }
}

func reverseSumA2Q(s string) int {
    sum := 0
    for i, j := len(s)-1, 0; i >= 0; i-- {
        d := int(s[i]) - '0'
        if 0 <= d && d <= 9 {
            j++
            sum += j * d
        }
    }
    return sum
}

func BenchmarkSumA2Q(b *testing.B) {
    for n := 0; n < b.N; n++ {
        rawString := "987-65"
        reverseSumA2Q(rawString)
    }
}

求和是更大问题的一部分，计算 CAS Registry Number 校验位。

package main

import "fmt"

// CASRNCheckDigit returns the computed
// CAS Registry Number check digit.
func CASRNCheckDigit(s string) string {
    // CAS Registry Number
    // https://en.wikipedia.org/wiki/CAS_Registry_Number
    //
    // The check digit is found by taking the last digit times 1,
    // the preceding digit times 2, the preceding digit times 3 etc.,
    // adding all these up and computing the sum modulo 10.
    //
    // The CAS number of water is 7732-18-5:
    // the checksum 5 is calculated as
    // (8×1 + 1×2 + 2×3 + 3×4 + 7×5 + 7×6)
    // = 105; 105 mod 10 = 5.
    //
    // Check Digit Verification of CAS Registry Numbers
    // https://www.cas.org/support/documentation/chemical-substances/checkdig

    for i, sep := 0, 0; i < len(s); i++ {
        if s[i] == '-' {
            sep++
            if sep == 2 {
                s = s[:i]
                break
            }
        }
    }

    sum := 0
    for i, j := len(s)-1, 0; i >= 0; i-- {
        d := int(s[i]) - '0'
        if 0 <= d && d <= 9 {
            j++
            sum += j * d
        }
    }
    return string(rune(sum%10 + '0'))
}

func main() {
    var rn, cd string
    // 987-65-5: Adenosine 5'-triphosphate disodium salt
    // https://www.chemicalbook.com/CASEN_987-65-5.htm
    rn = "987-65"
    cd = CASRNCheckDigit(rn)
    fmt.Println("CD:", cd, "\tRN:", rn)
    // 732-18-5: Water
    // https://www.chemicalbook.com/CASEN_7732-18-5.htm
    rn = "7732-18-5"
    cd = CASRNCheckDigit(rn)
    fmt.Println("CD:", cd, "\tRN:", rn)
    // 7440-21-3: Silicon
    // https://www.chemicalbook.com/CASEN_7440-21-3.htm
    rn = "7440-21-3"
    cd = CASRNCheckDigit(rn)
    fmt.Println("CD:", cd, "\tRN:", rn)
}

https://go.dev/play/p/VYh-5LuGpCn

BenchmarkCD-4   37187641   30.29 ns/op   4 B/op   1 allocs/op

Answer 2

也许这样效率更高

func reverseStringSum(s string) int {
    total := 0
    count := 1
    for i := len(s) - 1; i >= 0; i-- {
        num, _ := strconv.Atoi(string(s[i]))
        total += count * num
        count++
    }
    return total
}

Go中数字（字符串类型）的高效反向索引

Efficient reverse indexing of number (type string) in Go

string

integer

go