Golang中的Reverse在底层是如何工作的?

huangapple go评论79阅读模式
英文:

How does Reverse work in Golang under the hood?

问题

给定的代码使用了Go语言的排序包(sort)中的Reverse函数来对字符串切片进行反向排序。下面是对代码的翻译:

s := []string{"Zeno", "John", "Al", "Jenny"}

sort.Sort(sort.Reverse(sort.StringSlice(s)))

我无法理解Reverse的逻辑。

Reverse的源代码如下:

func Reverse(data Interface) Interface {
	return &reverse{data}
}
type reverse struct {
	// 这个嵌入的Interface允许Reverse使用另一个Interface实现的方法。
	Interface
}
type Interface interface {
	// Len返回集合中的元素个数。
	Len() int

	// Less报告索引为i的元素是否必须在索引为j的元素之前排序。
	//
	// 如果Less(i, j)和Less(j, i)都为false,
	// 那么索引为i和j的元素被认为是相等的。
	// Sort函数可以以任意顺序放置相等的元素在最终结果中,
	// 而Stable函数会保持相等元素的原始输入顺序。
	//
	// Less必须描述一个传递性的排序关系:
	//  - 如果Less(i, j)和Less(j, k)都为true,那么Less(i, k)也必须为true。
	//  - 如果Less(i, j)和Less(j, k)都为false,那么Less(i, k)也必须为false。
	//
	// 注意,当涉及到非数字(NaN)值时,浮点数比较(float32或float64值上的<运算符)不是传递性的排序关系。
	// 有关浮点数值的正确实现,请参见Float64Slice.Less函数。
	Less(i, j int) bool

	// Swap交换索引为i和j的元素。
	Swap(i, j int)
}

上述给出的操作是如何使给定的数组反向排序的呢?在Go语言的排序包中,排序的核心是通过实现Interface接口的LessLenSwap方法来实现的。Reverse函数接受一个实现了Interface接口的对象,并返回一个新的对象,该对象在调用LessLenSwap方法时会反转原始对象的行为。

在给定的代码中,sort.StringSlice(s)将字符串切片s转换为实现了Interface接口的对象。然后,sort.Reverse函数接受这个对象,并返回一个新的对象,该对象在调用LessLenSwap方法时会反转原始对象的行为。最后,sort.Sort函数对这个新的对象进行排序,实现了对字符串切片s的反向排序。

因此,给定的操作可以使给定的数组反向排序。

英文:
s := []string{&quot;Zeno&quot;, &quot;John&quot;, &quot;Al&quot;, &quot;Jenny&quot;}

sort.Sort(sort.Reverse(sort.StringSlice(s)))

I could not understand the logic of Reverse

The source code for Reverse seems as follows:

func Reverse(data Interface) Interface {
	return &amp;reverse{data}
}
type reverse struct {
	// This embedded Interface permits Reverse to use the methods of
	// another Interface implementation.
	Interface
}
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int

	// Less reports whether the element with index i
	// must sort before the element with index j.
	//
	// If both Less(i, j) and Less(j, i) are false,
	// then the elements at index i and j are considered equal.
	// Sort may place equal elements in any order in the final result,
	// while Stable preserves the original input order of equal elements.
	//
	// Less must describe a transitive ordering:
	//  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
	//  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
	//
	// Note that floating-point comparison (the &lt; operator on float32 or float64 values)
	// is not a transitive ordering when not-a-number (NaN) values are involved.
	// See Float64Slice.Less for a correct implementation for floating-point values.
	Less(i, j int) bool

	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

How do those given operations above induce the given array to be reversed?

答案1

得分: 1

如果你看一下sort.StringSlice类型,你会发现它实现了Less方法,注意比较x[i] < x[j],这意味着较小的元素排在前面。

func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }

然后注意sort.reverse类型(不是sort.Reverse接口),它也实现了Less方法,但是看看它是如何传递i和j参数的,接收i和j但是传递j和i,这等同于x[i] > x[j]。

// Less返回嵌入实现的Less方法的相反结果。
func (r reverse) Less(i, j int) bool {
    return r.Interface.Less(j, i)
}
英文:

If you look at the sort.StringSlice type, you can see it implements the Less method, notice the comparison x[i] < x[j], which means smaller element goes first.

func (x StringSlice) Less(i, j int) bool { return x[i] &lt; x[j] }

And then notice the sort.reverse type (not sort.Reverse interface), it also implements the Less method but see how it passes the i and j arguments, receives i and j but passes j and i, which is just equivalent to x[i] > x[j]

// Less returns the opposite of the embedded implementation&#39;s Less method.
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

huangapple
  • 本文由 发表于 2021年12月27日 22:44:45
  • 转载请务必保留本文链接:https://go.coder-hub.com/70496937.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定