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

您的"减少"功能不具有传递性.也就是说,如果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)
    }
}