golang sort.Sort 随机输出并且是错误的

Question

我有一个应用于结构的自定义排序函数。完整代码在 play.golang.org 上。

type Stmt struct {

    Name  string

    After []string

}

func sortStmts(stmts []Stmt) []Stmt {

    sort.Sort(ByAfter(stmts))

    return stmts

}

type ByAfter []Stmt

func (a ByAfter) Len() int      { return len(a) }

func (a ByAfter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func (a ByAfter) Less(i, j int) bool {

    isLess := true

    //fmt.Printf("%s.%+v is being compared with %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)

    for _, v := range a[i].After {

        if a[j].Name == v {

            isLess = false

            break

        }

    }

    if isLess {

        //fmt.Printf("%s.%+v is Before %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)

    } else {

        //fmt.Printf("%s.%+v is After %s.%+v\n", a[i].Name, a[i].After, a[j].Name, a[j].After)

    }

    return isLess

}

我的目的是自动创建一组正确排序的 sql create 语句，以便从属表先出现。

因此，如果Stmt{Name: "user_role", After: []string{"user", "role"} }存在，则在有序列表中user_role应该在user和 之后role。

在我们开始添加更多值之前，这似乎工作得很好。直到那时我才进去检查并意识到我可能只是第一次偶然幸运，但确实没有任何一致性。

我在排序函数中做错了什么，结果是随机的。我特别想知道为什么“角色”项目没有出现在“user_role”项目之前，即使我已经将它指定为 user_role 为在角色之后。

Answer 1

你的“Less”函数不是可传递的。也就是说，如果 A < B 且 B < C，那么它也必须成立 A < C。您不能使用常规排序函数指定偏序并获得排序输出。相反，您需要实现拓扑排序。这是对您的数据的简单实现（除了我删除了重复的“密码”条目）。package mainimport "fmt"type Stmt struct {&nbsp; &nbsp; Name&nbsp; string&nbsp; &nbsp; After []string}func topSort(ss []Stmt) []string {&nbsp; &nbsp; after := map[string][]string{} // things that must come after&nbsp; &nbsp; counts := map[string]int{}&nbsp; &nbsp; &nbsp;// number unsatified preconditions&nbsp; &nbsp; zc := map[string]struct{}{}&nbsp; &nbsp; // things with zero count&nbsp; &nbsp; for _, s := range ss {&nbsp; &nbsp; &nbsp; &nbsp; for _, a := range s.After {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; after[a] = append(after[a], s.Name)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; counts[s.Name] = len(s.After)&nbsp; &nbsp; &nbsp; &nbsp; if len(s.After) == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; zc[s.Name] = struct{}{}&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; r := []string{}&nbsp; &nbsp; for len(zc) > 0 {&nbsp; &nbsp; &nbsp; &nbsp; for n := range zc {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r = append(r, n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for _, a := range after[n] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counts[a]--&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if counts[a] == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; zc[a] = struct{}{}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; delete(zc, n)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return r}func main() {&nbsp; &nbsp; stmts := []Stmt{&nbsp; &nbsp; &nbsp; &nbsp; {Name: "app", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "billingplan", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_app", After: []string{"campaign", "app"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_ip", After: []string{"campaign", "ip"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_operator", After: []string{"campaign", "operator"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_sponsor", After: []string{"campaign", "sponsor"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_subscriberfilter", After: []string{"campaign", "subscriber_filters"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_url", After: []string{"campaign", "url"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "contentpartner", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "filter_criteria", After: []string{"campaign", "subscriber_filters"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "ip", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "mobile_registered", After: []string{"campaign", "app"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "operator", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "passwords", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "publish_package", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "role", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "sponsor", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "subscriber_dbs", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "subscriber_filters", After: []string{"subscriber_dbs"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "timezone", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "url", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "app_user", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "user_role", After: []string{"app_user", "role"}},&nbsp; &nbsp; }&nbsp; &nbsp; r := topSort(stmts)&nbsp; &nbsp; for _, s := range r {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(s)&nbsp; &nbsp; }}

Answer 2

正如匿名者所提到的，你需要一个拓扑排序。Tarjan 的强连通分量算法具有以反向拓扑排序顺序返回 SCC 的特性。这意味着它可以用作拓扑排序算法。这是基于维基百科伪代码的 Tarjan 算法的实现（可在此处运行，最初由我发布到 golang-nuts 列表）（更普遍地在此处实现，但使用基本相同的底层代码）：package mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "log")type Stmt struct {&nbsp; &nbsp; Name&nbsp; string&nbsp; &nbsp; After []string}func main() {&nbsp; &nbsp; stmts := []Stmt{&nbsp; &nbsp; &nbsp; &nbsp; {Name: "app", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "billingplan", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_app", After: []string{"campaign", "app"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_ip", After: []string{"campaign", "ip"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_operator", After: []string{"campaign", "operator"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_sponsor", After: []string{"campaign", "sponsor"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_subscriberfilter", After: []string{"campaign", "subscriber_filters"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "campaign_url", After: []string{"campaign", "url"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "contentpartner", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "filter_criteria", After: []string{"campaign", "subscriber_filters"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "ip", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "mobile_registered", After: []string{"campaign", "app"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "operator", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "passwords", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "publish_package", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "role", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "passwords", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "sponsor", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "subscriber_dbs", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "subscriber_filters", After: []string{"subscriber_dbs"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "timezone", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "url", After: []string{"app_user"}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "app_user", After: []string{}},&nbsp; &nbsp; &nbsp; &nbsp; {Name: "user_role", After: []string{"app_user", "role"}},&nbsp; &nbsp; }&nbsp; &nbsp; g := make(graph)&nbsp; &nbsp; for _, s := range stmts {&nbsp; &nbsp; &nbsp; &nbsp; g[s.Name] = after(s.After)&nbsp; &nbsp; }&nbsp; &nbsp; sorted, err := topoSort(g)&nbsp; &nbsp; if err != nil {&nbsp; &nbsp; &nbsp; &nbsp; log.Fatalf("could not sort: %v", err)&nbsp; &nbsp; }&nbsp; &nbsp; for _, s := range sorted {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(s)&nbsp; &nbsp; }}func topoSort(g graph) ([]string, error) {&nbsp; &nbsp; sccs := tarjanSCC(g)&nbsp; &nbsp; sorted := make([]string, len(sccs))&nbsp; &nbsp; for i, s := range sccs {&nbsp; &nbsp; &nbsp; &nbsp; if len(s) != 1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return nil, fmt.Errorf("found directed cycle: %q", s)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; sorted[i] = s[0]&nbsp; &nbsp; }&nbsp; &nbsp; return sorted, nil}// graph is an edge list representation of a directed graph.type graph map[string]set// set is an string set.type set map[string]struct{}func after(i []string) set {&nbsp; &nbsp; if len(i) == 0 {&nbsp; &nbsp; &nbsp; &nbsp; return nil&nbsp; &nbsp; }&nbsp; &nbsp; s := make(set)&nbsp; &nbsp; for _, v := range i {&nbsp; &nbsp; &nbsp; &nbsp; s[v] = struct{}{}&nbsp; &nbsp; }&nbsp; &nbsp; return s}// tarjanSCC returns a the strongly connected components of the// directed graph g.func tarjanSCC(g graph) [][]string {&nbsp; &nbsp; t := tarjan{&nbsp; &nbsp; &nbsp; &nbsp; g: g,&nbsp; &nbsp; &nbsp; &nbsp; indexTable: make(map[string]int, len(g)),&nbsp; &nbsp; &nbsp; &nbsp; lowLink:&nbsp; &nbsp; make(map[string]int, len(g)),&nbsp; &nbsp; &nbsp; &nbsp; onStack:&nbsp; &nbsp; make(map[string]bool, len(g)),&nbsp; &nbsp; }&nbsp; &nbsp; for v := range t.g {&nbsp; &nbsp; &nbsp; &nbsp; if t.indexTable[v] == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t.strongconnect(v)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return t.sccs}// tarjan implements Tarjan's strongly connected component finding// algorithm. The implementation is from the pseudocode at//// http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm//type tarjan struct {&nbsp; &nbsp; g graph&nbsp; &nbsp; index&nbsp; &nbsp; &nbsp; int&nbsp; &nbsp; indexTable map[string]int&nbsp; &nbsp; lowLink&nbsp; &nbsp; map[string]int&nbsp; &nbsp; onStack&nbsp; &nbsp; map[string]bool&nbsp; &nbsp; stack []string&nbsp; &nbsp; sccs [][]string}// strongconnect is the strongconnect function described in the// wikipedia article.func (t *tarjan) strongconnect(v string) {&nbsp; &nbsp; // Set the depth index for v to the smallest unused index.&nbsp; &nbsp; t.index++&nbsp; &nbsp; t.indexTable[v] = t.index&nbsp; &nbsp; t.lowLink[v] = t.index&nbsp; &nbsp; t.stack = append(t.stack, v)&nbsp; &nbsp; t.onStack[v] = true&nbsp; &nbsp; // Consider successors of v.&nbsp; &nbsp; for w := range t.g[v] {&nbsp; &nbsp; &nbsp; &nbsp; if t.indexTable[w] == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Successor w has not yet been visited; recur on it.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t.strongconnect(w)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t.lowLink[v] = min(t.lowLink[v], t.lowLink[w])&nbsp; &nbsp; &nbsp; &nbsp; } else if t.onStack[w] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Successor w is in stack s and hence in the current SCC.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t.lowLink[v] = min(t.lowLink[v], t.indexTable[w])&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // If v is a root node, pop the stack and generate an SCC.&nbsp; &nbsp; if t.lowLink[v] == t.indexTable[v] {&nbsp; &nbsp; &nbsp; &nbsp; // Start a new strongly connected component.&nbsp; &nbsp; &nbsp; &nbsp; var (&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; scc []string&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; w&nbsp; &nbsp;string&nbsp; &nbsp; &nbsp; &nbsp; )&nbsp; &nbsp; &nbsp; &nbsp; for {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; w, t.stack = t.stack[len(t.stack)-1], t.stack[:len(t.stack)-1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t.onStack[w] = false&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Add w to current strongly connected component.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; scc = append(scc, w)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if w == v {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // Output the current strongly connected component.&nbsp; &nbsp; &nbsp; &nbsp; t.sccs = append(t.sccs, scc)&nbsp; &nbsp; }}func min(a, b int) int {&nbsp; &nbsp; if a < b {&nbsp; &nbsp; &nbsp; &nbsp; return a&nbsp; &nbsp; }&nbsp; &nbsp; return b}请注意，重复运行此代码不会产生相同的严格输出顺序，因为许多路径相对于彼此并不是绝对可排序的（这不会显示在操场上，因为结果已被缓存 - 您可以看到这个尽管通过包装对 tarjanSCC 的调用）。虽然它可能是更容易直接实现拓扑排序，使用的Tarjan的SCC算法，我们能够找到一种失败的原因，例如这里（CF使用相同的数据在这里）。