项目欧拉#22与Golang; 每次都会返回不同的结果

Question

我正在使用Go进行Project Euler的问题22,我是新手,我的代码给出了不一致的结果,这意味着每次运行程序时它都会显示不同的结果.它总是非常接近我所看到的正确答案,但范围在几百点之内.我原本以为它可能是由于浮动舍入不准确但我已经检查过,事实并非如此(我认为).如果有人能够指出可能会导致这种情况发生的事情,我将非常感激.几天来,我一直在努力寻找我的代码问题而无法解决它甚至在论坛上发现类似的问题.作为旁注,我最初使用golang math/big包编写了这个,并且获得了相同的更改结果.

package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "math"
    "strings"
)

func openFileReturnSlice(f string) []string {
    bytes, err := ioutil.ReadFile(f)
    if err != nil {
        log.Fatal("Failed to read file: p022_names.txt")
    }
    s2s := strings.Split(string(bytes), "\"")
    s22 := strings.Join(s2s, "")
    names := strings.Split(s22, ",")
    return names
}

func alphabetize(n []string) ([]string, map[string]int) {
    wordsValues := make(map[string]float64)
    wordLetterVal := make(map[string]int)
    for _, s := range n {
        loop := -1
        var wordValue float64
        alpha := int(0)
        for _, l := range s {
            ell := int(l) - 64
            mvDec := math.Pow(100, math.Abs(float64(loop)))
            wordValue += float64(l) / mvDec
            alpha += ell
            loop--
        }
        wordsValues[s] = wordValue
        wordLetterVal[s] = alpha
    }
    var sortedNames []string
    lenWordValues := len(wordsValues)
    for i := 0; i < lenWordValues; i++ {
        var lowValName string
        lowVal := float64(10)
        for k, v := range wordsValues {
            if v < lowVal {
                lowVal = v
                lowValName = k
            }
        }
        delete(wordsValues, lowValName)
        sortedNames = append(sortedNames, lowValName)
    }
    return sortedNames, wordLetterVal
}

func main() {
    names := openFileReturnSlice("p022_names.txt")
    alphabetical, sumAlphaValues := alphabetize(names)
    var total int
    for k := 0; k < len(alphabetical); k++ {
        var temp int
        key := k + 1
        temp = sumAlphaValues[alphabetical[k]] * key
        total += temp
    }
    fmt.Println("The total is: ", total)
}

Answer 1

浮点的使用是可疑的，它是不精确的。映射的迭代顺序未指定，并且不保证从一次迭代到下一次迭代的顺序相同。您对地图的使用最有可能解释看似随机的行为。

首先要问的问题是：正确答案是什么？

package main

import (
    "bytes"
    "fmt"
    "io/ioutil"
    "log"
    "strings"
)

func readNames(f string) []string {
    b, err := ioutil.ReadFile(f)
    if err != nil {
        log.Fatal(err)
    }
    s := string(bytes.Replace(b, []byte(`"`), []byte(``), -1))
    return strings.Split(s, ",")
}

func totalScores(names []string) int64 {
    for i := 0; i < len(names); i++ {
        for j := i + 1; j < len(names); j++ {
            if names[i] > names[j] {
                names[i], names[j] = names[j], names[i]
            }
        }
    }

    total := int64(0)
    for i, name := range names {
        score := int64(0)
        for _, char := range name {
            score += int64(char - 'A' + 1)
        }
        score *= int64(i) + 1
        total += score
    }
    return total
}

func main() {
    names := readNames("p022_names.txt")
    total := totalScores(names)
    fmt.Println("The total is: ", total)
}

输出：

The total is:  871198282

这就是欧拉项目希望您编写解决方案的第一个版本的方式。您的第二个版本应该用更快的排序（例如快速排序）替换简单的选择排序。

例如，您的程序需要很长时间才能产生错误的结果：

The total is:  871197995
real    0m1.945s
user    0m1.944s
sys     0m0.004s

我的程序产生正确的结果并且速度更快：

The total is:  871198282
real    0m0.771s
user    0m0.768s
sys     0m0.004s

如果我们用 Go 排序替换我的选择排序：

sort.StringSlice(names).Sort()

修改后的程序会产生正确的结果，而且速度要快得多：

The total is:  871198282
real    0m0.014s
user    0m0.012s
sys     0m0.000s

欧拉计划，命名分数，问题 22 是关于快速排序算法，而不是关于简单的分数计算。

为了从代码中获得稳定的结果，请注释掉以下delete语句：

// delete(wordsValues, lowValName)

现在剩下浮点错误：浮点算术和IEEE 浮点。

您的算法创建近似的、非唯一的浮点数wordValue。因此，映射上的随机迭代可以选择一些不同的lowVal和lowValName对，并且可以删除不同的映射条目。

非唯一wordValues：

0.657666698284738
0.6576697465786885
0.6576697465786885
0.6576698865786884
0.6578786577658275
0.6578847978698485
0.658571858384738
0.6669827865826875
0.6765847269827377
0.676976698384738
0.677282738384698
0.6772827383847367
0.6772827383847367
0.677282738384738
0.677282738384738
0.6772827383847982
0.6776697769788476
0.6982786983847379
0.6986657871697675
0.7076798269786776
0.7076798269788476
0.7082657867698368
0.7082657867738368
0.7082696869827366
0.7082696869827366
0.7165668273697676
0.716979827169658
0.7169798271698486
0.716979827173658
0.716979827173658
0.716979827173658
0.7185737676698277
0.7269788273698486
0.7273766869716582
0.7465678185697674
0.746567818569769
0.746567818569769
0.7469657878698486
0.7479836980727379
0.7565847265827377
0.7565847269827377
0.7573776669827669
0.7765716865766978
0.7765826769767379
0.7765826769767379
0.7765827165826985
0.7765827165826985
0.7765827165826985
0.7765827165826985
0.7765827165827385
0.7765827165827385
0.7765827185698275
0.7773677269767378
0.827983657673787
0.8384698072657875
0.8472797765837379
0.8665766978847378