我正在寻找一种通用算法来找到两个有序列表之间的最小差异。我在 Go 中需要它，所以让我们假设它们是字符串切片。列表示例：list := []string{ "Anna", "Mike", "Simon", "Jerry", "Louisa", "Mary",}请注意，此列表中的元素是唯一的。第二个列表将是此列表的更改版本。更改可能包括以下任何一种情况，单独或组合：一个（或多个）列表元素向上或向下移动一个或几个位置；两个元素交换位置；一个新元素替换了一个旧元素。作为比较的结果，我想要的是一组最小的更改，这些更改需要应用于第一个列表以获得第二个列表。然后我会使用这些数据来标记列表中的更改。例如，我想产生这样的输出：AnnaMike↑LouisaSimonJerryMary这说明在新的榜单中，“路易莎”已经上移了。我还想知道“路易莎”已经上升了2 个位置，但我不需要在我的输出中显示它。对我来说重要的是“Simon”和“Jerry”的位置也发生了变化，但列表之间的整体差异只能用“Louisa”向上移动2个位置来描述，而且这样的描述更短，所以我认为它是最小的这就是我想要得到的。有没有可以解决问题的软件包，或者可能是已知的算法？如果它很重要，那么列表的长度在我的情况下不会改变。
1 回答
喵喵时光机
TA贡献1846条经验 获得超7个赞
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
这是一个工作的游乐场示例。
我很确定它远非完美，但它肯定会满足我的需求。
- 1 回答
- 0 关注
- 102 浏览
添加回答
举报
0/150
提交
取消