假设我有一个具有唯一的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
相关推荐
最新文章