小编典典

如何计算两个列表的增量(插入/删除/移动索引)?

swift

假设我有两个具有唯一ID的对象列表和一个确定其顺序的属性,那么如何有效地获取增量索引(插入了哪些索引,删除了哪些索引以及移动了哪些索引)?

输入示例:

let before: [(id: String, timestamp: String)] = [
    ("A", "2015-06-04T12:38:09Z"),
    ("B", "2015-06-04T10:12:45Z"),
    ("C", "2015-06-04T08:39:55Z"),
    ("D", "2015-06-03T23:58:32Z"),
    ("E", "2015-06-01T00:05:51Z"),
]

let after: [(id: String, timestamp: String)] = [
    ("F", "2015-06-04T16:13:01Z"),
    ("C", "2015-06-04T15:10:29Z"),
    ("A", "2015-06-04T12:38:09Z"),
    ("B", "2015-06-04T10:12:45Z"),
]

let delta = deltaFn(before, after)

上面是可视化的:

BEFORE                                   AFTER
+-------+----+----------------------+    +-------+----+----------------------+
| index | id | timestamp            |    | index | id | timestamp            |
+-------+----+----------------------+    +-------+----+----------------------+
|     0 |  A | 2015-06-04T12:38:09Z |    |     0 |  F | 2015-06-04T16:13:01Z |
|     1 |  B | 2015-06-04T10:12:45Z |    |     1 |  C | 2015-06-04T15:10:29Z |
|     2 |  C | 2015-06-04T08:39:55Z |    |     2 |  A | 2015-06-04T12:38:09Z |
|     3 |  D | 2015-06-03T23:58:32Z |    |     3 |  B | 2015-06-04T10:12:45Z |
|     4 |  E | 2015-06-01T00:05:51Z |    |     - |    |                      |
+-------+----+----------------------+    +-------+----+----------------------+

预期结果(增量):

Inserted indexes:  [0]
Deleted indexes:   [3, 4]
Moved indexes:     [(from: 0, to: 2), (from: 1, to: 3), (from: 2, to: 1)]

阅读 272

收藏
2020-07-07

共1个答案

小编典典

可以通过使用2个映射(从每个元素的ID到其索引的映射)并将它们进行比较来解决。

对于哈希映射,时间复杂度为O(n),对于基于树的映射,时间复杂度为O(nlogn)。

伪代码:

map1 = empty map
map2 = empty map
for each element x with index i in before:
    map1.insert(x,i)
for each element x with index i in after:
    map2.insert(x,i)

//find moved and deleted:
for each key x in map1:
   id1 = map1.get(x)
   id2 = map2.get(x)
   if id2 == nil:
       add id1 to "deleted indexes"
   else if id1 != id2:
       add (id1,id2) to "moved indexes"
       map2.delete(x)
//find new indexes:
for each key x in map2:
    add map2.get(x) to "inserted indexes"

编辑 :(建议在评论中)

通过仅映射最小的列表,然后迭代数组(未映射)而不是映射,可以将O(min{m,n})基于树的映射到的内存输出和时间减到最少(两个列表的大小O(max{m,n}log(min{m,n}))在哪里m,n)。

map = empty map
for each element x with index i in smaller list:
    map.insert(x,i)

for each element x with index i1 in larger list:
   i2 = map.get(x)
   if i2:
       if i1 != i2:
           add (i2, i1) to "moved indexes" if smaller list is before
           add (i1, i2) to "moved indexes" if smaller list is after
       map.delete(x)
   else:
       add i1 to "inserted indexes" if smaller list is before
       add i1 to "deleted indexes" if smaller list is after

// Find new indexes:
for each key x in map:
    add map.get(x) to "deleted indexes" if smaller list is before
    add map.get(x) to "inserted indexes" if smaller list is after
2020-07-07