金刚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语句，这样依赖表才是第一位的。

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

在我们开始增加更多的价值之前，这似乎很好。直到那时，我才进去检查，并意识到，我可能只是意外地得到幸运的第一次，但真的没有任何一致性。

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

Answer 1

正如匿名者所提到的，您需要对此进行拓扑排序。Tarjan强连通分量算法具有如下性质: SCCs按反向拓扑排序顺序返回。这意味着它可以作为一个拓扑排序算法。

下面是基于维基百科的伪代码(更一般实现的是这里，但使用了基本相同的底层代码)的Tarjan算法的实现(由我运行的已发布和最初的这里 )：

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算法，我们可以找到导致排序失败的原因，例如这里 (具有相同数据的这里)。

Answer 2

你的“较少”功能不是传递性的。也就是说，如果A

不能使用常规排序函数指定部分顺序并获得排序输出。相反，您需要实现一个拓扑排序。

以下是您的数据上的一个简单实现(除了删除重复的“密码”条目外)。

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 3

这个问题在这里得到了回答：https://groups.google.com/forum/#!topic/golang-nuts/C_7JY1f3cSc。这是一个更详细和具体的答案，我可以立即使用。要求这个人在这里更新但他/她还没有..。所以我自己来吧。

因为我有一个泰詹躺在附近。以下是该数据的拓扑排序：

http://play.golang.org/p/SHagFMvuhl

在清华，2015-03-12，22:47 -0700，Sathish VJ写道：

在我的例子中，我确实检查了依赖项中的传递性。当我打印调试语句时，我注意到的一件具体事情是，一些比较永远不会发生。例如，到目前为止，user_role从未与角色相比较。虽然曾经有过一些不那么重要的元素，但它确实如此。

sort.Sort不会进行所有的比较。这将导致O(n^2)时间。