英文:
making generic algorithms in go
问题
我无法找到一种干净的方法来实现一个适用于任何类型的算法。
以下代码将产生错误,尝试将字符串或类型切片转换为接口,并且无法比较interface{}对象:invalid operation: result[0] > result[n - 1] (operator > not defined on interface)
func main() {
c := Algo("abc")
//...
c := Algo([3]int{1,2,3})
//...
}
func Algo(list []interface{}) chan []interface{} {
n := len(list)
out := make(chan []interface{})
go func () {
for i := 0; i < n; i++ {
result := make([]interface{}, n)
copy(result, list)
// an actually useful algorithm goes here:
if (result[0] > result[n-1]) {
result[0], result[n-1] = result[n-1], result[0]
}
out <- result
}
close(out)
}()
return out
}
虽然这很麻烦(我认为它应该是自动的),我可以手动将类型切片装箱和拆箱为interface{},但上面的真正问题是比较。而且它只会变得越来越笨拙。
a := [3]int{1,2,3}
b := make([]interface{}, len(a))
for i, _ := range a {
b[i] = a[i]
}
我甚至考虑过使用vector.Vector,但很多人都说不要使用它们。
那么,我应该只为int切片和字符串实现相同的算法吗?那么对于myObject的切片呢?我可以创建一个带有自定义比较函数的接口,但是如何使其与标准类型一起工作呢?
英文:
I can't figure out a clean way to implement an algorithm that will work on any type.
The following code will produce errors trying to convert a string or a typed slice into interfaces, and you can't compare interface{} objects: invalid operation: result[0] > result[n - 1] (operator > not defined on interface)
func main() {
c := Algo("abc")
//...
c := Algo([3]int{1,2,3})
//...
}
func Algo(list []interface{}) chan []interface{} {
n := len(list)
out := make(chan []interface{})
go func () {
for i := 0; i < n; i++ {
result := make([]interface{}, n)
copy(result, list)
// an actually useful algorithm goes here:
if (result[0] > result[n-1]) {
result[0], result[n-1] = result[n-1], result[0]
}
out <- result
}
close(out)
}()
return out
}
Although it's a pain (I think it should be automatic), I can manually box and unbox typed slices into interface{}s, the real problem above is the comparison. And it just keeps getting more and more kludgy.
a := [3]int{1,2,3}
b := make([]interface{}, len(a))
for i, _ := range a {
b[i] = a[i]
}
I've even thought of using vector.Vector, but so many people say never to use them.
So should I just implement the same algorithm for int slices and strings? What about slices of myObject? I can make an interface with a custom comparison func, but then how do I make it work with standard types?
答案1
得分: 11
你可以使用Go语言中的接口来实现这个功能。一个接受接口类型的函数在某种意义上是泛型的,因为它不关心底层具体类型的数据表示方式。它通过方法调用来完成所有操作。
要创建一个泛型版本的算法,你需要确定算法对数据对象的所有要求,并定义抽象这些要求的方法。抽象方法的签名成为接口的方法集。
为了使类型与这种泛型算法兼容,你需要在类型上定义方法来满足算法参数的接口。
我将使用你的示例代码,并展示一种实现方法。大部分所需的功能恰好已经被sort.Interface覆盖,所以我选择将其嵌入其中。只需要另外一个功能,即复制数据。
下面是一个完整的工作程序,由你的示例代码创建。
package main
import (
"fmt"
"sort"
)
func main() {
s1 := sortableString("abc")
c1 := Algo(s1)
fmt.Println(s1, <-c1)
s2 := sortable3Ints([3]int{1,2,3})
c2 := Algo(&s2)
fmt.Println(s2, <-c2)
}
type algoContainer interface {
sort.Interface
Copy() algoContainer
}
type sortableString []byte
func (s sortableString) Len() int { return len(s) }
func (s sortableString) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sortableString) Less(i, j int) bool { return s[i] < s[j] }
func (s sortableString) Copy() algoContainer {
return append(sortableString{}, s...)
}
func (s sortableString) String() string { return string(s) }
type sortable3Ints [3]int
func (sortable3Ints) Len() int { return 3 }
func (s *sortable3Ints) Swap(i, j int) {
(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}
func (s sortable3Ints) Less(i, j int) bool { return s[i] < s[j] }
func (s sortable3Ints) Copy() algoContainer { c := s; return &c }
func Algo(list algoContainer) chan algoContainer {
n := list.Len()
out := make(chan algoContainer)
go func () {
for i := 0; i < n; i++ {
result := list.Copy()
// actually useful:
if result.Less(n-1, 0) {
result.Swap(n-1, 0)
}
out <- result
}
close(out)
}()
return out
}
英文:
You can do this in Go using interfaces. A function that takes an interface type is generic in the sense that it doesn't care about the data representation of the underlying concrete type. It does everything through method calls.
To make a generic version of your algorithm then, you have to identify all of the capabilities that the algorithm requires of the data objects and you have to define methods that abstract these capabilities. The abstract method signatures become method sets of interfaces.
To make a type compatible with this kind of generic algorithm, you define methods on the type to satisfy the interface of the algorithm parameter.
I'll take your example code and show one way to do this. Most of the required capabilities happen to be covered by sort.Interface so I chose to embed it. Only one other capability is needed, one to make a copy of the data.
type algoContainer interface {
sort.Interface
Copy() algoContainer
}
Below is a complete working program made from your example code.
package main
import (
"fmt"
"sort"
)
func main() {
s1 := sortableString("abc")
c1 := Algo(s1)
fmt.Println(s1, <-c1)
s2 := sortable3Ints([3]int{1,2,3})
c2 := Algo(&s2)
fmt.Println(s2, <-c2)
}
type algoContainer interface {
sort.Interface
Copy() algoContainer
}
type sortableString []byte
func (s sortableString) Len() int { return len(s) }
func (s sortableString) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sortableString) Less(i, j int) bool { return s[i] < s[j] }
func (s sortableString) Copy() algoContainer {
return append(sortableString{}, s...)
}
func (s sortableString) String() string { return string(s) }
type sortable3Ints [3]int
func (sortable3Ints) Len() int { return 3 }
func (s *sortable3Ints) Swap(i, j int) {
(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}
func (s sortable3Ints) Less(i, j int) bool { return s[i] < s[j] }
func (s sortable3Ints) Copy() algoContainer { c := s; return &c }
func Algo(list algoContainer) chan algoContainer {
n := list.Len()
out := make(chan algoContainer)
go func () {
for i := 0; i < n; i++ {
result := list.Copy()
// actually useful:
if result.Less(n-1, 0) {
result.Swap(n-1, 0)
}
out <- result
}
close(out)
}()
return out
}
答案2
得分: 8
由于Go编程语言目前不支持泛型类型,这将很难实现。
请查看Go的sort包,了解它如何通过定义具有Len、Less和Swap方法的sort.Interface类型来处理与特定类型相关的比较和其他操作。
英文:
Since the Go Programming Language doesn't currently support generic types, this is going to be hard to do.
> Why does Go not have generic
> types?
>
> Generics may well be added at some
> point. We don't feel an urgency for
> them, although we understand some
> programmers do.
>
> Generics are convenient but they come
> at a cost in complexity in the type
> system and run-time. We haven't yet
> found a design that gives value
> proportionate to the complexity,
> although we continue to think about
> it. Meanwhile, Go's built-in maps and
> slices, plus the ability to use the
> empty interface to construct
> containers (with explicit unboxing)
> mean in many cases it is possible to
> write code that does what generics
> would enable, if less smoothly.
>
> This remains an open issue.
Look at the Go sort package to see how it handles comparisons and other operations specific to a type by defining the sort.Interface type with Len, Less, and Swap methods.
答案3
得分: 6
Go没有泛型类型,但你可以看一下<a href="http://golang.org/pkg/sort/">sort</a>是如何工作的,以找到一个解决方法。他们创建了一个类似这样的接口:
type Interface interface {
// Len是集合中元素的数量。
Len() int
// Less返回索引i的元素是否应该在索引j的元素之前排序。
Less(i, j int) bool
// Swap交换索引i和j的元素。
Swap(i, j int)
}
现在,对于任何自定义类型,你可以创建一个相应的自定义集合类型,可以进行排序。排序算法只需要处理整数和布尔值,所以不会看到或关心底层数据类型是什么。
英文:
Go does not have generic types, but you can take a look at how <a href="http://golang.org/pkg/sort/">sort</a> works to find a workaround. What they do is create an interface like this:
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns whether the element with index i should sort
// before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
And now for any custom type you can make a corresponding custom collection type that can be sorted. The sort algorithm only has to deal with integers and booleans, and so doesn't see or care what the underlying data types are.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论