内容
list-diff 源码[1] 代码是大佬 livoras[2] 所写，本文对此代码进行详细解释
列表对比算法
问题
-
如果列表中元素的顺序为 1 2 3 4，现在要把列表中元素的顺序移动为2 1 3 4，应该怎样做呢？ -
相信你肯定想到了，应该把 1和2交换位置；咱们现在把交换位置这个操作，可以看成删除第0个位置的元素，和在第1个位置添加元素1的结合。 -
所以列表中元素的操作就只有增加和删除。
贪心算法
-
问题：如果列表中元素的顺序为
1 2 3 4，现在要把列表中元素的顺序移动为4 2 3 1，应该怎样做呢？ -
这时，我们可以利用贪心算法的思路来进行思考【也就是
要尽可能少的进行移动，让新列表和旧列表同一位置的元素相同。根据这个想法，如果想让新列表和旧列表同一位置的元素相同，可以删除旧列表这个位置的元素，再添加正确的元素。上面这个过程需要两步，也就是说，一个位置的元素操作最多两步，使用贪心算法，操作必须为零步或一步】 -
零步：那就是新旧列表中同一位置元素相同，不需要进行任何操作。
-
一步：操作可以为增加或删除。这两种操作应该如何选择呢？
再次回到贪心算法的目的，让新旧列表中同一位置的元素相同，如果在这个位置增加和新列表相同的元素，当然可以使得元素相同。那么什么时候选择删除呢？如果要选择删除，说明了，删除之后，相同位置的元素变得相同。
例如： 1 2 3 4 要变成 2 1 3 4 首先遍历到第一个元素，发现不相同，可以增加2；检查1后面的那个元素2，发现和当前的元素相同，选择删除 删除之后变为 2 3 4 继续遍历下一个元素 3，发现和 1 不相同，可以增加1；检查 3 后面的元素是 4，发现和当前元素不相同，所以增加 1 增加之后变为 2 1 3 4 继续往后遍历，发现都相同
-
所以目前咱们的遍历算法就设计好了
注意
-
上面算法可以提高效率的前提是新旧列表中至少有一部分是相同的，只是位置不同
-
比如
1 2 3 4和3 4 2 1，3 4这部分是相同的，所以可以利用上述算法来提高效率 -
如果是
1 2 3 4和4 3 2 1完全没有相同的部分，只能在每一个位置增加新元素，然后删掉多余的部分“` // 例如： 1 2 3 4 4 3 2 1 1 2 3 4 4 3 2 1 // 删除后面的
key 的作用
key 存在（新旧列表全部都设置 key）
-
如果有 key 的话，可以很容易定位旧列表的元素在新列表中存不存在，不需要每次都遍历新列表 -
如果旧列表中的元素在新列表中不存在，那么就将旧列表中的这个元素删除 -
至此，旧列表中的元素都存在于新列表中，但是新列表中的元素不一定都在旧列表中 -
问题变成了使用上面的列表对比算法来使新旧列表元素相同。
key 不存在（新旧列表全部都没有设置 key）
-
因为不知道新旧列表中是否有某些部分是相同的，所以不能使用上述算法提高效率。直接返回 {}。
新旧列表中一部分设置了 key，另一部分没有设置 key
-
对设置了 key 的使用算法。 -
没有设置 key 的，直接在旧列表这个位置增加这个元素
代码
删除旧列表多余的元素
根据元素 key 来判断是否需要删除
-
遍历旧集合，根据 key 判断这个元素是否在新集合中存在。如果不存在，将 children 加入null，说明将来是要删除的。如果存在，将这个元素直接加入 children
删除在旧列表中属性不为key且这个位置不需要的元素
-
如果新列表中没有添加 key 的元素个数要小于旧列表中没有添加 key 的元素个数，那么要将旧列表中一部分位置删除，直到和新列表中没有添加 key 的元素个数相同。
代码
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
// key = 'id'
function diff (oldList, newList, key) {
var oldMap = makeKeyIndexAndFree(oldList, key)
var newMap = makeKeyIndexAndFree(newList, key)
var newFree = newMap.free
var oldKeyIndex = oldMap.keyIndex
var newKeyIndex = newMap.keyIndex
var moves = []
var children = []
var i = 0
var item
var itemKey
var freeIndex = 0
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
while (i < oldList.length) {
// item {id: "a"}
item = oldList[i]
// itemKey a
itemKey = getItemKey(item, key)
if (itemKey) {
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
// newKeyIndex: [c:0, a:1, b:2, e: 3, f: 4]
if (!newKeyIndex.hasOwnProperty(itemKey)) {
children.push(null)
} else {
var newItemIndex = newKeyIndex[itemKey]
children.push(newList[newItemIndex])
}
} else {
// 删除在旧列表中属性不为key且这个位置不需要的元素
var freeItem = newFree[freeIndex++]
children.push(freeItem || null)
}
i++
}
// 执行删除操作
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
// children [{id:"a"},{id:"b"},{id:"c"},null,{id:"e"}]
var simulateList = children.slice(0)
i = 0
while (i < simulateList.length) {
if (simulateList[i] === null) {
remove(i) // 加入操作数组
removeSimulate(i) // 从 simulateList 中移除
} else {
i++
}
}
// 操作函数
function remove (index) {
var move = {index: index, type: 0}
moves.push(move)
}
function insert (index, item) {
var move = {index: index, item: item, type: 1}
moves.push(move)
}
function removeSimulate (index) {
simulateList.splice(index, 1)
}
}
/**
* Convert list to key-item keyIndex object.
* 将列表转换为 key-item 的键值对象
* [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}] -> [a:0,b:1,c:2...]
* @param {Array} list
* @param {String|Function} key
*/
function makeKeyIndexAndFree (list, key) {
var keyIndex = {}
var free = []
for (var i = 0, len = list.length; i < len; i++) {
var item = list[i]
var itemKey = getItemKey(item, key)
if (itemKey) {
keyIndex[itemKey] = i
} else {
free.push(item)
}
}
return {
keyIndex: keyIndex,
free: free
}
}
// 获取置顶key的value
function getItemKey (item, key) {
if (!item || !key) return void 666
return typeof key === 'string'
? item[key]
: key(item) // 如果传来的 key 是一个函数，例如function(item){ return item }
}
使用列表对比算法对新旧列表进行操作
// 遍历 newList 和 simulateList
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}] i
// simulateList [{id:"a"},{id:"b"},{id:"c"},{id:"e"}] j
var j = i = 0
while (i < newList.length) {
item = newList[i]
itemKey = getItemKey(item, key) // c
var simulateItem = simulateList[j] // {id:"a"}
var simulateItemKey = getItemKey(simulateItem, key) // a
// newList 不为空或者 oldList 不为空
if (simulateItem) {
// 新旧集合中 key-value 相等，而且位置相同 ———————— 列表对比算法相同的那一种情况
// 或者是
// undefined === undefined 说明新旧集合中都没有设置 key，不做任何操作
if (itemKey === simulateItemKey) {
j++
} else {
// 旧集合中没有设置 key
// 列表对比算法是针对设置了 key 的算法，没有设置就直接插入
if (!oldKeyIndex.hasOwnProperty(itemKey)) {
insert(i, item)
} else {
// 列表对比算法不相同的那一种情况【列表对比算法是针对设置了 key 的算法】
// 获取下一个位置的元素
var nextItemKey = getItemKey(simulateList[j + 1], key)
// 如果设置了 key 且和当前元素【itemKey】相同，删除这个位置的元素
if (nextItemKey === itemKey) {
remove(i)
removeSimulate(j)
j++
} else {
// 增加
insert(i, item)
}
}
}
} else {
// 这个语句可以执行的条件是：oldList为空，而newList不为空
insert(i, item)
}
i++
}
// 移除掉多余的元素
var k = simulateList.length - j
while (j++ < simulateList.length) {
k--
remove(k + i)
}
完整代码
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
function diff (oldList, newList, key) {
// oldMap: [a:0,b:1,c:2...]
var oldMap = makeKeyIndexAndFree(oldList, key)
var newMap = makeKeyIndexAndFree(newList, key)
var newFree = newMap.free
var oldKeyIndex = oldMap.keyIndex
var newKeyIndex = newMap.keyIndex
var moves = []
// a simulate list to manipulate
var children = []
var i = 0
var item
var itemKey
var freeIndex = 0
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
while (i < oldList.length) {
// item {id: "a"}
item = oldList[i]
// itemKey a
itemKey = getItemKey(item, key)
if (itemKey) {
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
// newKeyIndex: [c:0, a:1, b:2, e: 3, f: 4]
if (!newKeyIndex.hasOwnProperty(itemKey)) {
children.push(null)
} else {
var newItemIndex = newKeyIndex[itemKey]
children.push(newList[newItemIndex])
}
} else {
// 删除在旧列表中属性不为key且这个位置不需要的元素
var freeItem = newFree[freeIndex++]
children.push(freeItem || null)
}
i++
}
// 执行删除操作
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]
// children [{id:"a"},{id:"b"},{id:"c"},null,{id:"e"}]
var simulateList = children.slice(0)
i = 0
while (i < simulateList.length) {
if (simulateList[i] === null) {
remove(i) // 加入操作数组
removeSimulate(i) // 从 simulateList 中移除
} else {
i++
}
}
// 遍历 newList 和 simulateList
// oldList = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
// newList = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}] i
// simulateList [{id:"a"},{id:"b"},{id:"c"},{id:"e"}] j
var j = i = 0
while (i < newList.length) {
item = newList[i]
itemKey = getItemKey(item, key) // c
var simulateItem = simulateList[j] // {id:"a"}
var simulateItemKey = getItemKey(simulateItem, key) // a
// newList 不为空或者 oldList 不为空
if (simulateItem) {
// 新旧集合中 key-value 相等，而且位置相同 ———————— 列表对比算法相同的那一种情况
// 或者是
// undefined === undefined 说明新旧集合中都没有设置 key，不做任何操作
if (itemKey === simulateItemKey) {
j++
} else {
// 旧集合中没有设置 key
// 列表对比算法是针对设置了 key 的算法，没有设置就直接插入
if (!oldKeyIndex.hasOwnProperty(itemKey)) {
insert(i, item)
} else {
// 列表对比算法不相同的那一种情况【列表对比算法是针对设置了 key 的算法】
// 获取下一个位置的元素
var nextItemKey = getItemKey(simulateList[j + 1], key)
// 如果设置了 key 且和当前元素【itemKey】相同，删除这个位置的元素
if (nextItemKey === itemKey) {
remove(i)
removeSimulate(j)
j++
} else {
// 增加
insert(i, item)
}
}
}
} else {
// 这个语句可以执行的条件是：oldList为空，而newList不为空
insert(i, item)
}
i++
}
// 移除掉多余的元素
var k = simulateList.length - j
while (j++ < simulateList.length) {
k--
remove(k + i)
}
function remove (index) {
var move = {index: index, type: 0}
moves.push(move)
}
function insert (index, item) {
var move = {index: index, item: item, type: 1}
moves.push(move)
}
function removeSimulate (index) {
simulateList.splice(index, 1)
}
return {
moves: moves,
children: children
}
}
/**
* Convert list to key-item keyIndex object.
* 将列表转换为 key-item 的键值对象
* [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}] -> [a:0,b:1,c:2...]
* @param {Array} list
* @param {String|Function} key
*/
function makeKeyIndexAndFree (list, key) {
var keyIndex = {}
var free = []
for (var i = 0, len = list.length; i < len; i++) {
var item = list[i]
var itemKey = getItemKey(item, key)
if (itemKey) {
keyIndex[itemKey] = i
} else {
free.push(item)
}
}
return {
keyIndex: keyIndex,
free: free
}
}
// 获取置顶key的value
function getItemKey (item, key) {
if (!item || !key) return void 666
return typeof key === 'string'
? item[key]
: key(item) // 如果传来的 key 是一个函数，例如function(item){ return item }
}
exports.makeKeyIndexAndFree = makeKeyIndexAndFree // exports for test
exports.diff = diff
本文转自 https://juejin.cn/post/7078934768645046286，如有侵权，请联系删除。
参考资料
https://github.com/livoras/list-diff/blob/master/lib/diff.js: https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2Flivoras%2Flist-diff%2Fblob%2Fmaster%2Flib%2Fdiff.js
[2]
https://www.zhihu.com/people/livoras.com: https://link.juejin.cn/?target=https%3A%2F%2Fwww.zhihu.com%2Fpeople%2Flivoras.com
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/20471.html
