我该如何计算两个表的增量（插入/删除/移动索引）？

问题描述

假设我有一个具有唯一的ID和属性，确定它们的顺序对象两份名单，我怎样才能最有效地获得增量指标（插入哪些索引，它被删除，并且被移动）？

Assuming I have two lists of objects that have unique ids and an attribute that determines their order, how can I efficiently get the delta indexes (which indexes were inserted, which were deleted, and which were moved)?

输入举例：

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 |    |     - |    |                      |
+-------+----+----------------------+    +-------+----+----------------------+

预期结果（增量）：

Expected result (delta):

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

推荐答案

有可通过利用2地图，从每个元素到它的索引的编号地图，和比较它们解决。

It can be solved by using 2 maps, that map from the ID of each element to its index, and comparing them.

时间复杂度为O（n）的散列地图和O（nlogn）用于基于树的映射。

Time complexity is O(n) for hash maps and O(nlogn) for tree based maps.

伪code：

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"

修改：（建议在评论）

您可以存储输出到 0（分{M，N}）和时间的情况下，基于树的映射最大限度地减少了 0（最大{M，N}日志（分钟{M，N}）），其中 M，N 是两个列表的大小，通过映射只有最小的列表，然后迭代阵列（这是不映射），而不是图

You can minimize memory output to O(min{m,n}) and time in case of tree-based map to O(max{m,n}log(min{m,n})), where m,n are the sizes of the two lists, by mapping only the smallest list, and then iterating the array (which was not mapped) rather than the map.

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

这篇关于我该如何计算两个表的增量（插入/删除/移动索引）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！