比较两个有序列表的差异：顺序和内容

在IT行业这个发展更新速度很快的行业，只有不停止的学习，才不会被行业所淘汰。如果你是Golang学习者，那么本文《比较两个有序列表的差异：顺序和内容》就很适合你！本篇内容主要包括##content_title##，希望对大家的知识积累有所帮助，助力实战开发！

我正在寻找一种通用算法来查找两个有序列表之间的最小差异。

我在 go 中需要它，所以我们假设它们是字符串切片。列表示例：

list := []string{
    "anna",
    "mike",
    "simon",
    "jerry",
    "louisa",
    "mary",
}

请注意，此列表中的元素是唯一的。

第二个列表将是此列表的修改版本。更改可能包括以下任何情况，单独或组合：

• 一个（或多个）列表元素向上或向下移动一个或几个位置；
• 两个元素交换位置；
• 新元素替换旧元素之一。

我想要的比较结果是需要对第一个列表应用一组最小的更改才能获得第二个列表。然后我将使用这些数据来标记列表中的更改。例如，我想产生这样的输出：

Anna
Mike
↑Louisa
Simon
Jerry
Mary

这表明在新列表中，“louisa”已上升。我还想知道“louisa”已上升 2 个位置，但我不需要在输出中显示它。

对我来说重要的是“simon”和“jerry”的位置也发生了变化，但列表之间的整体差异可以用“louisa”向上移动 2 个位置来描述，并且这样的描述较短，所以我认为它是最小的，这就是我想要得到的。

是否有任何包可以做到这一点，或者可能是已知的算法？如果它很重要，那么在我的例子中列表的长度不会改变。

解决方案

volker 和 torek，谢谢您的评论，我发现它们与该问题最相关。对于偏离主题的内容，我深表歉意，我还没有太多在 stackoverflow 上提问的经验。

torek引用的文章重点是设计一种具有最高可实现效率的算法。这确实是一项伟大的成就，但在我的特定应用程序中，我将针对仅包含 10 个项目的列表使用此算法，并且仅在几个小时内使用一次，因此我不需要它具有一流的效率。因此，我对如何做到这一点有了一个相当简单的想法，而且它似乎有效。

这个想法是计算所有元素的新位置和旧位置之间的差异，找到移动最大的元素，在输出报告中标记它如何移动，并将其移动到新位置。然后重复直到列表相同。在此操作之前应解决列表组成的差异。我不能保证它在大列表上完全按预期工作，它们之间有很多差异，但我需要它来处理相对较短的列表，只有 1-2 个更改，所以它应该适合我。

这是一个示例代码：

// diff describes how an updated position of an element is different from an old one
// it's either a new element, or it's shifted by "shift" in "direction", or position didn't change
type diff struct {
    shift int
    direction direction
    isnew bool
}

type direction int
const (
    up = direction(-1)
    down = direction(1)
    none = direction(0)
)

func hasshifts(shifts []diff) bool {
    for _, d := range shifts {
        if d.shift != 0 {
            return true
        }
    }
    return false
}

func diffs(old, updated []string) (shifts []diff) {
    for i, newel := range updated {
        for j, oldel := range old {
            if newel == oldel {
                var dir direction
                switch {
                case i < j:
                    dir = up
                case i > j:
                    dir = down
                default:
                    dir = none
                }
                shifts = append(shifts, diff{int(math.abs(float64(i-j))), dir, false})
                break
            }
        }
        if len(shifts) < i+1 {
            shifts = append(shifts, diff{isnew: true})
        }
    }
    return
}

func move(list *[]string, position, shift int, dir direction) {
    for i := position; i != position + shift * int(dir); i += int(dir) {
        (*list)[i], (*list)[i+int(dir)] = (*list)[i+int(dir)], (*list)[i]
    }
}

func compare(old, updated []string) (report []string) {
    report = append([]string{}, updated...)

    // first, find and mark updated elements; add them to the old list
    shifts := diffs(old, updated)
    for i, d := range shifts {
        if d.isnew {
            old = append(old[:i], append(updated[i:i+1], old[i:]...)...)
            report[i] = "*" + report[i]
        }
    }

    // remove elements of the old list that aren't present in the updated
    shifts = diffs(updated, old) // reversed
    n := 0
    for i, d := range shifts {
        if !d.isnew {
            old[n] = old[i]
            n++
        }
    }
    old = old[:n]

    // until lists are identical
    shifts = diffs(old, updated)
    for hasshifts(shifts) {
        // find an element with the largest shift
        highest := 0
        for i, d := range shifts {
            if d.shift > shifts[highest].shift || (d.shift == shifts[highest].shift && d.direction == up) {
                highest = i
            }
        }

        // mark in report how this element shifted
        if shifts[highest].direction == up {
            report[highest] = "↑" + report[highest]
        } else {
            report[highest] = "↓" + report[highest]
        }

        // move this element in the old list to its updated place
        for i, oldel := range old {
            if oldel == updated[highest] {
                move(&old, i, shifts[highest].shift, shifts[highest].direction)
                break
            }
        }

        // update diffs
        shifts = diffs(old, updated)
    }
    return
}

函数 compare(old, updated) 返回一个字符串列表，通过以下方式说明两个列表之间的更改：

• 它的顺序和组成与更新后的列表相同；
• 前缀“*”将添加到更新列表的所有新元素中；
• 为需要上移（向列表开头）的元素添加前缀“↑”，以将旧列表转换为更新后的列表；
• 需要下移的元素添加前缀“↓”；
• 它优先考虑“向上”移动（如果两个相邻元素交换了位置）。

让我们使用以下列表来测试它：

var (
    old = []string{
        "first",
        "second",
        "third",
        "fourth",
        "fifth",
        "sixth",
        "seventh",
        "eighth",
        "ninth",
        "tenth",
    }
    updated = []string{
        "eighth",
        "second",
        "third",
        "first",
        "fourth",
        "new",
        "sixth",
        "seventh",
        "tenth",
        "ninth",
    }
)

结果将是：

↑eighth
second
third
↓first
fourth
*new
sixth
seventh
↑tenth
ninth

这是一个有效的 go playground example。

我很确定它远非完美，但它肯定能满足我的需要。

今天关于《比较两个有序列表的差异：顺序和内容》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！