我试图使用Go来实现叶子上带有值的二叉树,即相当于:
data Tree a
= Node {left: Tree, right: Tree}
| Leaf {value: a}
我有两个问题:1,我无法找到一种方法来创建一个包含多个构造函数的类型,所以我必须将所有数据放在一个中.2,我不能使它变成多态,所以我不得不使用interface{}
(我猜这是类型系统的"选择退出"?).这是我能做的最好的:
package main
import ("fmt")
type Tree struct {
IsLeaf bool
Left *Tree
Value interface{}
Right *Tree
}
func build(n int) *Tree {
if (n == 0) {
return &Tree{IsLeaf: true, Left: nil, Value: 1, Right: nil}
} else {
return &Tree{IsLeaf: false, Left: build(n - 1), Value: 0, Right: build(n - 1)}
}
}
func sum(tree *Tree) int {
if (tree.IsLeaf) {
return tree.Value.(int)
} else {
return sum(tree.Left) + sum(tree.Right)
}
}
func main() {
fmt.Println(sum(build(23)))
}
它实现了类型并通过对生成的巨大树进行求和来测试它.我已经开始在Javascript中进行等效的实现(包括构造函数的冗余数据,为了公平):
const build = n => {
if (n === 0) {
return {IsLeaf: true, Value: 1, Left: null, Right: null};
} else {
return {IsLeaf: false, Value: 0, Left: build(n - 1), Right: build(n - 1)};
}
}
const sum = tree => {
if (tree.IsLeaf) {
return tree.Value;
} else {
return sum(tree.Left) + sum(tree.Right);
}
}
console.log(sum(build(23)));
我编译了Go代码go build test.go
并运行它time ./test
.我已经运行了Node.js代码node test.js
.经过多次测试后,Go程序2.5
平均运行大约几1.0
秒钟,而Node.js则运行几秒钟.
这使得2.5x
这个简单程序的Go 慢于Node.js,这是不正确的,因为Go是一个带有成熟编译器的静态类型的编译语言,而Javascript是一个无类型的,解释的.
为什么我的Go程序这么慢?我错过了一些编译器标志,还是代码有问题?
1> Timothy Jone..:
摘要
由于类型断言和reduntant数据,此代码较慢.
Go不鼓励你在热门地方写类型断言:
tree.Value.(int)
取出这种类型的断言(并相应地更改Value
为int
类型),并且您的代码将执行大约两倍的速度(这应该是您的节点示例的速度).
同时取出冗余数据,您的代码执行速度大约是原来的三倍.请参阅帖子末尾的游乐场示例.
细节
我认为这是设计的错误,而不是实施.阅读你的问题,我认为Go的类型系统如何运作存在一些混乱.
Go的对象模型不鼓励你使用catch-all类型进行多态性(有关Go的多态性的讨论,请参阅这个优秀答案的上半部分).
在Javascript世界中,每个对象都是特定类型.在Go中,struct
如果a符合interface
合同,则可以将其视为特定的接口类型.请注意,structs
这不是对象 - 您所谓的构造函数只是struct
初始化器.
可以编写interface{}
作为所有类型的占位符进行操作的Go代码,但该语言并不真正鼓励您以这种方式编写代码(正如您在问题中指出的那样,在代码中编写干净代码是一项挑战.你会用Javascript写的方式).
因为Go实际上没有对象,所以尝试编写在Go中感觉非常面向对象的代码将具有挑战性(此外,Go没有标准继承或方法重载).出于这个原因,我认为你的代码不是Go鼓励程序员编写的代码.所以,这不是一个公平的考验.
类型断言很慢.(我并不是围绕Go的内部设计,但这肯定表明程序员不会写出很多类型的断言).因此,您的代码不具备高效性就不足为奇了.我将您的代码更改为:
type Tree struct {
IsLeaf bool
Left *Tree
Value int
Right *Tree
}
.....
func sum(tree *Tree) int {
if (tree.IsLeaf) {
return tree.Value
} else {
return sum(tree.Left) + sum(tree.Right)
}
}
并且在我的机器上实现了2倍的加速.
可能还有其他优化 - 您可能能够删除IsLeaf
,并且您不需要在非叶节点上存储值(或者,您可以在整个树中分配值,因此永远不要浪费Value
).我不知道Javascript是否优化了这些不必要Value
的,但我不相信Go会这样做.
所以,我认为你的代码使用的内存比它需要的多得多,这对性能也无济于事.
有关系吗?
我个人并不相信"我在X和Y中编写了这个程序,发现Y更慢",特别是因为很难在框架之间进行公平比较.还有很多其他方差来源 - 程序员知识,机器负载,启动时间等.
要做一个公平的测试,你需要编写每种语言惯用的代码,但也要使用相同的代码.我认为实现这两者并不现实.
如果此代码是您的特定方案,并且性能是主要目标,那么此测试可能会有所帮助.但是,否则我不认为这是一个非常有意义的比较.
在规模上,我希望其他考虑因素能够超越您创建和遍历树的速度.存在技术问题,例如数据吞吐量和负载下的性能,以及程序员时间和维护工作等更软的问题.
不过,学术练习很有意思.编写这样的代码是查找框架边缘的好方法.
编辑:我尝试使你的代码更像Go,它具有比原始版本快3倍的额外优势:
https://play.golang.org/p/mWaO3WR6pw
这个树对于游乐场来说有点沉重,但您可以复制并粘贴代码以在本地运行.
我没有尝试过更多可能的优化,例如树的并行构造.
您可以扩展此设计以获得所需的多态行为(通过提供替代Leaf
实现),但我不确定Sum()
非数字类型的含义.不知道如何定义Sum()
是一种很好的例子,这种思维导致不决定通过泛型包含多态性.