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 []Stmtfunc (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 main

import "fmt"

type Stmt struct {

    Name  string

    After []string

}

func topSort(ss []Stmt) []string {

    after := map[string][]string{} // things that must come after

    counts := map[string]int{}     // number unsatified preconditions

    zc := map[string]struct{}{}    // things with zero count

    for _, s := range ss {

        for _, a := range s.After {

            after[a] = append(after[a], s.Name)

        }

        counts[s.Name] = len(s.After)

        if len(s.After) == 0 {

            zc[s.Name] = struct{}{}

        }

    }

    r := []string{}

    for len(zc) > 0 {

        for n := range zc {

            r = append(r, n)

            for _, a := range after[n] {

                counts[a]--

                if counts[a] == 0 {

                    zc[a] = struct{}{}

                }

            }

            delete(zc, n)

        }

    }

    return r

}

func main() {

    stmts := []Stmt{

        {Name: "app", After: []string{"app_user"}},

        {Name: "billingplan", After: []string{}},

        {Name: "campaign", After: []string{"app_user"}},

        {Name: "campaign_app", After: []string{"campaign", "app"}},

        {Name: "campaign_ip", After: []string{"campaign", "ip"}},

        {Name: "campaign_operator", After: []string{"campaign", "operator"}},

        {Name: "campaign_sponsor", After: []string{"campaign", "sponsor"}},

        {Name: "campaign_subscriberfilter", After: []string{"campaign", "subscriber_filters"}},

        {Name: "campaign_url", After: []string{"campaign", "url"}},

        {Name: "contentpartner", After: []string{"app_user"}},

        {Name: "filter_criteria", After: []string{"campaign", "subscriber_filters"}},

        {Name: "ip", After: []string{"app_user"}},

        {Name: "mobile_registered", After: []string{"campaign", "app"}},

        {Name: "operator", After: []string{}},

        {Name: "passwords", After: []string{"app_user"}},

        {Name: "publish_package", After: []string{}},

        {Name: "role", After: []string{}},

        {Name: "sponsor", After: []string{"app_user"}},

        {Name: "subscriber_dbs", After: []string{}},

        {Name: "subscriber_filters", After: []string{"subscriber_dbs"}},

        {Name: "timezone", After: []string{}},

        {Name: "url", After: []string{"app_user"}},

        {Name: "app_user", After: []string{}},

        {Name: "user_role", After: []string{"app_user", "role"}},

    }

    r := topSort(stmts)

    for _, s := range r {

        fmt.Println(s)

    }

}

Answer 2

正如匿名者所提到的，你需要一个拓扑排序。Tarjan 的强连通分量算法具有以反向拓扑排序顺序返回 SCC 的特性。这意味着它可以用作拓扑排序算法。

这是基于维基百科伪代码的 Tarjan 算法的实现（可在此处运行，最初由我发布到 golang-nuts 列表）（更普遍地在此处实现，但使用基本相同的底层代码）：

package main

import (

    "fmt"

    "log"

)

type Stmt struct {

    Name  string

    After []string

}

func main() {

    stmts := []Stmt{

        {Name: "app", After: []string{"app_user"}},

        {Name: "billingplan", After: []string{}},

        {Name: "campaign", After: []string{"app_user"}},

        {Name: "campaign_app", After: []string{"campaign", "app"}},

        {Name: "campaign_ip", After: []string{"campaign", "ip"}},

        {Name: "campaign_operator", After: []string{"campaign", "operator"}},

        {Name: "campaign_sponsor", After: []string{"campaign", "sponsor"}},

        {Name: "campaign_subscriberfilter", After: []string{"campaign", "subscriber_filters"}},

        {Name: "campaign_url", After: []string{"campaign", "url"}},

        {Name: "contentpartner", After: []string{"app_user"}},

        {Name: "filter_criteria", After: []string{"campaign", "subscriber_filters"}},

        {Name: "ip", After: []string{"app_user"}},

        {Name: "mobile_registered", After: []string{"campaign", "app"}},

        {Name: "operator", After: []string{}},

        {Name: "passwords", After: []string{"app_user"}},

        {Name: "publish_package", After: []string{}},

        {Name: "role", After: []string{}},

        {Name: "passwords", After: []string{"app_user"}},

        {Name: "sponsor", After: []string{"app_user"}},

        {Name: "subscriber_dbs", After: []string{}},

        {Name: "subscriber_filters", After: []string{"subscriber_dbs"}},

        {Name: "timezone", After: []string{}},

        {Name: "url", After: []string{"app_user"}},

        {Name: "app_user", After: []string{}},

        {Name: "user_role", After: []string{"app_user", "role"}},

    }

    g := make(graph)

    for _, s := range stmts {

        g[s.Name] = after(s.After)

    }

    sorted, err := topoSort(g)

    if err != nil {

        log.Fatalf("could not sort: %v", err)

    }

    for _, s := range sorted {

        fmt.Println(s)

    }

}

func topoSort(g graph) ([]string, error) {

    sccs := tarjanSCC(g)

    sorted := make([]string, len(sccs))

    for i, s := range sccs {

        if len(s) != 1 {

            return nil, fmt.Errorf("found directed cycle: %q", s)

        }

        sorted[i] = s[0]

    }

    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 {

    if len(i) == 0 {

        return nil

    }

    s := make(set)

    for _, v := range i {

        s[v] = struct{}{}

    }

    return s

}

// tarjanSCC returns a the strongly connected components of the

// directed graph g.

func tarjanSCC(g graph) [][]string {

    t := tarjan{

        g: g,

        indexTable: make(map[string]int, len(g)),

        lowLink:    make(map[string]int, len(g)),

        onStack:    make(map[string]bool, len(g)),

    }

    for v := range t.g {

        if t.indexTable[v] == 0 {

            t.strongconnect(v)

        }

    }

    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 {

    g graph

    index      int

    indexTable map[string]int

    lowLink    map[string]int

    onStack    map[string]bool

    stack []string

    sccs [][]string

}

// strongconnect is the strongconnect function described in the

// wikipedia article.

func (t *tarjan) strongconnect(v string) {

    // Set the depth index for v to the smallest unused index.

    t.index++

    t.indexTable[v] = t.index

    t.lowLink[v] = t.index

    t.stack = append(t.stack, v)

    t.onStack[v] = true

    // Consider successors of v.

    for w := range t.g[v] {

        if t.indexTable[w] == 0 {

            // Successor w has not yet been visited; recur on it.

            t.strongconnect(w)

            t.lowLink[v] = min(t.lowLink[v], t.lowLink[w])

        } else if t.onStack[w] {

            // Successor w is in stack s and hence in the current SCC.

            t.lowLink[v] = min(t.lowLink[v], t.indexTable[w])

        }

    }

    // If v is a root node, pop the stack and generate an SCC.

    if t.lowLink[v] == t.indexTable[v] {

        // Start a new strongly connected component.

        var (

            scc []string

            w   string

        )

        for {

            w, t.stack = t.stack[len(t.stack)-1], t.stack[:len(t.stack)-1]

            t.onStack[w] = false

            // Add w to current strongly connected component.

            scc = append(scc, w)

            if w == v {

                break

            }

        }

        // Output the current strongly connected component.

        t.sccs = append(t.sccs, scc)

    }

}

func min(a, b int) int {

    if a < b {

        return a

    }

    return b

}

请注意，重复运行此代码不会产生相同的严格输出顺序，因为许多路径相对于彼此并不是绝对可排序的（这不会显示在操场上，因为结果已被缓存 - 您可以看到这个尽管通过包装对 tarjanSCC 的调用）。

虽然它可能是更容易直接实现拓扑排序，使用的Tarjan的SCC算法，我们能够找到一种失败的原因，例如这里（CF使用相同的数据在这里）。